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

[matt grime]

naturally, it being radio 4, the first method was the one used. so ask a question (hoping to breathe life into this thread)

 

[D H]

naturally, it being radio 4, the first method was the one used. so ask a question (hoping to breathe life into this thread)

Sticking with the radio show puzzles, here's one from Car Talk.

Three different numbers are chosen at random, and one is written on each of three slips of paper. The slips are then placed face down on the table. The objective is to choose the slip upon which is written the largest number.

Here are the rules: You can turn over any slip of paper and look at the amount written on it. If for any reason you think this is the largest, you're done; you keep it. Otherwise you discard it and turn over a second slip. Again, if you think this is the one with the biggest number, you keep that one and the game is over. If you don't, you discard that one too.

The chance of getting the highest number is one in three. Or is it? Is there a strategy by which you can improve the odds?

 

[Moo Of Doom]

Turn over the first slip and remember the number. Discard it, then turn over the second slip. If the number on it is higher than the first slip, take it. It has a 2/3 chance of being the largest. If the number on the second slip is smaller than the first slip, you know it's not the largest, so you should go on to the third slip. In this case there's a 1/3 chance. (Unless, of course, you can go back to the first slip, in which case there's a 2/3 chance).
I'm more sure about the strategy than the odds though, seeing as I've never taken a probability class, and haven't bothered reading the book I got about it >.<

 

[D H]

Moo, you got it. Now it's your turn -- ask a question.

 

[Moo Of Doom]

Yarr... I totally don't have a question. I pass this round. Someone take it. >.<

 

[Moo Of Doom]

Well, that didn't work. Alright then. The next question will go to the first person to post a proof of the following:

Let $$a,b \in \mathbb{N}$$ and $$S=\{ n \in \mathbb{N}\ |\ n=ax+by$$ for some $$x,y \in \mathbb{Z} \}$$.

Prove $$\inf{(S)}=\gcd{(a,b)}$$.

(Note: in this case $$\mathbb{N}$$ does not include 0.)

 

[matt grime]

You mean min, not inf, for what it's worth. There's no need to invoke the unnecessarily opaque inf. The min exists, it is less than the gcd by... and greater because...

 

[Galileo]

It's been a while, so I`ll have a go.
Just let me know if I use something that may not be regarded as known for the purpose of solving this problem.

For given positive integers a,b we can find integers x,y such that ax+by=gcd(a,b). (This is Bézout's Identity, which follows from the Euclidian algorithm). This is also the smallest positive integer that can be expressed in this way. Thus gcd(a,b) is the minimum of S.

 

[Moo Of Doom]

matt: Yeah, I guess min would be better.

Galileo: I'd say Bézout's Identity is off-limits because it's practically what we want to prove. But I guess finding a proof of that would be no big deal... so, ehm... you got it. Post something! :)

 

[WARGREYMONKKTL]

i don't get it!

There are 50 factors of 100 divisibile by 2, 25 by 4, 12 by 8, 6 by 16, 3 by 32 1 by 64 so the power of two in 100! is 97.

similiarly there are

33 div by 3, 11 by 9, 3 by 27 and 1 by 81 making 48 times 3 divides, so i guess

2*3^50 will do

you said the thing that in the quotation.
i don't really get it
how can you get 100!=2^98*3^49?

 

[Galileo]

matt: Yeah, I guess min would be better.

Galileo: I'd say Bézout's Identity is off-limits because it's practically what we want to prove. But I guess finding a proof of that would be no big deal

Yeah, thought so, that's why I chose not to participate for a while, but I want to revive the thread a bit.
So here's a question that requires no real math knowhow.

Given any five points on a sphere. Show that some four of them must lie on a closed hemisphere.

 

[AKG]

Pick any two points and consider the great circle passing through them. This splits the sphere into two closed hemispheres (that overlap on the great circle), but there are three remaining points. By the pigeonhole principle, one of the hemispheres must contain two of these points. That hemisphere has four, since it has the two just mentioned, plus the original two used to make the great circle.

 

[Galileo]

That is, ofcourse, correct. Your turn AKG.

 

[matt grime]

you said the thing that in the quotation.
i don't really get it
how can you get 100!=2^98*3^49?

But I didn't say anything like that. Try reading it again, all of it, all the preceding posts too.

 

[WARGREYMONKKTL]

Thanks.
I Have A Question. How Can We Apply Calculus In Physics.
Can You Give Me Somelinks About It Or Else...
Thanks
Hae A Godd Day Everyone!

 

[AKG]

I don't know the answer to this one yet, but I'll post it:

Prove that if an element of a ring has at least two right inverses, it has infinitely many

Recommended steps:

If an element b of a ring has N right inverses (N > 1), then bx = 0 has N+1 solutions

If b has at least N right inverses, it has at least N+1

The following isn't a solution, it's just what I've thought of so far:

It's clear how the first hint implies the second, and how the second proves the desired result. Now this problem was from a combinatorics class, so given N right inverses, there is some way to combine them to get a number of solutions to bx = 0, and we probably need to use some combinatorial argument to count the number of such solutions.

If x, y, z are distinct right inverses, then 0, x-y, y-x, y-z, z-y, x-z, z-x are solutions to the homogeneous equation. We know that at least 0, x-y, and x-z are distinct. We are left with four things, y-x, y-z, z-y, and z-x. And none of these are zero. So if we assume that there are only 3 distinct solutions to the homogenous equation, then we get that the pigeons:

y-x, y-z, z-y, z-x

must fit into the pigeon holes

x-y, x-z

It's also clear that y-x and y-z can't go in the same hole. Likewise, z-y and z-x can't be in the same hole. Now if you put y-x in the first hole, then it contains both x-y and y-x. Hence for every a-b in that hole, b-a is in that hole. This will lead to contradictions. So you must put y-x in the second hole, and y-z in the first, giving:

{0}, {x-y, y-z}, {x-z, y-x}

and z-x, z-y yet to be placed. It's clear, by the contradictions mentioned above which arise by putting a number and it's additive inverse in the same hole, that we must get:

{0}, {x-y, y-z, z-x}, {y-x, z-y, x-z}

Does this give a contradiction? Moreover, how can this be generalized to n > 3?

 

[AKG]

Another thought I had:

If x-y = y-z = z-x, then 3(x-y) = x-y + y-z + z-x = 0. So we can conclude some things:

If c and d are distinct elements of {x, y, z}, then 0 is not equal to c-d, and d-c is not equal to c-d. Moreover, 2(c-d) = d-a, and 3(c-d) = 0.

Again, we're looking for some sort of contradiction here. We're saying that if b has 3 right inverses, we want a contradiction if there are only 3 solutions to bX = 0. If there are only 3 solutions, then it must be that:

the three distinct solutions are 0, x-y, and y-x
x-y = y-z = z-x
3(x-y) = 0

where x, y, and z are the distinct right inverses of b. We want this to give a contradiction. Moreover, we want to generalize this to the case where there are n distinct right inverses, not just n=3.

 

[vishal@physicsforums]

well if you ask for the least number(N belongs to I) i guess it should be some small( very small no.)infact -ve no.

even for comprehendible numbers ( whole nos may be) it should be zero.This is a trivially obtained solution but nevertheless should be correct?

What do you think..!

 

[BoTemp]

This seems to be a bit dead. If I knew anything about rings I'd offer my own answer, but as is I'll just post my own:

Find a general identity for sin^n x for n odd. By identity, I mean rewriting in terms of a sum of single powers of the sine and cosine harmonics (sin(nx), cos(nx).

This problem is more useful than interesting, I realize, but I'm just trying to restart the game.

 

[cliowa]

but I'm just trying to restart the game.

So am I. So I'll give you an easy one:

There is a 1-dim. rod fixed in space in horizontal position. On this rod there are point-like ants, which can move alonge the rod, i.e. in 1 dimension only.
As the rod has a fixed, finite length L, an ant may fall off the rod and end up somewhere else (that doesn't matter here). Once it has fallen off there's no way getting back.

The particular kind of ants we are considering here has the following property: It moves with a speed v (either backwards or forwards) and reverses direction if it hits another ant.

The scenario now is this: There is a certain number N (may be huge or small) of ants on the rod. At some initial point in time t0=0 they are all moving (that implies motion with a speed of v), but it is not known in which direction. They move according to the rule stated above.

These are my questions:
1) What will happen? :-)
2) Is there a point of time t1>t0, when not even one single ant is left on the rod?
3) If yes, what's the maximum time needed for this to happen? What's the minimum?
4) If no, how would one need to modify the setting (i.e. the rules of motion) to make all ants eventually fall off?

