/sci/ - Science & Math

reported for homework

Fortunately, they showed us how <span class="math">I[/spoiler] is represented in that parenthesis-heavy matrix notation. We infer that
<div class="math">
A = {3\: \: 2\choose 4\: \: 2}.
</div>

>>4379578
Never gets old. Never.

>>4379653
Just diagonalize the matrix.

>>4379653
huh?

You could easily diagonalize <span class="math">A[/spoiler] to ease raising tho the <span class="math">n[/spoiler]th power. But I suspect that's not the best approach.

>>4379658
Nah, I tried that, and the diagonalisation (and the general expression of the nth power) is awful, with square roots of ugly stuff everywhere. There must be something better, indeed. The "minus I" makes me think "characteristic polynomial", but honestly I don't really see how to exploit that either.

Easy proof by induction that <span class="math">A^n[/spoiler] has the form <div class="math">A^n= {a_n\ \ b_n \choose 2b_n\ \;a_n }.</div> That's gotta be worth something.

eigenvalues 5/2 +/- sqrt (33)/2
eignvectors ( 1 +/- sqrt(33) , 4 )

it is easy to show that when we decompose vectors ( 3 , 2 ) and ( 4 , 2 ) into linear combinations of the eigenvectors, they share a GCD greater than one for some A^n.

Since the process then repeats to infinity, the GCD is infinite.

>>4379692
Oh look, the tripfags knows how to google solutions.

>>4379692
Don't you mean <div class="math">A^n= {a_n\ \ b_n \choose 2b_n\ \;c_n }.
</div>

>>4379692
The bottom right one should be <span class="math">b_n[/spoiler] I guess.

>>4379697
>>4379695
Oh yeah, indeed, not <span class="math">b_n[/spoiler].

>>4379692
Forget this. I thought the (2,2) entry was a three. I could have sworn it was — I checked out this problem a few days ago.

The period of a pendulum depends only on its length only for very small oscillations. For large oscillations the period depends on the amplitude. Such amplitude dependence can be eliminated by making the string of the pendulum (shown in red) to wrap around a limiting curve (shown in black). What is the shape of this curve?

>>4379726
cycloid

>>4379718
It should be a three:
http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/1994.pdf


I haven't worked on it any more than the observation in >>4379692
I'm guessing we can solve this one in no time.

>>4379694
I would have nothing to gain. But I realize that hasn't stopped others, so you're free to suspect it.

>>4379735
We all know that you are TN5 with another trip. Please stop shitting up the putnam threads.

>>4379742
TN5 is the moderator who posts these threads. If she/he is in here: you should change the (2,2) entry to a 3 in the original post.

>>4379756
I seriously hope he is not the moderator. He is a terrible person.

>>4379756
No I'm not the moderator, and I only posted like two of these threads when nobody else posted them. But anyway, that guy didn't notice you were here before you got a trip, it seems. See http://archive.installgentoo.net/sci/thread/S4337992 and previous uses of "Yo, I got this one" in the archives.

>>4379766
>that feel when Blackman was banned

>>4379761
I would rather think that people just hate tripfags randomly. I posted in the last 3 putnam threads anonymously and didn't get the same hate. Now that I know that, I'll probably go back to tripfagging, since I can fairly assume I'm not really being the dick people tell me I am (which I would otherwise try to fix, since I do take criticism into account).

>>4379766
Sorry, I got the wrong impression.

>>4379766
How do you know it was him? Oh right, because you are the same person.

>>4379793
Beeeeeecause he first shared the same name and then the same tripcode, and all the time the same capabilities at problem solving?

>>4379798
>capabilities at problem solving

Fixed:
>Looking up the solution in google and then spamming the thread with latex to pretend you are working it out right now

Just stop it and don't ruin the thread. Some people want to have fun with the putnam problems.

>>4379798
That's wrong though, TN5

Just admit you are a fat scottish neckbeard with MPD

Not sure if this works.

Lemma 1:
<span class="math">A^n[/spoiler] always has the form <div class="math">{o\: \: e\choose e\: \: o}</div>, where o represents an odd number and e represents an even number.

Proof:
Induct on n. n=1 is trivial. If it's true for n=k, then <div class="math">A^{k+1} = A^k*A = {o\: \: e\choose e\: \: o}*{3\: \: 2\choose 4\: \: 3} = {3o+4e\: \: 2o+3e\choose 3e+4o\: \: 2e+3o} = {o\: \: e\choose e\: \: o}</div>

Now we're going to show that <span class="math">d_{2n} \geq 2d_n[/spoiler]. <div class="math">A^{2n}-I = (A^n-I)(A^n+I) = d_n\left(\frac{A^n-I}{d_n}\right)\left[{o\: \: e\choose e\: \: o} + {1\: \: 0\choose 0\: \: 1}\right] = d_n\left(\frac{A^n-I}{d_n}\right){e\: \: e\choose e\: \: e} = 2d_n M</div> where M is a matrix of integers. If X is a matrix, let <span class="math">f(X)[/spoiler] be the GCD of the entries of X. Then, <div class="math">d_{2n} = f(A^{2n}-I) = f(2d_n M) = 2d_n f(M) \geq 2d_n</div>

Thus <span class="math">d_{2n} \geq 2d_n[/spoiler] and <span class="math">d_n[/spoiler] grows without bound as <span class="math">n \rightarrow \infty[/spoiler]

>>4379896
That looks good to me.

>>4379896
That's very nice! But it doesn't completely prove the statement. For example, it doesn't show that <span class="math">d_{2n+1}\to\infty[/spoiler] as <span class="math">n\to\infty[/spoiler].

>>4379816
I assume you're trolling.
But if not, I'd be interested to see where you can find the solution I gave to the problem that TN5 linked to in >>4379766 .

