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

[Gokul43201]

A Q&A game is simple: One person asks a relevant question (it can be research, calculation, a curiosity, something off-the-top-of-the-head, anything ... as long as it's a math question) and other people try to answer. The person who posts the first correct answer (as recognized by s/he who asked the question) gets to ask the next question, and so on.

Let me start this off with a simple number theory problem :

What is the least number than must be multiplied to 100! (that's a factorial) to make it divisible by 12^{49} ?

(throw in a brief -couple of lines or so- explanation with the answer)

 

[JonF]

1/(99!*50)

 

[Gokul43201]

Not correct. "Multiplying" by your number gives a "product" of 2 (=100!/50*99!), and 2 is not divisible by 12^{49}.

 

[JonF]

i think i read it backwards...

 

[matt grime]

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

 

[Gokul43201]

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

I'm not sure I follow the finish...

You've shown that 100! has 2^{97} * 3^{48}. And what happened after that ?

In any case : Next question is yours ...

 

[matt grime]

Duh, do i feel stupid from typing too quickly whilst someone is talking to me. should have been 6.

Willl think of a question later tonight.

 

[matt grime]

Ok, here's one that I hope isn't too tricky.

Let A be an nxn matrix over C, the complexes.

Suppose that Tr(A^r)=0 for all r. Show A is nilpotent.

All the other ones I could think of were too easily looked up.

 

[CRGreathouse]

Quick explanation

I'm not sure I follow the finish...

You've shown that 100! has 2^{97} * 3^{48}. And what happened after that ?

12^{49}=2^{98}3^{49}, so 100!=2^{97}3^{48}X must be multiplied by 6=2^{98-97}3^{49-48} before 12^{49} will divide it.

 

[Gokul43201]

Yes, CRG : matt clarified this in his subsequent post. Thanks !

Back to matt's question :

Let A be an nxn matrix over C, the complexes.

Suppose that Tr(A^r)=0 for all r. Show A is nilpotent.

 

[matt grime]

If there's no progress on this after a couple of days i'll post hints. perhaps people should post what they think they need to do. i like tyhe question cos it uses lots of bits from here there and everywhere.

 

[snoble]

Well it seems that first you need to show that such a matrix does not have n distinct eigenvectors and then show that not having n distinct eigenvectors implies nilpotents.

The first question relates to the fact that if a matrix had a full set of Eigenvectors then diagonalization gives us that \sum \lambda_i^n =0 for all n>0.

For the second half I would gather you need to consider the vectors not in the span of the Eigenvectors and consider where they may be mapped.

hmmm... that may not be enough for the first half. You may need to also show that any vector that is a eigenvector is in fact in the kernel.

Experimentally it appears like we are dealing with upper or lower triangular matrix if you just assume Tr(A^r) =0 for r=1..n. But that could just be maple not returning all possible answers which it sometimes does.

That's what I've been thinking

 

[Hurkyl]

Hrm.

If a matrix A is diagonalizable, then I claim that there exists an n such that all of the nonzero eigenvalues of Aⁿ lie in the right half-plane. The requirement that Tr(Aⁿ) = 0, forces all the eigenvalues to be 0, and thus A is zero... clearly nilpotent!

So the trick, then, is when the matrix is not diagonalizable.


Then again, this only works for complex valued matrices.

 

[matt grime]

I did state the matrix was over C, though this is largely for conveniece.

And, snobel, the matrix 0 has a full set of eigen values and is certainly nilpotent an satisfies the criterion.

 

[snoble]

Oops... of course that is the sole matrix with a full set of 0 eigenvalues and \lambda_i=0 is the sole set of solutions in C satisfying my condition.

 

[uart]

What is the least number than must be multiplied to 100! (that's a factorial) to make it divisible by 12^{49} ?

Sorry but the correct answer is the rational number 12^49 / 100! , it's smaller than the previous answer of 6 by a factor or approx 10^104.

Ok so here's my QA puzzle : Why is it that mathematicians are worse than the general layperson when it comes to not specifying that they require a whole number solution when that is the case. :p

 

[matt grime]

If you're going to take that attitude, there is no answer; think negatives.

 

[shmoe]

Ok so here's my QA puzzle : Why is it that mathematicians are worse than the general layperson when it comes to not specifying that they require a whole number solution when that is the case. :p

Because a mathematician will expect the reader to see the words "divisible" and "number theory" and realize that the interesting solution lies in the whole numbers. In fact if you are throwing rationals into the mix, the concept of "divisibility" collapses into something really dull (as with any field). The overlying assumption we're interested in whole numbers here is just like when you saw "least number" you assumed it had to be positive, 0 works fine and is smaller than yours, so is -6, etc.

 

[uart]

just like when you saw "least number" you assumed it had to be positive.

Actually I didn't assume that it had to be positive but I could see that there was no solution if negatives were included so I took the liberty of further constraining the under-specified problem so that it did have a solution.

Anyway don't take that last post too seriously, it was a wind-up and I did really know that he meant positive integer. :)

 

[snoble]

Grimey I see it now.

The trick isn't to diagonalize the matrix the trick is to write it out in the form A=PUP^{-1} where U is upper triangular (I'll post how you know you can do this later). Then the Trace of A^r is just the trace of U^r since A is just a conjugate of U. And of course the trace of U^r=0 is the same as \sum_i d_i^r=0 where d_i are the diagonal elements. Then Hurkyl had the right idea when he said you could find an r such that d_i^r has positive real part. In fact what you can say is that given any finite set of non-zero complex numbers and any \epsilon>0 there exists a positive integer r such |Arg(d_i^r)| < \epsilon. This is either an analysis statement or a number theory statement depending on your interpretation. So U is upper triangular and has a 0 diagonal. There fore A^{n-1}=PU^{n-1}P^{-1}=P0P^{-1}=0 where A is nxn.

So two big statements still to be proven if anybody wants to do them (upper triangulation and |Arg(d_i^r)| < \epsilon or I will write them up when I'm not supposed to be busy working on something else.

How about a new problem.

Lets call a subset A of [0,1] paired if 0,1\in A and for every pair a,b \in A such that a<b and b-a \ne 1 there exists another pair c,d \in A such that c<d and c\ne a and d-c= b-a. Sounds very complicated but all it says is if a set is paired then every distance between points, except 1, occurs twice. An example of a paired set is {0,1/5, 2/5, 4/5, 1}. Notice that the difference 1/5 appears 3 times, 2/5 appears twice and 3/5 appears twice but the difference 1 appears only once.<br /> <br /> Alright, here's the question. Are there any finite (only contains finitely many elements) paired sets such that there exists an irrational number in the set. Give an example or prove why not.<br /> <br /> I will be really impressed if you use Euclidian Geometry.<br /> <br /> Regards,<br /> Steven

 

[matt grime]

Firstly, you do not need to "prove " it can be put in upper triangular form, this is Jrodan Canonical form.

Whilst you ceratinly have the right idea, please note GOkul's rule that you must wait for me to say if it is correct before posting a new question. I would like to see you, or anyone else, prove that if d_1,..,d_n is a set of complex numbers such that the sum of all the r'th powers is zero for all r, then all the d_i are zero. Please note this statement is true in any field, not just C. The reason I would like to see it is that I think its proof (or at least the one in my mind) is nice, not because I think it is hard. FOr a hint think Newton.

 

[snoble]

hmm... I can't do it for a field in general but I can do it for the comlex numbers by induction.

I will prove that given a finite set d_1, d_2, ...,d_n of non-zero complex numbers and \epsilon>0 then there exists a positive integer r such that |Arg(d_i^r)| <\epsilon

Base case
Start with d_1 \ne 0 and \epsilon>0. Then take N>0 such that 2\pi/N < \epsilon. Let c_r = Arg(d_1^r). So there exists an i,j such that 1 \le i < j \le N and dist(c_i, c_j) < \epsilon (note that the distance function I am using is distance between angles on the unit circle so dist(3\pi /4, -3\pi /4) = \pi/2) This is easy to see since there are N angles that can be reordered such that c_{\sigma (1)}\le c_{\sigma(2)}\le ...\le c_{\sigma(N)} so dist(c_{\sigma (1)}, c_{\sigma(2)}) + dist(c_{\sigma (2)}, c_{\sigma(3)}) + \ldots + dist(c_{\sigma (N-1)}, c_{\sigma(N)})+ dist (c_{\sigma (N)}, c_{\sigma(1)}) \le 2\pi so since dist is positive there exists dist(c_{\sigma(k)}, c_{\sigma(k+1)}) \le 2\pi/N < \epsilon.

So since dist(c_i, c_j) <\epsilon then dist(c_{i-1}, c_{j-1}) <\epsilon then dist(c_{1}, c_{j-i+1}) < \epsilon then dist(0, c_{j-i}) < \epsilon. So r=j-i.

Inductive step is straight forward. Given d_1,\ldots, d_{n+1} \ne 0 and \epsilon >0, 1/N < \epsilon take r' such that |Arg(d_i^{r'})| < \epsilon/N for 1 \le i \le n. Then as in BaseCase there exists an r, 1\le r\le N such that |Arg( (d_{n+1}^{r'})^r)| < \epsilon and ofcourse |Arg(d_i^{r'\cdot r})| < r\cdot\epsilon/N <\epsilon

So with the above in mind and given a finite set of complex numbers none equal to zero. Take r |Arg(d_i^r)| < \pi/2. So Re(d_i^r) >0 so Re(\sum d_i^r) >0. Which contradicts \sum d_i^r =0. There fore if \sum d_i^r =0 for all r then d_1=d_2=\ldots =d_n=0

I am curious about how to do this for a general field though. Sorry about jumping the gun posting my question but I really happen to like that question since it doesn't necessarily use the math you expect it would.

 

[matt grime]

You certainly get to ask that as the next question, and I won't post the answer to it, but I'd like to get this one cleared up.

 

[snoble]

Hmm... does the general solution have something to do with taking a field F and n dimensional vector space F^n over F. Then taking the linear functional g: F^n -> F st
g(f1,f2,...,fn) = f1+f2+...+fn. Concluding that the kernel of g must be at most n. But if a1^k + a2^k +... +an^k =0 for all k>1 then (a1^i, a2^i,..., an^i) is orthogonal to (a1^j,...,an^j) using the standard dot product. So either (a1^k,...,an^k) for k from 1 to n is a spanning set or one of the vectors is a 0 vector. If it were a spanning set then the whole space is in the kernel so 1+0+0+...+0 =0 which doesn't make sense. So ai^k =0 for all i. But then ai=0 because a field is a domain.

Can you do that? Can you always use the standard dot product to show orthogonality to show that the set is a spanning set? I think I may have to assume the conclusion to be able to do that.

Man I've got to stop thinking about this and get back to work.

 

[matt grime]

That isn't what I'd've done, and I'm not sure it'dve worked in anything other than char 0.

The hint to think about what Newton and polynomial might yield has been ignored, so far.

 

[snoble]

sigh... clearly mine doesn't work once if I put a little thought into it. [1,-1,i,-i] would be self orthogonal under the standard real dot product which doesn't make sense.

 

[snoble]

When you mentioned characteristic 0 did you mean that my method wouldn't work in non-characteristic 0 (evidently it doesn't even work in characteristic 0) or that the theorem as a whole doesn't hold in non-characteristic 0 fields. Because I don't think it does.

 

[matt grime]

I meant that your inner product idea deosn't hold since the vector (1,1) dots with itselt fo give 0 in char 2. And now I think abouit it the char of the field does need to be restricted: it cannot divide the numbre n if d_1,..,d_n are the diagonal elements of the matrix.

Right, This is getting far too long and complicated.
I think we need an extra rule: no "working through the problem in thie thread". INstead for each new problem a new unsticky thread ought to be started for people ti discuss things in if they so wish.


The answer is: the functions

d_1^r + \ldots +d_n^r

for r = 0 to n is a generating set of the fixed point space of the ring k[d_1,..,d_n] under the action of S_n permuting the subscripts (Newton's identities).

Or they span the symmetirc polynomiials.

Thus if they all (except the zeroeth powers) evaluate to 0 at some point, then alll symmetric polynomials do (except the constants). In particular, the poly d_1d_2..d_n the product of all of the d_i's. Since this is over a field, it follows that wlog d_1 is 0 and the result follows by induction (this fails if the char of the field divides n, eg n=2, 0=x+y=(x+y)^2 = x^2+2xy+y^2=2xy, so fails in char 2)


Now, snoble, you had the right idea, so could you repost you problem. And suggested answers only in the thread, eh?

 

[snoble]

Lets call a subset A of [0,1] paired if 0,1\in A and for every pair a,b \in A such that a<b and b-a \ne 1 there exists another pair c,d \in A such that c<d and c\ne a and d-c= b-a. Sounds very complicated but all it says is if a set is paired then every distance between points, except 1, occurs twice. An example of a paired set is {0,1/5, 2/5, 4/5, 1}. Notice that the difference 1/5 appears 3 times, 2/5 appears twice and 3/5 appears twice but the difference 1 appears only once.

Alright, here's the question. Are there any finite (only contains finitely many elements) paired sets such that there exists an irrational number in the set. Give an example or prove why not.

Steven
p.s. I will post hints only when asked

p.p.s. Your answer needs a little bit of a repair matt. You are actually looking at the subring of the fixed point space that maps (0,0,...,0) to 0. Since you don't have that \sum d_i^0 =0. Just in case you ever plan on giving this out on an assignment.

 

[Gokul43201]

Reposting the standing question (from snoble, above) for clarity :

Lets call a subset A of [0,1] paired if 0,1\in A and for every pair a,b \in A such that a<b and b-a \ne 1 there exists another pair c,d \in A such that c<d and c\ne a and d-c= b-a.

Are there any finite (only contains finitely many elements) paired sets such that there exists an irrational number in the set. Give an example or prove why not.



Open to all enthusiasts !

People that recently asked a question are requested to give others a little time (say, a day or two) before jumping in themselves.

 

[The Bob]

Are there any finite (only contains finitely many elements) paired sets such that there exists an irrational number in the set. Give an example or prove why not.

If I understood what you meant I might give it a go. Call me stupid but it makes no sense to me.

The Bob (2004 ©)

 

[Moo Of Doom]

If I understood what you meant I might give it a go. Call me stupid but it makes no sense to me.

The Bob (2004 ©)

He means that if there is a finite set, A, in [0,1] so that 0 and 1 are in A, and the difference between any two members of A, excluding the difference between 0 and 1, occurs with two different pairs of numbers in the set. So if you have two members of the set that are 2/7 apart, you need another pair that is 2/7 apart (Though this can share one of the members of the other pair, I think).

Can you construct a finite set of that kind, so that it includes an irrational number?

(My guess is no, but I'm a long way from proving it.)

 

[uart]

(My guess is no, but I'm a long way from proving it.)

That was definitely my impression too Moo. Put it this way, if there does exist a finite example of such a set (that includes an irrational) then I'd be very interested to see it.

 

[snoble]

That's the question alright. An example of a paired set is {0,1/5,2/5,4/5,1}. Yes, two pairs can share a member; this example requires that since 2/5=4/5-2/5=2/5 -0. So to reiterate can you find a paired set that is both finite and contains an irrational. Or show why one can't exist.

 

[eNathan]

Here is a new question.

Why is the answer to life the universe, and everything = 42? How was this derived?

:rofl"

 

[CRGreathouse]

Here is a new question.

Why is the answer to life the universe, and everything = 42? How was this derived?

:rofl"

"What is six multiplied by nine"?

...at least according to Douglas Adams.[/size]

 

[eNathan]

"What is six multiplied by nine"?

...at least according to Douglas Adams.[/size]

Ye, I read something of that sort. But why 6 and why 9? Why not 6+9? Why not \frac {6} {9}

 

[matt grime]

Please, can we get back on topic and not ruin Gokul's admirable idea with asinine comments.

 

[snoble]

Thanks matt,
I'll post a hint if anyone's interested. The problem is a bit out of the range of most high school math students but anyone with a bit of university experience has the tools to solve it. I hope nobody is scared off by it.

Steven

 

[Gokul43201]

yes please...some big hints.

 

[snoble]

The first of the big hints. This is a linear algebra problem but the vector space you want isn't over the reals. Think about what would be a useful basis and what would be in the span of that basis.

 

[snoble]

Does anybody want to post any work in progress or thoughts of a solution? That way at least a next questioner can be chosen. I apologize if I bogged this game down with a poor question . I still have feel someone out there can solve it. I solved it as a junior undergraduate and I wasn't that amazing of a junior undergrad.

 

[mansi]

Let’s say you have an irrational x in A which is a paired set. You’re sure of 0,x and 1 being in the set. Now, obviously x-0 != 1-x .So there must be at least one additional point in the set (or two points p,q distinct from x such that p-q=x-0) .Now this point is irrational( in the other case, at least one of p & q is irrational). If we go on this way…we get infinitely many irrationals in the set. That , I guess ,amounts to saying that a paired set containing an irrational point contains infinitely many irrationals.
All of this seems too simple to be correct….and what’s infinitely worse is that I don’t see any use of the hint given by snoble...and lastly, why are the biggies like matt and gokul not coming up with smart ideas,like they always do?
i guess the odds aren't in my favour...THERE HAS TO BE SOMETHING WRONG IN THIS!

 

[matt grime]

I guessed the first and thus set the last one; I haven't even bothered to think about this one really, other than to clarfiy something with the setter.

 

[snoble]

mansi you are on the right line of thought but as always the devil is in the details. If you can formalize "If we go on this way" you've basically proven it. Try even just take it to the next stage... why can't there be only two irrationals in a paired set... why can't there be only n irrationals.

 

[mansi]

i'm writing down the proof...i'm onto it ,head on...
but there's something i'd like to clarify...
in a paired set ,is it possible to have 3 pairs of elements having the same distance between them...or do we consider it to be exactly two pairs?

 

[snoble]

3 of the same distance is totally cool. That's why {0,1/5,2/5,4/5,1} is a paired set even though 1/5 shows up 3 times.

 

[mansi]

Ok…so I think I’ve got something (not a proof) here…
Let A be a paired set containing an irrational point, say x. 0,x,1 belong to A and x-0 != 1-x, so there exists at least one additional point which is irrational or two points,at least one of which is irrational.
In the first case, say , the irrational point is p. so you have 0,x,p,1 belonging to A. p –x !=p-0 and p-x !=1-x. The only possibility is that p-x =1-p and p-0=1-x but that contradicts the fact that x is irrational. Therefore, there exists at least one more irrational point in the set….and so on.
In the second case , say you’ve 2 points p and q and WLOG p is irrational.
i.e. we have x-0= p-q .
If q is rational…and if q=1/2 then you don’t have another rational point but taking all the possible combinations of the distances between rational and irrational , you have to have an irrational…
If q != ½ then there’s definitely another rational point z in the set. Consider the difference x-z. We need a pair of elements giving us this difference.
x- z !=p-z (contradicts the fact that z is rational) and x-z !=1-p and x-z !=p-0. Therefore , we’re sure that there’s another irrational in the set…
So , now you have 3 irrationals in the set…x,p and q(say). Consider the difference between the two irrationals q and x. Picking up all possible
Pairs, you get to know that another irrational exists in the set .
Finally,as I said earlier…existence of an irrational in a paired set implies the existence of infinitely many irrationals in the set…
I think this is more like an observation, not a proof in the typical sense…

 

[mansi]

so...am i supposed post a new question,or not??

 

[Gokul43201]

Give snoble a day or two to respond...