I hope you enjoy

 

[AKG]

Yes, the ants will eventually fall off. This is easy to see. The ants closest to the ends will certainly fall off, and this will continue until they all fall off. For any N, I believe the minimum amount of time is 0, and the maximum is L/v.

 

[cliowa]

...and the maximum is L/v.

That needs some explanation, right?
Best regards...Cliowa

 

[AKG]

Actually, it's wrong. With eight ants, you can get them to stay on for 3L/2v at least.

 

[StatusX]

Imagine instead of bouncing off each other, the ants just pass right through each other. If the ants are indistinguishable, there's no way to tell this scenario apart from the original one. So the best they can do is if an ant starts at one end facing the other, which will leave some ant on the rod for time L/v, as AKG originally said.

 

[Gokul43201]

Imagine instead of bouncing off each other, the ants just pass right through each other. If the ants are indistinguishable, there's no way to tell this scenario apart from the original one. So the best they can do is if an ant starts at one end facing the other, which will leave some ant on the rod for time L/v, as AKG originally said.

Neat!

 

[AKG]

Very nice, StatusX!

 

[cliowa]

Very nice, StatusX!

Yeah, that's true. It's why I like the problem. Another nice visualization (basically the same) is the following: Imagine every ant carries with it a flag with a certain color (let them all be distinguishable). Now let the ants exchange flags when they meet. The picture you would see is lots of flags just "walking" straight on, all the way along the rod until they fall off.

 