It's true, I did look ahead in the MAA Putnam archive a few days ago. (Hey, I couldn't help it! I've got Putnam Fever.) But if I ever solve a problem beforehand, I wouldn't bother posting a solution — at least not before others do. To do so would pointlessly ruin the thread for everyone else.

Anyway, the MAA Putnam archive doesn't have solutions before 1995. But I'm guessing that starting in three days, these threads might get ruined a lot more frequently.

>>4379911
Oh I see. I just showed that for any N there exists an n such that <span class="math">d_n > N[/spoiler], but it should be that for any N there exists an n such that <span class="math">d_k > N[/spoiler] for all <span class="math">k\geq n[/spoiler].

back to the drawing board

>>4379935
But you only need something far weaker now. Like proving that <span class="math">(d_n)_n[/spoiler] is non-decreasing.

>>4379937
I'm not so sure, because it could still conceivably be the case that the sequence <span class="math">d_{2n+1}[/spoiler] is constant.

>>4379948
No. It could be that the sequence <span class="math">(d_n)_n[/spoiler] is not non-decreasing, by <span class="math">(d_{2n+1})_n[/spoiler] goes to infinity as a subsequence of <span class="math">(d_n)_n[/spoiler], so it cannot be constant. My point was not really that <span class="math">(d_n)_n[/spoiler] is not non-decreasing, though, but that using that other anon's proof, it is probably possible to find a lemma that gives the solution much more quickly than starting over from scratch.

>>4379977
>by (d_{2n+1})_n goes to infinity
>by
Should be "but". Sorry about that.

>>4379977
Doh, I really don't know what I was thinking in >>4379948 . You're of course right: showing <span class="math">(d_n)[/spoiler] is nondecreasing is sufficient. But I have a hunch that won't be much easier to prove.

>>4379989
I don't know... His proof was beautiful enough to make me think it's a necessary step. But that might be the emotional part of my mind talking.

>>4379989
Wait, hold on. It's immediately true!

>>4379995
I certainly hope not, I'd feel dumb, I've been trying to prove it since you posted >>4379911.

>>4379995 <span class="math">[/spoiler]
If <span class="math">a_n = d_n\alpha_n[/spoiler] and <span class="math">b_n = d_n\beta_n[/spoiler] then

<span class="math">a_{n+1} = 3a_n + 4b_n = d_n(3\alpha_n + 4\beta_n)[/spoiler], and
<span class="math">b_{n+1} = 2a_n + 3b_n = d_n(2\alpha_n + 3\beta_n).[/spoiler]

So <span class="math">d_n|d_{n+1}[/spoiler], which implies <span class="math">d_n\leq d_{n+1}[/spoiler]

>>4380004
Oh, fuck. nevermind. I forgot about subtracting 1 from <span class="math">a_n[/spoiler]. duh.

>>4380009
Which is why anon's proof for <span class="math">d_{2n}[/spoiler] was so cool. The <span class="math">A^{2n}-I=(A^n-I)(A^n+I)[/spoiler] is an awesome way to be able to do a recursion not on the <span class="math">A^n[/spoiler], but on the
<span class="math">A^n-I[/spoiler] itself.

>>4379896 here

>>4380020
Thanks, I think it's pretty neat too.

I've been trying to work with <span class="math">A^n-I[/spoiler] instead of <span class="math">A^n[/spoiler] but I'm not really getting anywhere. All I've really managed to say is that if <span class="math">B_n = A^n-I[/spoiler], then <div class="math">B_{x+y} = B_xB_y + B_x + B_y</div>, but that's pretty trivial.

I also managed to find explicit forms for <span class="math">a_n[/spoiler] and <span class="math">b_n[/spoiler] but they're ugly and probably not going to help at all.

It's no coincidence that <span class="math">A^n-I[/spoiler] is factorable, but I can't seem to do anything with it. This is difficult.

Fuck. I always sucked at maths back in high school because I never cared about it, but this shit looks pretty fucking interesting.

Too bad it's all hieroglyphs for me.

>>4380891
A^n always has odd along the diagonal, so it's always divisible by 2.
A^(2^n) - I has GCD of the GCD of A^(2^(n-1)) - I times the GCD of A^(2^(n-1)) + I - just factor out the GCDs and multiply, then multiply it back in, for proof.
But GCD A^(2^(n-1)) + I is divisible by 2, and GCD of A^(2^(n-1)) is divisible by 2^(n-1) by inductive hypothesis which I didn't actually state before, so GCD A^(2^n) is divisible by 2^n

>>4381669
That's what >>4379896 does and what >>4379911 criticizes :)

>>4381681
Yup, don't mind me. I'm thinking, just like the rest of the thread.

>>4381685
I just wanted to hook you up on the few posts that discussed what to do afterward.

>>4381688
I still got nothing.

>>4381827
Yeah I've also eventually given up.

TN5, please stop posting.

Fuck, we didn't solve it today.

Does anyone have a solution? I'd really like to know how this is done.

The books solution is quite nice and simple.

This is all you need to know about maths:

http://www.feandft.com/18%20Sacred%20Geometry.htm

>>4379896

just a minor techical point, you need a positive d_1, because you're essentially asserting that its quotient by 2 is the identity, but since the gcd of the identity is 0, the gcd stays at 0.

>>4382830
darn, why didn't we think of using the determinant.

>>4383726
>>4379673 here.
With the 32,42 matrix instead of the 32,43, it didn't give such a good result, which is maybe why no one tried using it. Also I did think about it shortly because of the A^n-I, which looked like the characteristic polynomials det(A^n-lambda*I) taken in 1, but it didn't lead anywhere (and that's not the fault of the 2 instead of a 3).