Putnam, year 3: Specifics
Dec. 3rd, 2007 12:48 amFirst half:
A1 - Took that polynomial, composed it with itself, then moved on and didn't work on this one anymore.
A2 - I did this one by splitting into 4 triangles with a common vertex at the origin. I used one not-really-rigorous way to show the area of one of these triangles was minimized when it was iscosceles, then went back and did it a different way... only thing was, following through on my different way led to something wrong (so I didn't write that bit down). Uh...
Someone else did this by - the shoestring formula, is that what it's called? - the thing that looks like a determinant but is 2-by-n. Wow, I haven't seen that in a long time, I had entirely forgotten about that, I remember thinking.
A3 - Easy enough.
A4 - First I found the obvious linear ones. Then I realized obviously constant ones worked too. Were these all? I tried to look for a quadratic one... and, unexpectedly, found one - 100n²+10n+1. No, that doesn't actually work; I miscalculated. Still, I thought, this still looks kind of nice; what if I compose it with itself? Eep! After computing the result, I moved on. (Had I gotten my calculation of the original polynomial right, I would have moved on immediately, as what I was going for was 90n²+20n+1, or, as I originally arrived at it, (10n+1)²-10n².)
A5 - This one I did first, by writing up McKay's proof of Cauchy's Theorem (the p-tuples that product to 1 proof). But that, I thought, required oddly specific knowledge. (Calvin actually just said "this is part of Cauchy's Theorem", which I don't think it is usually considered to be - especially as McKay's proof is the only one I've seen that also proves this.) Fortunately, looking up the solutions, there actually were other ways to do this one...
Also, when was the last time they put a problem requiring actual knowledge of algebra on the Putnam?
A6 - I started on this one very late, because I somehow failed to notice it was actually a graph theory problem and had no idea what to do with it (being scared of geometry, after all). So, what do we have for this one? Euler's formula, v-e+f=2; looking at face-edge relations, we have 2e=3(f-1)+n; and looking at vertex-edge relations, 2e≤6(v-n)+2n. I spent some time manipulating these and heard the five-minute call. Somehow, I quickly got an answer, and scribbled it down (omitting much algebra, of course)! Of course, it was completely wrong - I had used some false equations I had written down earlier; in my haste, I hadn't noticed they weren't true. Had I algebra'd right, though, I still wouldn't have gotten it - I would have just gotten n≥1. In fact, you can't even get it from just those 3 relations - they're linearly dependent.
So, A3, A5, hopefully A2, and definitely not A6[0].
Second half:
B1 - Technically false as stated, but easy enough. (Though I actually didn't notice it was false as stated until long after I first solved it and put it aside; somehow the thought of "Wait, what about constants?" popped into my head - possibly a result of problem A4 before - and thankfully I went back and changed this.)
B2 - "Where the hell does 1/8 come from?" Scribbled a bit but didn't really try very much.
B3 - Oh gods, floors! Why does it always have to be floors?[3] Uh... find a recursion, maybe? Hm... well, it looks like we have xn+1=5xn+sum{xi:i=0 to n=1}. Is this true? I don't know, I haven't looked much at the solutions yet. Anyway, I conjectured this, figuring, well, if this is true, I can easily compute the generating function. So I did that, split into partial fractions, yay, explicit formula! And hey, since I have an explicit formula, perhaps I can prove *this* by induction, without reference to my conjectured recursion! Only problem... my explicit formula didn't work. It calculated x0 to be 10 rather than 1. Shit. At this point, I was running out of time. I'm thinking writing out irrational numbers explicitly and working with them that way rather than, you know, naming them and using their polynomial was a bad idea. (Well, I did name them in my own notes, r and s, but I should have just never worried about their explicit forms at all, except to define them.) Well, with no time left, I scribbled down my conjectured recursion, the generating function it gets you, and that you could split it into partial fractions to get an explicit formula closely resembling the one above, but apparently not quite equal to it[4].
B4 - Tried a bunch of stuff but didn't get much of anywhere.
B5 - This one is awful, and thus great. Looking it up, I see there's a very simple solution; and someone here apparently went and actually found nice forms for the Pi? I could be wrong about that. Maybe he just found the solution I saw here, thinking about it. Anyway, I like mine for how awful it is.
I spent a lot of time getting nowhere (goddamn floors), before finally getting the idea of trying it for k=2. Well, for n even, ⌊n/2⌋=n/2, and for n odd, ⌊n/2⌋=(n-1)/2. So what I need are polynomials P0 and P1 such that n²/4=P1(n)*n/2+P0(n) and (n-1)²/4=P1(n)*(n-1)/2+P0(n)... and hey, that's just solving a system of linear equations...
OH....
OK. All matrices and vectors that follow will be 0-indexed. Define a k-by-k matrix A over Q(x) by Ai,j=((x-i)/k)j, and Q∈Q(x)k by Qi=((x-i)/k)k. Then by a well-known formula[5], det(A)=product{(x-j)/k-(x-i)/k: 0≤i<j<k}=product{(i-j)/k: 0≤i<j<k}, and in particular, A is nonsingular. There is a unique P∈Q(x)k st AP=Q. Then for each n∈Z, let n=qk+r, 0≤r<k, ⌊n/k⌋=(n-r)/k, then ⌊n/k⌋k=((n-r)/k)k=Qr(n)=(AP)r(n)=sum{Ar,i(n)Pi(n): i=0 to k-1}=sum{Pi(n)((n-r)/k)i: i=0 to k-1}=sum{Pi(n)⌊n/k⌋i: i=0 to k-1}, which is what we wanted.
That's not the awful part. You may have noticed something missing in the above - namely, any assertion that our Pi are actually polynomials and not just rational functions. And, of course, I would never have actually written all this down if I did not have some assurance that the Pi are, in fact, polynomials. This is the awful part.
I used Cramer's Rule[6].
Cramer's Rule - Pi is given by the determinant of A-with-Q-substituted-into-the-ith-row divided by det(A). A completely awful formula. Cramer's Rule, which, Dr. Nevard taught us back in Senior Topics, you should never, ever, ever use. As if it really needed stating.
He said, as I recall, that the only application he knew of was something where you had these matrices and vectors of polynomials, and used to prove that your solution vector in fact consisted of polynomials and not just rational functions.
Which, as it happened, is exactly what I wanted to do. And somehow this memory triggered, and led me to this solution.
So I used Cramer's rule. A and Q consist entirely of polynomials, so A-with-Q-substituted-in has polynomial determinant, and the determinant of A, we saw above, is a constant. And there you go.
B6 - Didn't try.
So, in the second half, B1, B5, and maybe a point or two on B3.
-Harry
[0]Well, definitely not A1 or A4 either, but YKWIM.
[3]Though, ironically enough, the only non-B1 problem I got in this half involved floors.
[4]Tangentially, it occurs to me I ought to go remember that other way of solving linear recurrences, i.e. not by splitting the generating function into partial fractions. Though of course this recurrence doesn't fit that. Though, it gets you a rational generating function, so I suppose it must also come from a linear recurrence?
[5]The Vandermonde determinant, looking it up. I may have made a sign error, though obviously this is not very relevant. Probably should have tried some small examples to see which way the sign went first...
[6]Though I didn't recall its name, and simply cited it as "a well-known formula". Though I verified it first, because, of course, this was something I had never used before and wasn't certain I had it right.
A1 - Took that polynomial, composed it with itself, then moved on and didn't work on this one anymore.
A2 - I did this one by splitting into 4 triangles with a common vertex at the origin. I used one not-really-rigorous way to show the area of one of these triangles was minimized when it was iscosceles, then went back and did it a different way... only thing was, following through on my different way led to something wrong (so I didn't write that bit down). Uh...
Someone else did this by - the shoestring formula, is that what it's called? - the thing that looks like a determinant but is 2-by-n. Wow, I haven't seen that in a long time, I had entirely forgotten about that, I remember thinking.
A3 - Easy enough.
A4 - First I found the obvious linear ones. Then I realized obviously constant ones worked too. Were these all? I tried to look for a quadratic one... and, unexpectedly, found one - 100n²+10n+1. No, that doesn't actually work; I miscalculated. Still, I thought, this still looks kind of nice; what if I compose it with itself? Eep! After computing the result, I moved on. (Had I gotten my calculation of the original polynomial right, I would have moved on immediately, as what I was going for was 90n²+20n+1, or, as I originally arrived at it, (10n+1)²-10n².)
A5 - This one I did first, by writing up McKay's proof of Cauchy's Theorem (the p-tuples that product to 1 proof). But that, I thought, required oddly specific knowledge. (Calvin actually just said "this is part of Cauchy's Theorem", which I don't think it is usually considered to be - especially as McKay's proof is the only one I've seen that also proves this.) Fortunately, looking up the solutions, there actually were other ways to do this one...
Also, when was the last time they put a problem requiring actual knowledge of algebra on the Putnam?
A6 - I started on this one very late, because I somehow failed to notice it was actually a graph theory problem and had no idea what to do with it (being scared of geometry, after all). So, what do we have for this one? Euler's formula, v-e+f=2; looking at face-edge relations, we have 2e=3(f-1)+n; and looking at vertex-edge relations, 2e≤6(v-n)+2n. I spent some time manipulating these and heard the five-minute call. Somehow, I quickly got an answer, and scribbled it down (omitting much algebra, of course)! Of course, it was completely wrong - I had used some false equations I had written down earlier; in my haste, I hadn't noticed they weren't true. Had I algebra'd right, though, I still wouldn't have gotten it - I would have just gotten n≥1. In fact, you can't even get it from just those 3 relations - they're linearly dependent.
So, A3, A5, hopefully A2, and definitely not A6[0].
Second half:
B1 - Technically false as stated, but easy enough. (Though I actually didn't notice it was false as stated until long after I first solved it and put it aside; somehow the thought of "Wait, what about constants?" popped into my head - possibly a result of problem A4 before - and thankfully I went back and changed this.)
B2 - "Where the hell does 1/8 come from?" Scribbled a bit but didn't really try very much.
B3 - Oh gods, floors! Why does it always have to be floors?[3] Uh... find a recursion, maybe? Hm... well, it looks like we have xn+1=5xn+sum{xi:i=0 to n=1}. Is this true? I don't know, I haven't looked much at the solutions yet. Anyway, I conjectured this, figuring, well, if this is true, I can easily compute the generating function. So I did that, split into partial fractions, yay, explicit formula! And hey, since I have an explicit formula, perhaps I can prove *this* by induction, without reference to my conjectured recursion! Only problem... my explicit formula didn't work. It calculated x0 to be 10 rather than 1. Shit. At this point, I was running out of time. I'm thinking writing out irrational numbers explicitly and working with them that way rather than, you know, naming them and using their polynomial was a bad idea. (Well, I did name them in my own notes, r and s, but I should have just never worried about their explicit forms at all, except to define them.) Well, with no time left, I scribbled down my conjectured recursion, the generating function it gets you, and that you could split it into partial fractions to get an explicit formula closely resembling the one above, but apparently not quite equal to it[4].
B4 - Tried a bunch of stuff but didn't get much of anywhere.
B5 - This one is awful, and thus great. Looking it up, I see there's a very simple solution; and someone here apparently went and actually found nice forms for the Pi? I could be wrong about that. Maybe he just found the solution I saw here, thinking about it. Anyway, I like mine for how awful it is.
I spent a lot of time getting nowhere (goddamn floors), before finally getting the idea of trying it for k=2. Well, for n even, ⌊n/2⌋=n/2, and for n odd, ⌊n/2⌋=(n-1)/2. So what I need are polynomials P0 and P1 such that n²/4=P1(n)*n/2+P0(n) and (n-1)²/4=P1(n)*(n-1)/2+P0(n)... and hey, that's just solving a system of linear equations...
OH....
OK. All matrices and vectors that follow will be 0-indexed. Define a k-by-k matrix A over Q(x) by Ai,j=((x-i)/k)j, and Q∈Q(x)k by Qi=((x-i)/k)k. Then by a well-known formula[5], det(A)=product{(x-j)/k-(x-i)/k: 0≤i<j<k}=product{(i-j)/k: 0≤i<j<k}, and in particular, A is nonsingular. There is a unique P∈Q(x)k st AP=Q. Then for each n∈Z, let n=qk+r, 0≤r<k, ⌊n/k⌋=(n-r)/k, then ⌊n/k⌋k=((n-r)/k)k=Qr(n)=(AP)r(n)=sum{Ar,i(n)Pi(n): i=0 to k-1}=sum{Pi(n)((n-r)/k)i: i=0 to k-1}=sum{Pi(n)⌊n/k⌋i: i=0 to k-1}, which is what we wanted.
That's not the awful part. You may have noticed something missing in the above - namely, any assertion that our Pi are actually polynomials and not just rational functions. And, of course, I would never have actually written all this down if I did not have some assurance that the Pi are, in fact, polynomials. This is the awful part.
I used Cramer's Rule[6].
Cramer's Rule - Pi is given by the determinant of A-with-Q-substituted-into-the-ith-row divided by det(A). A completely awful formula. Cramer's Rule, which, Dr. Nevard taught us back in Senior Topics, you should never, ever, ever use. As if it really needed stating.
He said, as I recall, that the only application he knew of was something where you had these matrices and vectors of polynomials, and used to prove that your solution vector in fact consisted of polynomials and not just rational functions.
Which, as it happened, is exactly what I wanted to do. And somehow this memory triggered, and led me to this solution.
So I used Cramer's rule. A and Q consist entirely of polynomials, so A-with-Q-substituted-in has polynomial determinant, and the determinant of A, we saw above, is a constant. And there you go.
B6 - Didn't try.
So, in the second half, B1, B5, and maybe a point or two on B3.
-Harry
[0]Well, definitely not A1 or A4 either, but YKWIM.
[3]Though, ironically enough, the only non-B1 problem I got in this half involved floors.
[4]Tangentially, it occurs to me I ought to go remember that other way of solving linear recurrences, i.e. not by splitting the generating function into partial fractions. Though of course this recurrence doesn't fit that. Though, it gets you a rational generating function, so I suppose it must also come from a linear recurrence?
[5]The Vandermonde determinant, looking it up. I may have made a sign error, though obviously this is not very relevant. Probably should have tried some small examples to see which way the sign went first...
[6]Though I didn't recall its name, and simply cited it as "a well-known formula". Though I verified it first, because, of course, this was something I had never used before and wasn't certain I had it right.