[StatusX]

Oh, I guess I'm supposed to post another question. Ok, here's one. If $p(x)=a_0 x^{16} + a_1 x^8 + a_2 x^4 +a_3$ and $a_0/16+a_1/8+a_2/4+a_3=0$, show p(x) has a real root.

 

[AKG]

Here's an inelegant solution:

Given the relation between the coefficients, we can write:

$$p(x) = a_0\left (x^{16} - \frac{1}{16}\right ) + a_1\left (x^8 - \frac{1}{8}\right ) + a_2\left (x^4 - \frac{1}{4}\right )$$

Regarding p as a function on R, if it has no real roots then it is strictly positive or strictly negative. So:

$$\mbox{sgn}(p(0)) = \mbox{sgn}(p(1)) = \mbox{sgn}\left (p\left (16^{-1/16}\right )\right ) = \mbox{sgn}\left (p\left (4^{-1/4}\right ) \right )$$

From this, we can deduce:

$$\mbox{sgn}(a_0 + 2a_1 + 4a_2) = \mbox{sgn}(a_0 + 2a_1) = \mbox{sgn}(-a_1 - 2a_2) = \mbox{sgn}(-15a_0 - 14a_1 - 12a_2)$$

If these four expressions really did have the same signs, then for any four positive numbers A, B, C, and D, we could not have:

$$A(a_0 + 2a_1 + 4a_2) + B(a_0 + 2a_1) + C(-a_1 - 2a_2) + D(-15a_0 - 14a_1 - 12a_2) = 0$$

But take (A,B,C,D) = (11,4,16,1)

 

[StatusX]

That looks correct, but I think there's a simpler way.