How Can We Make 100! Divisible by 12^{49}?

  • Thread starter Gokul43201
  • Start date
  • Tags
    Game
In summary, the conversation was about a Q&A game where one person asks a math question and others try to answer it. The first correct answer gets to ask the next question. One of the questions was about finding the least number that must be multiplied to 100! to make it divisible by 12^{49}. The correct answer was 12^{49} / 100!. There was also a question about why mathematicians often forget to specify that they require a whole number solution.
  • #176
O well since I guess I got the last one, I'll just ask again what post 169 asked: How can one find the surface area of a ring?
 
Mathematics news on Phys.org
  • #177
Here's one:

Let G be a group of odd order. Prove that for every element g in G, there is exactly one element h in G such that h2=g.
 
  • #178
Cute problem

I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose [tex]p(x)[/tex] is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate [tex]p(x)[/tex] at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of [tex]p(x)[/tex]?
 
Last edited:
  • #179
StatusX said:
Here's one:

Let G be a group of odd order. Prove that for every element g in G, there is exactly one element h in G such that h2=g.
Because |G| is odd, so too is o(g) for each g in G. Consequently, o(g^2)=o(g). This means that <g^2>=<g>, and do this for each g in G. [Alternatively, let o(g)=2k-1 so that g^(2k-1)=1 => (g^k)^2 = g.]

For uniqueness, let S={g^2 : g in G}, and note that |S|<=|G|. On the other hand, each element in G is a square, and all the squares in G come out of S, so that |G|<=|S|.
 
  • #180
rs1n said:
I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose [tex]p(x)[/tex] is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate [tex]p(x)[/tex] at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of [tex]p(x)[/tex]?
Hmm. Are there any restrictions on x, i.e. does it have to be a nonnegative integer? And can we use knowledge gathered from evaluating at the first value to pick the second one?

My initial guess was +/- 1, but that won't be sufficient most of the time. So maybe +/- 1/d, but this also doesn't seem to be very helpful for large degrees. It seems impossible to do it with two values picked at the same time!
 
  • #181
morphism said:
Hmm. Are there any restrictions on x, i.e. does it have to be a nonnegative integer? And can we use knowledge gathered from evaluating at the first value to pick the second one?

My initial guess was +/- 1, but that won't be sufficient most of the time. So maybe +/- 1/d, but this also doesn't seem to be very helpful for large degrees. It seems impossible to do it with two values picked at the same time!

There are no restrictions on x, other than [tex]x\in \mathbb{R}[/tex]. And yes, you may use the information you obtained from one evaluation in your other evaluation of [tex]p(x)[/tex]. That is, if you evaluate at x=a, you may use the information obtained from p(a) to pick your second value of x.
 
Last edited:
  • #182
rs1n said:
I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose [tex]p(x)[/tex] is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate [tex]p(x)[/tex] at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of [tex]p(x)[/tex]?
Has something to do with the dth root of something like, I dunno, 2. Or maybe a better one to do is this: first evaluate p(1), that's the sum of all the coefficients. Then pick a prime P > p(1), and evaluate p(P). Then if you consider p(P) mod P², p(P) mod P³, ..., p(P) mod Pd or something you can recover the coefficients.
 
  • #183
AKG said:
Or maybe a better one to do is this: first evaluate p(1), that's the sum of all the coefficients. Then pick a prime P > p(1), and evaluate p(P). Then if you consider p(P) mod P², p(P) mod P³, ..., p(P) mod Pd or something you can recover the coefficients.

That's essentially it, but there's still some extra math required if you pick a prime. Instead, let [tex]n=\lceil \log_{10} p(1) \rceil[/tex]. Then evaluate [tex]p(10^n)[/tex]. The k-th coefficient can be recovered by simply reading off the k-th block of n digits.

Example:

p(x) = 99 x^2 + 23.
p(1) = 99+23 = 122.
n = 3

p(1000) = 99 (1000)^2 + 23 = 099, 000, 023
 
  • #184
Surely a single evaluation of p(x) will do. Just take x to be any transcendental number. Eg, x=e. Of course, restricting to integer x is more interesting.
 
  • #185
Are you sure you guys weren't one of the sources used in "An Introduction to Criminalistics?"
 
Last edited:
  • #186


I know.
 
  • #187


We could all just try to fingure out what pi really is.
 
  • #188


Some of you might have seen this before, but I just found it, and it has such a nice solution I thought I'd post it:

Say we have N people, and we have a door we want to lock in such a way that at least M of the people must be present in order for it be unlocked. To do this, we use some number L of locks and distribute keys to each of the people, so that when any M of them are present, they have all the keys among them, but for a group of fewer than M, some keys will be missing. What's the best way to do this (ie, the minimal L)?

