Putnam solutions

A place to talk about anything (that doesn't belong in the other forums).

Moderator:Æron

User avatar
norsenerd
Posts:2269
Joined:Tue Oct 14, 2003 2:42 pm
Location:Lost
Contact:

Postby norsenerd » Sun Dec 07, 2003 3:57 pm

Because it was requested I have made this thread so people can discuss the solutions to the Putnam problems. I only have solutions for the three I solved at this point in time and they're not necisaraly the most elegant solutions (or necisarly right *crosses fngures*) I see solutions on wednessday but I will refrain from positng them hoping sombody will get them. If I either feel preasured to do so or I think it's gone on for long enough I will post solutions.<br><br>Good luck and good mathing.
Llewellyn for President 2008 <br><br><img><br><img>

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Wed Dec 10, 2003 6:07 pm

Wow, fun stuff. Well, I looked at the problems a little Monday. I managed to figure one out, and have printed up the rest for later. Please don't give the answers until next Monday, at least! I'd like to answer them myself.<br><br>Oh well, on with the proof.<br><br>First, I'm solving the first question. I will be rewriting a_1 as a1, a_2 as a2, etc. to save on space. just remember that 'an' means 'a_n', NOT 'a*n'.<br><br>Here we go. The question is to prove:<br><br><b>(a1*a2*...*an)^(1/n) + (b1*b2*...*bn)^(1/n) <= [(a1+b1)*(a2+b2)*...*(an+bn)]^(1/n)</b><br><br>given that all the a's and b's are non-negative integers. (this will be important later)<br><br>Anywho, first I divided both sides by <b>(b1*b2*...*bn)^(1/n)</b>. Since everything is taken to the power of 1/n, I can slip the math into the parenthesis. This gives me<br><br><b>[(a1*a2*...*an)/(b1*b2*...*bn)]^(1/n) + 1 <= [ ((a1+b1)*(a2+b2)*...*(an+bn)) / (b1*b2*...*bn) ]^(1/n)</b><br><br><b>[(a1/b1)*(a2/b2)*...*(an/bn)]^(1/n) + 1 <= [ (a1+b1)/b1 * (a2+b2)/b2 * ... * (an+bn)/bn ] ^ (1/n)</b><br><br>just reworking the math. You'll see why later.<br><br>on the right side of the <=, everything is grouped into the form <b>(a+b )/b</b>. This can be writen as <b>a/b + b/b</b>, which equals <b>a/b + 1</b>. So, looking at the right side only:<br><br><b>[ (a1/b1 + 1) * (a2/b2 + 1) * ... * (an/bn + 1)] ^ (1/n)</b><br><br><b>[(a1/b1)*(a2/b2)*...*(an/bn) * (1*n)] ^ (1/n)</b><br><br>Why? Because if you add 1 to n terms being multiplied together, you could also multiply the terms together and multiply the total by 1*n.<br><br>(don't believe me? prove (2*1)*(3*1)*(4*1)*(5*1) = (2*3*4*5)*(1*4). 4 terms)<br><br>So, we end up with<br><br><b>[(a1/b1)*(a2/b2)*...*(an/bn)]^(1/n) + 1 <= [(a1/b1)*(a2/b2)*...*(an/bn) * (1*n)] ^ (1/n)</b><br><br><b>[(a1/b1)*(a2/b2)*...*(an/bn)]^(1/n) + 1 <= [(a1/b1)*(a2/b2)*...*(an/bn)]^(1/n) * (n)^(1/n)</b><br><br>cancel like terms, and:<br><br><b>1 <= n^(1/n)</b><br><br>Remember, n is the number of terms in the set. If n=0, it makes me wonder why I'm doing the problem at all. If n=1, 1^1=1. If n=2 (or more), then it will always be more than 1. Good luck trying to produce a set of numbers half a number long (or better still - with a negative amount!)<br><br>Well, it took me about 10 minutes to solve the problem, and about 30 to write it out. Let's hope the other proofs are shorter.
Still mostly here.

User avatar
norsenerd
Posts:2269
Joined:Tue Oct 14, 2003 2:42 pm
Location:Lost
Contact:

Postby norsenerd » Wed Dec 10, 2003 8:42 pm

I see a problem with this equality:<br><br><!--QuoteBegin--> <table border='0' align='center' width='95%' ><tr><td class='quotetop'><b>Quote:</b> </td></tr><tr><td class='quotebody'> <br>[ (a1/b1 + 1) * (a2/b2 + 1) * ... * (an/bn + 1)] ^ (1/n)<br><br>=<br><br>[(a1/b1)*(a2/b2)*...*(an/bn) * (1*n)] ^ (1/n)<br><!--QuoteEnd--></td></tr></table> <!--QuoteEEnd--><br><br>This is not true. You got the first term write but the last term is just one and you're missing all the cross terms. Fore example: (2+1)*(3+1)*(4+1)*(5+1) = (3*4*5*6) = 360 != 480 = 120*4 = (2*3*4*5)*(1*4)<br><br>Try looking at what the right side would look like if you multiply evrything out under the radical. Take a look at small number of terms first to see if there is a patern and compare that to the left side.<br><br>Good try though.
Llewellyn for President 2008 <br><br><img><br><img>

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Mon Dec 15, 2003 4:09 pm

Thanks. I saw this error about an hour after I wrote it; you know, when I couldn't go on-line anymore. I would have felt REALLY stupid if I was to correct myself. Hey, at least I tried.<br><br>Let's see here, I have... 3 more solutions. Which one first?<br>
Still mostly here.

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Mon Dec 15, 2003 4:25 pm

<!--QuoteBegin--> <table border='0' align='center' width='95%' ><tr><td class='quotetop'><b>Quote:</b> </td></tr><tr><td class='quotebody'> Given that f(x) is a real valued funtion on the interval [0,1] show that:<br><br>the double integral form 0 to 1 from 0 to 1 of the absolute value of (f(x)+f(y)) dxdy is greater then or equal to the integral from 0 to 1 of the absolute value of (f(x)) dx.<!--QuoteEnd--></td></tr></table> <!--QuoteEEnd--><br><br>Okay, to start off, I will say that the integral of f(x) = g(x). This is kinda essential.<br><br>Re-writing the problem, using "abs" for absolute value and "int" for integral, we have:<br><br><b>abs [ int ( int [ f(x)+ F(y) ] dx ) dy ] >= abs [ int f(x) dx ]</b><br><br>with all integral from 0 to 1. Doing the first integration on the left (and the only one on the right) gets<br><br><b>abs ( int [ g(x) + x*f(y) ] dy ) >= abs g(x)</b><br><br>x*f(y) is taken while x = 0 -> 1, so it equals 0*f(y) - 1*f(y) = -f(y). g(x) taken from 0 to 1 is whatever it is. Integrating again gets<br><br><b>abs [ -g(x) + -g(y) ] >= abs g(x)</b><br><br>for the same reason. Divide both sides by "abs g(x)," and<br><br><b>abs [ -g(x)/g(x) + -g(y)/g(x) ] >= 1</b><br><br>"abs g(x)" is positive (obviously), so the >= sign won't change. Simplifying:<br><br><b>abs [ -1 + -g(y)/g(x) ] >= 1</b><br><b>abs [ 1 + g(y)/g(x) ] >= 1</b><br><b>1 + abs [ g(y)/g(x) ] >= 1</b><br><b>abs [ g(y)/g(x) ] >= 0</b><br><br>The absolute value of any real number is always greater than or equal to zero, so the statement is true.<br>
Still mostly here.

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Mon Dec 15, 2003 5:15 pm

Some food and I'm feeling better. Still tired, though.<br><br><!--QuoteBegin--> <table border='0' align='center' width='95%' ><tr><td class='quotetop'><b>Quote:</b> </td></tr><tr><td class='quotebody'> For intergars a,b,c,d,e let a*z^4+b*z^3+c*z^2+d*z+e = a*(z-r_1)*(z-r_2)*(z-r_3)*(z-r_4) for all z when a !=0. Fiven that r_1+r_2 is rational and that r_1+r_2 != r_3+r_4 prove that r_1*r_2 is rational.<!--QuoteEnd--></td></tr></table> <!--QuoteEEnd--><br><br>First off, I'm stating that r1 stands for r_1, etc. Same thing again.<br><br><b>az^4+bz^3+cz^2+dz+e = a*(z-r1)*(z-r2)*(z-r3)*(z-r4)</b><br><br>(note to self: why are you re-typing all this?)<br>In any case, I'll work with the right side only. Factoring gives<br><br><b>a*(z^2 - z*r1 - z*r2 + r1*r2)*(z^2 - z*r3 - z*r4 + r3*r4)</b><br>you ready?<br><b>a*(z^4 - z^3*r3 - z^3*r4 + z^2*r3*r4<br> - z^3*r1 + z^2*r1*r3 + z^2*r1*r4 - z*r1*r3*r4<br> - z^3*r2 + z^2*r2*r3 + z^2*r2*r4 - z*r2*r3*r4<br> + z^2*r1*r2 - z*r1*r2*r3 - z*r1*r2*r4 + r1*r2*r3*r4)</b><br><br>Simplifying, this gives us:<br><b>a*z^4 +<br>[a*(-r1 - r2 - r3 - r4)]*z^3 +<br>[a*(r3*r4 + r1*r3 + r1*r4 + r2*r3 + r2*r4 + r1*r2)]*z^2 +<br>[a*(-r1*r3*r4 - r2*r3*r4 - r1*r2*r3 - r1*r2*r4)]*z +<br>r1*r2*r3*r4</b><br><br>Boy, I hope that shows up all right.<br>In any case, when comparing polynomials, two polynomials are equal iff the numbers in front of same exponential terms are the same... in other words, the numbers in front of the z^4 term need to be the same, etc.<br><br>So let's compare:<br><br><b>z^4 : a = a<br>z^3 : b = -a * (r1+r2+r3+r4)<br>z^2 : c = a * (r1*r2 + r1*r3 + r1*r4 + r2*r3 + r2*r4 + r3*r4)<br>z^1 : d = -a * (r1*r2*r3 + r1*r2*r4 + r1*r3*r4 + r2*r3*r4)<br>z^0 : e = r1*r2*r3*r4</b><br><br>Given that both c and a are intergers, then c/a is a rational number. Thus the trick is to prove that all the components of the 3rd line are rational.<br>It seems to me that you cannot add two irrational numbers and get a rational one. Thus, since r1*r2 + yadda yadda equals a rational number, all of the added terms must be rational also.<br><br>Of course, if only rational numbers can be added to produce rational numbers, it begs the question: doesn't "r1+r2=rational" (stated in the problem) prove that both are rational? If so, why the long problem? Am I missing something?<br><br>EDIT: Oops, I found a little inconsistenticy there, but I'll let others find it.<br>
Still mostly here.

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Mon Dec 15, 2003 5:59 pm

*post deleted*
Still mostly here.

User avatar
erikbarrett
Posts:496
Joined:Wed Oct 15, 2003 3:51 pm
Location:Ohio, USA

Postby erikbarrett » Mon Dec 15, 2003 7:56 pm

The post above: proof why rushed tired people shouldn't teach math.<br><br>I'll try to scan some graphs so it's a little easier to understand.
Still mostly here.


Return to “Anything”

Who is online

Users browsing this forum: No registered users and 46 guests