I'll post the solution in a few days if no one else does.
 
  • #189


Cool question
N choose (M-1). For every subset of M-1 people there must be a key belonging to everyone except them
Easy once you spot the trick.
 
  • #190


That's right. Were you able to prove that's the optimal solution, ie, has the least number of locks and keys?
 
  • #191


Here's the proof, if anyone's interested:

Pick some group of M-1 people. This group must be missing the key to at least one lock. But since the addition of anyone else gives them the necessary M people, anyone outside the group must have the keys to all their missing locks. In particular, each person either has all or none of the keys to this set of locks, so if there's more than one, we might as well consolidate them into a single lock.

Thus we have a map from the set of M-1 person subsets (a set with N choose M-1 elements) to the set of locks. We show it's a bijection. If it wasn't injective, and two M-1 person subsets were missing the same lock, then their union, a group of at least M people, would also be missing the lock, a contradiction. If it wasn't surjective, there would be locks that no M-1 person group is missing, but then we clearly don't need these locks.

Thus an optimal solution has N choose M-1 locks, with one lock for each M-1 person group, and with the people in the group being precisely the people who don't have the key to the corresponding lock.
 
  • #192


Since no-one has posted a new question in over a month, here's a cool one I saw somewhere:

In a very long hallway, there are 1000 doors all initially open. Consider the following process:
First, you close every door.
Second, you open every other door.
Next, you toggle the state of every 3rd door (open it if it is closed and close it if it is open),
Next, you toggle every 4th door,
and you continue this process, toggling the state of every nth door.

At the end of this process (when n=1000), how many doors are open?

Here is a diagram:
http://img504.imageshack.us/img504/1967/door2rc2.gif [Broken]
 
Last edited by a moderator:
  • #193


maze's question is classic... the answer is
N-floor (sqrt(N))
the nice animation makes it kinda obvious... the reason is only perfect squares have an odd number of distinct divisors.

problem 2 above
it suffices to find # of ways to arrange coins such that each row has one coin. This is easily given as [tex]n^n[/tex], so answer is [tex]1-n^n/ \binom{n^2}{n}[/tex]... if you want to find probability such that at least one row or one column has no silver coin, then it would be [tex]1-n!/ \binom{n^2}{n}[/tex]

problem 3 above
LHS is less than or equal to [tex]a(a+b+c)+b(a+b+c)+c(a+b+c)[/tex] by weighted AM-GM inequality, which is clearly less than or equal to 1

Problem 1 seems too long and I am feeling kinda lazy...

Now for my problem... hmmmm... after all these years... let's see...I'm not sure if this is appropriate:

prove that all one dimensional compact connected Lie group (a manifold that is also a group with smooth multiplication) is diffeo-isomorphic to S1 (the circle).

In case we want to make things "elementary", evaluate:
[tex]\int_{0}^\infty \frac{dx}{1+x^n}[/tex]
In case you think a simple contour will bring this problem down... try to evaluate it for n>1, not just integers.edit: sorry, latex just doesn't work well with spoiler alerts...
 
Last edited:
  • #194


I wasn't able to solve the following problem when I came across it, if anyone wants to give it a shot:

18 people play in a tournament that has 17 rounds of 9 games. Each person plays in only one game in each of the rounds and plays every other person no more than once in the tournament. After n rounds there are 4 people who have only played one game, what is the largest possible n?
 
Last edited:
  • #195


For tim's integral:

Its simply differentiating the integral with respect to n. We get that I'(n) = -1, so that I(n)= -n + C. The constant is evaluated by letting n=2, where we find that I(2) = pi/2.

Hence, pi/2 = -2 + C, C = 2 + pi/2

I(n) = -n + 2 + pi/2
 
  • #196


I don't think differentiating with respect to n helps... you'll get something like x^n (ln x) on top, and it's not obvious to me how you manage to simplify it to get one.

Also, the answer should always be positive, so you can't have -n there.
 
  • #197


Sigh. I am still kicking myself for differentiating wrt x and not n. Sorry for wasting everyones time.
 
  • #198


oops.. it's been a while and I completely forgot about this thread... I feel that I should provide a solution at least...

since spoiler doesn't work with latex... close your eyes if you don't want to see the answer!

let
[tex]\frac{1}{1+x^n}=\int_0^\infty e^{-(1+x^n)t}dt[/tex]

the integral becomes
[tex]\int_0^\infty\int_0^\infty e^{-(1+x^n)t} dxdt[/tex]

but, using integration by parts
[tex]\int_0^\infty e^{-x^n t}dx=\int_0^\infty tnx^n e^{-x^n t} dx=t^{-\frac{1}{n}}\Gamma \left(1+\frac{1}{n}\right)[/tex]

You might complain that t is singular at 0... but the integral converges just fine as long as t>1.

at the end of the day we get:
[tex]\int_{0}^\infty \frac{dx}{1+x^n}=\Gamma\left( 1-\frac{1}{n}\right)\Gamma\left(1+\frac{1}{n}\right)[/tex]
neat, heh?

You could simplify this to
[tex]\frac{\pi}{n \sin(\pi/n)}[/tex]

In fact... you could evaluate this integral using a wedge in the complex plane and get directly the sin result.
 
  • #199


Tim hasn't given a problem and it's been a long time so I'll revive it.

Given that
[itex]
\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}
[/itex]
find (for t>0)
[itex]
\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx
[/itex]
 
  • #200


Okay new to this, and with my luck probably wrong but...

inside the integral we have exp[-tx^2] = exp[t]exp[-x^2]

We can then pull exp[t] out of the integral and evaluate the integral

Finally we take the derivative and multiply the two together getting sqrt(pi)*exp[t]
 
  • #201


I will have a guess and I think it goes something like this...

We start with
[tex]
\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}
[/tex]

We consider
[tex]
\int_{- \infty}^{\infty}{e^{-tx^2}} dx
= \int_{- \infty}^{\infty}{e^{-u^2}} \frac{d(t^{-0.5}u)}{du}du
= \int_{- \infty}^{\infty}{e^{-u^2}} t^{-0.5} du
= t^{-0.5} \sqrt{\pi}
[/tex]

This leads to
[tex]
\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx
= \frac{d}{dt} t^{-0.5} \sqrt{\pi}
= \frac{-\sqrt{\pi}}{2} t^{-\frac{3}{2}}
[/tex]
 
  • #202


Here's a problem:

You find yourself in the middle of a forest, with no idea how you got there. You find a note on a nearby tree that says the edge of the forest is 1 mile away. Of course, you have no idea what direction it's in. Assuming you know the forest is a half-plane (ie, from above, it looks like the set of points {(x,y) | y>0}), what path should you take to minimize the distance you need to travel to find the edge?

(Specifically, what path minimizes the distance traveled in the worst case scenario. It might also be interesting to find the path that minimizes the expected distance, although this sounds harder).

Hint:
You can do better than the obvious path of length 2pi + 1.
 
  • #203


Go 1 mile in any direction, and then go along the circle with 1 mile radius about the origin for 270 degrees, then instead of walking along the remaining 90 degrees of the circle, depart from the circle and walk 1 mile along the tangent of it. Not sure if this is optimal in worst case, but certainly is the best I can come up so far.
Haven't try to solve the expected distance version though.
 
  • #204


You can do slightly better than that. Go in a straight line for sqrt(2) miles in, let's say, the northwest direction, then travel south to the west edge of the 1 mile radius circle surrounding your starting point, walk along the southern half of the circle, and then go a mile north, so that you finish sqrt(2) miles northeast of where you started.

I haven't been able to prove this is optimal yet, or tried to work out the expected distance version, so those are still things someone could try.
 
  • #205


ThirstyDog said:
I will have a guess and I think it goes something like this...

We start with
[tex]
\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}
[/tex]

We consider
[tex]
\int_{- \infty}^{\infty}{e^{-tx^2}} dx
= \int_{- \infty}^{\infty}{e^{-u^2}} \frac{d(t^{-0.5}u)}{du}du
= \int_{- \infty}^{\infty}{e^{-u^2}} t^{-0.5} du
= t^{-0.5} \sqrt{\pi}
[/tex]

This leads to
[tex]
\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx
= \frac{d}{dt} t^{-0.5} \sqrt{\pi}
= \frac{-\sqrt{\pi}}{2} t^{-\frac{3}{2}}
[/tex]

This is correct.
There is another way to do this with dimensional analysis which I found in some MIT lecture notes. Say that x have some dimension D. The exponent needs to be dimensionless to make sense, so t must have the dimension [tex]1/D^2[/tex]. And dx has the same dimension as x, so the result which contains t must have dimension D. [tex]1/\sqrt{t}[/tex] has dimension D, so we can say that

[tex]\int_{- \infty}^{\infty}{e^{-tx^2}} dx = \sqrt{\frac{\pi}{t}}[/tex]

Ignea_unda said:
Okay new to this, and with my luck probably wrong but...

inside the integral we have exp[-tx^2] = exp[t]exp[-x^2]

We can then pull exp[t] out of the integral and evaluate the integral

Finally we take the derivative and multiply the two together getting sqrt(pi)*exp[t]

Recall that [tex]e^t e^{-x^2} = e^{-x^2+t} \not= e^{-tx^2}[/tex]
 
Last edited:
  • #206


Here is a good question if someone wants a go:

A space-ship of (constant) mass M starts from rest in a zero gravity vacuum. It has a rocket that provides a constant force of F Newtons in any direction it wants. The space-ship's aim is to travel in a perfect circle of radius R from rest by using its rocket.

Find the direction (angle, theta) that the rocket should fire in terms of T for time, R, M, and F.
 
  • #207


Mathemagician
 
  • #208


StatusX said:
Here's a problem:

You find yourself in the middle of a forest, with no idea how you got there. You find a note on a nearby tree that says the edge of the forest is 1 mile away. Of course, you have no idea what direction it's in. Assuming you know the forest is a half-plane (ie, from above, it looks like the set of points {(x,y) | y>0}), what path should you take to minimize the distance you need to travel to find the edge?

(Specifically, what path minimizes the distance traveled in the worst case scenario. It might also be interesting to find the path that minimizes the expected distance, although this sounds harder).

Hint:
You can do better than the obvious path of length 2pi + 1.

edit: nm
 
  • #209


The answer is 1 mile. Because you are in the middle so going out can be anywhere so it is 1 mile from the middle.
 
  • #210


maze said:
edit: nm

The answer is 1 mile. Because you are in the middle so 1 mile to the end.
 
<h2>1. How do we make 100! divisible by 12<sup>49</sup>?</h2><p>To make 100! divisible by 12<sup>49</sup>, we need to find the highest power of 12 that is a factor of 100!. This can be found by dividing 100 by 12, which gives us 8. This means that 12<sup>8</sup> is the highest power of 12 that is a factor of 100!. To make it divisible by 12<sup>49</sup>, we need to multiply 12<sup>41</sup> to 100!.</p><h2>2. Can we make 100! divisible by 12<sup>49</sup> without changing its value?</h2><p>Yes, we can make 100! divisible by 12<sup>49</sup> without changing its value by multiplying it with 12<sup>41</sup>. This ensures that the value of 100! remains the same, but it becomes divisible by 12<sup>49</sup>.</p><h2>3. Why is it important to make 100! divisible by 12<sup>49</sup>?</h2><p>Making 100! divisible by 12<sup>49</sup> is important because it allows us to easily perform calculations involving large numbers. By making it divisible by 12<sup>49</sup>, we can break down the calculation into smaller, more manageable parts.</p><h2>4. What is the significance of 12<sup>49</sup> in this context?</h2><p>12<sup>49</sup> is the highest power of 12 that is a factor of 100!. This means that it is the smallest number that can divide 100! without leaving a remainder. It is significant because it allows us to make 100! divisible by a large number, making calculations easier.</p><h2>5. Is there a general rule for making a factorial divisible by a large number?</h2><p>Yes, there is a general rule for making a factorial divisible by a large number. We need to find the highest power of the number that is a factor of the factorial, and then multiply it to the factorial. This will ensure that the factorial is divisible by the large number without changing its value.</p>

1. How do we make 100! divisible by 1249?

To make 100! divisible by 1249, we need to find the highest power of 12 that is a factor of 100!. This can be found by dividing 100 by 12, which gives us 8. This means that 128 is the highest power of 12 that is a factor of 100!. To make it divisible by 1249, we need to multiply 1241 to 100!.

2. Can we make 100! divisible by 1249 without changing its value?

Yes, we can make 100! divisible by 1249 without changing its value by multiplying it with 1241. This ensures that the value of 100! remains the same, but it becomes divisible by 1249.

3. Why is it important to make 100! divisible by 1249?

Making 100! divisible by 1249 is important because it allows us to easily perform calculations involving large numbers. By making it divisible by 1249, we can break down the calculation into smaller, more manageable parts.

4. What is the significance of 1249 in this context?

1249 is the highest power of 12 that is a factor of 100!. This means that it is the smallest number that can divide 100! without leaving a remainder. It is significant because it allows us to make 100! divisible by a large number, making calculations easier.

5. Is there a general rule for making a factorial divisible by a large number?

Yes, there is a general rule for making a factorial divisible by a large number. We need to find the highest power of the number that is a factor of the factorial, and then multiply it to the factorial. This will ensure that the factorial is divisible by the large number without changing its value.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
2
Replies
53
Views
5K
Replies
6
Views
971
  • STEM Educators and Teaching
Replies
3
Views
1K
  • General Math
Replies
30
Views
3K
  • Math Proof Training and Practice
3
Replies
93
Views
6K
  • Sci-Fi Writing and World Building
3
Replies
87
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
  • STEM Academic Advising
Replies
11
Views
1K
Back
Top