![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyAs of writing this, I have not looked at the solutions that people have posted. (The problems from this and past years, along with solutions, can be found here). If you want to solve them yourself, don't read this, obviously...
EDIT 2:42 AM: I went back and checked B2 again as I noted I should do in the first paragraph below the cut, and indeed, my idea works (or I suppose would have worked, had... well, see last entry). I'm surprised I didn't hear anyone else using it, but then again, [formula] is kind of obscure.
Regarding last entry: [subject] is calculus, [formula] is Cauchy's repeated integration formula (actually, I think it does apply, as the proof should still work, I was just doing my integration wrong when I tried to use it afterward, as I was a bit too free with my improper integrals - I'll have to go back and check it again), [theorem] is Hensel's Lemma, and [do something] is count the number of k-local involutions, though apparently that's not how you solve it (or not the one I heard, anyway).
A1. There's nothing to say about this. I mean, c'mon.
A2. I figured this one out by looking at the 2x2 case. Interestingly enough, Sam Raskin got screwed up by looking at the 2x2 case, because he thought of placing 0s, rather than matching. (Er, oh, the actual answer is that Barbara wins, as because the number of rows is even, for each row she can pick a different, corresponding, row, and whatever Alan does, she imitates in the corresponding row. Thus two rows are equal (to understate things), and the determinant is 0.)
A3. That it terminates is just well-ordering under lexicographic order. Invariance... well, all the ways I've heard of doing this are essentially the same, small powers of primes filter to the left, large powers to the right, but the way I did it that I was surprised I hadn't heard from anyone else was to associate the sequence with a finite abelian group, Z/(a1)×...×Z/(an). Then the isomorphism type of this group is invariant under the operation, and the final result is the invariant factor form of the group, which by the Fundamental Theorem of Finite Abelian Groups, is uniquely determined. So I didn't have to do so much bookkeeping with prime factorizations. (The slight technical error I made was that actually, the invariant factor form doesn't include the string of 1s you'll get at the front. Of course, the number of those will have to be the length of the sequence minus the number of invariant factors, so this is pure bookkeeping, but I didn't write that down as I didn't realize it needed to be written till afterward.)
A4. The basic calculus I forget is that the sum converges iff the integral does. I doubt I would have gotten it had I remembered, though. People had all sorts of solutions for this one, but the nice one I saw afterward was that if the integral converges, then doing an integration by substitution and using the functional equation directly - no induction involved in this solution - the integral from 1 to infinity is the same as the integral from e to infinity. But then the integral from 1 to e is 0, which it isn't, contradiction.
A5. The obvious identification I failed to make is identifying (f,g) with f+ig. I thought of doing something with complex polynomials, but dismissed it because the real part and imaginary parts of a polynomial aren't also polynomials. Of course, when you're plugging in real numbers, they are. As a result, being unsure what to do with a bunch of sines and cosines, I tried to directly interpolate and show that at least one had nonzero leading coefficient. But how can I work with these sines and cosines? Hey, shouldn't these be linearly independent over Q? Short answer: No. Long answer: I wrote down a solution based on certain nth roots of unity being linearly independent over Q, which, uh, isn't true in most cases. Hardly at all. I wrote down "Oh, crap! This only works for n squarefree!", though I didn't even prove that, but it's when n is squarefree that the /primitive/ nth roots of unity are linearly independent; for them all to be happens, uh, never. The ones I was using did at least work in the prime case, but not, in fact, in the general squarefree case. Also, using complex polynomials would have made it much more obvious that "at least one of them is of degree ≥m-1" is preserved under rotation, seeing "at least one of them is of degree ≥m-1" is just "deg(f+ig)≥m-1" and rotation is just scalar multiplication. So that's probably no points on A5 after all.
A6. Only person there who had anything for this one was Calvin. His idea was as follows: We take a |G|m×2m matrix, where the rows are all possible sequences in G of length m, and the columns are the subsequences, and the entries are the group elements you get this way, and that (by picking m sufficiently large but less than clog|G|) if no row contained all of them, each row contained at most g-1, and you could do some PIE stuff to get a contradiction. If this works, I don't know.
B1. Yay high school geometry! You can easily find one with 2, and if there's 3 rational points, the center must be the circumcenter, which we can find by a bunch of rational linear equations (it being the intersection of the perpendicular bisectors) and so is rational.
B2. See my comments at the top, and yesterday's entry, about how I tried and failed to do this one, both during and after the exam. Apparently you end up with something containing a harmonic series over log?
B3. I've heard the answer to this one, though I forget it, but no idea how to prove it. Calvin said he knew how to do the cube - you use the hexagon - but didn't know how to prove that, either. Some people here did get it but I haven't heard anything about how.
B4. Oh man, I really screwed this one up. Here's the solution I came up with afterward. For a∈Z/(p³), pick n∈Z reducing to it, then h-n has a root in Z/(p²) and hence in Z/(p); we want to apply Hensel's Lemma to find a root in Z/(p³), as Z/(p³) is finite so surjectivity of h implies injectivity. Well, note that h'(0)=h1≠0 as for pk∈Z/(p²), pk≠0, h(pk)=h1pk+h0, and so it can't be injective over Z/(p²) if h1=0. But translates of h (meaning h(x+a)) also have the same property that defines h, and so also have nonzero derivative at 0, i.e. h has nonzero derivative everywhere, and we can apply Hensel's Lemma everywhere. But at the time, I was convinced Hensel's Lemma couldn't possibly apply, as it looked to me like things extended in more than one way - I was thinking about it purely in terms of a polynomial over Z/(p), but that's not how Hensel's Lemma works. And this despite noticing that h1≠0; I got into all sorts of confusing contradictions with that one.
B5. Here's my solution: We'll look at f' at rational points. At a rational point a/q, since the derivative exists, to find it we can approach a/q any way we want. We'll approach it through numbers b/n with an-bq=1, which is not so hard to see do approach a/q arbitrarily closely. You'll notice that at those points, the difference quotient is an integer; as Z is closed, the derivative is an integer. But f' is continuous and Q is dense in R and Z is still closed, so in fact f' lies in Z everywhere. But as R is connected and Z is discrete and f' is still continuous, f' is constant, i.e. f is a linear polynomial (with integer linear term, no less). And once you have that, the rest is easy. (The answer being that they're functions of the form l+x and l-x for l∈Z.)
B6. See top about how I tried to do this one; I tried various ways to show that it only depended on the value mod 2k+1 (without even getting into what happened for n<2k+1), but couldn't get any to work. The trick Calvin told me, though I haven't bothered to work out a full solution yet, is to realize that the number of k-local permutations is just the permanent of a 0-1 matrix with 1s in the spots (i,j) with |i-j|≤k, and that mod 2, a permanent is just a determinant, and so is not so hard to calculate. I've seen this sort of trick before; I'm going to have to start remembering it. Maybe I should look through A Course in Combinatorics a bit...
Later I'll actually take a look at the solutions for the other problems...
-Harry
EDIT 2:42 AM: I went back and checked B2 again as I noted I should do in the first paragraph below the cut, and indeed, my idea works (or I suppose would have worked, had... well, see last entry). I'm surprised I didn't hear anyone else using it, but then again, [formula] is kind of obscure.
Regarding last entry: [subject] is calculus, [formula] is Cauchy's repeated integration formula (actually, I think it does apply, as the proof should still work, I was just doing my integration wrong when I tried to use it afterward, as I was a bit too free with my improper integrals - I'll have to go back and check it again), [theorem] is Hensel's Lemma, and [do something] is count the number of k-local involutions, though apparently that's not how you solve it (or not the one I heard, anyway).
A1. There's nothing to say about this. I mean, c'mon.
A2. I figured this one out by looking at the 2x2 case. Interestingly enough, Sam Raskin got screwed up by looking at the 2x2 case, because he thought of placing 0s, rather than matching. (Er, oh, the actual answer is that Barbara wins, as because the number of rows is even, for each row she can pick a different, corresponding, row, and whatever Alan does, she imitates in the corresponding row. Thus two rows are equal (to understate things), and the determinant is 0.)
A3. That it terminates is just well-ordering under lexicographic order. Invariance... well, all the ways I've heard of doing this are essentially the same, small powers of primes filter to the left, large powers to the right, but the way I did it that I was surprised I hadn't heard from anyone else was to associate the sequence with a finite abelian group, Z/(a1)×...×Z/(an). Then the isomorphism type of this group is invariant under the operation, and the final result is the invariant factor form of the group, which by the Fundamental Theorem of Finite Abelian Groups, is uniquely determined. So I didn't have to do so much bookkeeping with prime factorizations. (The slight technical error I made was that actually, the invariant factor form doesn't include the string of 1s you'll get at the front. Of course, the number of those will have to be the length of the sequence minus the number of invariant factors, so this is pure bookkeeping, but I didn't write that down as I didn't realize it needed to be written till afterward.)
A4. The basic calculus I forget is that the sum converges iff the integral does. I doubt I would have gotten it had I remembered, though. People had all sorts of solutions for this one, but the nice one I saw afterward was that if the integral converges, then doing an integration by substitution and using the functional equation directly - no induction involved in this solution - the integral from 1 to infinity is the same as the integral from e to infinity. But then the integral from 1 to e is 0, which it isn't, contradiction.
A5. The obvious identification I failed to make is identifying (f,g) with f+ig. I thought of doing something with complex polynomials, but dismissed it because the real part and imaginary parts of a polynomial aren't also polynomials. Of course, when you're plugging in real numbers, they are. As a result, being unsure what to do with a bunch of sines and cosines, I tried to directly interpolate and show that at least one had nonzero leading coefficient. But how can I work with these sines and cosines? Hey, shouldn't these be linearly independent over Q? Short answer: No. Long answer: I wrote down a solution based on certain nth roots of unity being linearly independent over Q, which, uh, isn't true in most cases. Hardly at all. I wrote down "Oh, crap! This only works for n squarefree!", though I didn't even prove that, but it's when n is squarefree that the /primitive/ nth roots of unity are linearly independent; for them all to be happens, uh, never. The ones I was using did at least work in the prime case, but not, in fact, in the general squarefree case. Also, using complex polynomials would have made it much more obvious that "at least one of them is of degree ≥m-1" is preserved under rotation, seeing "at least one of them is of degree ≥m-1" is just "deg(f+ig)≥m-1" and rotation is just scalar multiplication. So that's probably no points on A5 after all.
A6. Only person there who had anything for this one was Calvin. His idea was as follows: We take a |G|m×2m matrix, where the rows are all possible sequences in G of length m, and the columns are the subsequences, and the entries are the group elements you get this way, and that (by picking m sufficiently large but less than clog|G|) if no row contained all of them, each row contained at most g-1, and you could do some PIE stuff to get a contradiction. If this works, I don't know.
B1. Yay high school geometry! You can easily find one with 2, and if there's 3 rational points, the center must be the circumcenter, which we can find by a bunch of rational linear equations (it being the intersection of the perpendicular bisectors) and so is rational.
B2. See my comments at the top, and yesterday's entry, about how I tried and failed to do this one, both during and after the exam. Apparently you end up with something containing a harmonic series over log?
B3. I've heard the answer to this one, though I forget it, but no idea how to prove it. Calvin said he knew how to do the cube - you use the hexagon - but didn't know how to prove that, either. Some people here did get it but I haven't heard anything about how.
B4. Oh man, I really screwed this one up. Here's the solution I came up with afterward. For a∈Z/(p³), pick n∈Z reducing to it, then h-n has a root in Z/(p²) and hence in Z/(p); we want to apply Hensel's Lemma to find a root in Z/(p³), as Z/(p³) is finite so surjectivity of h implies injectivity. Well, note that h'(0)=h1≠0 as for pk∈Z/(p²), pk≠0, h(pk)=h1pk+h0, and so it can't be injective over Z/(p²) if h1=0. But translates of h (meaning h(x+a)) also have the same property that defines h, and so also have nonzero derivative at 0, i.e. h has nonzero derivative everywhere, and we can apply Hensel's Lemma everywhere. But at the time, I was convinced Hensel's Lemma couldn't possibly apply, as it looked to me like things extended in more than one way - I was thinking about it purely in terms of a polynomial over Z/(p), but that's not how Hensel's Lemma works. And this despite noticing that h1≠0; I got into all sorts of confusing contradictions with that one.
B5. Here's my solution: We'll look at f' at rational points. At a rational point a/q, since the derivative exists, to find it we can approach a/q any way we want. We'll approach it through numbers b/n with an-bq=1, which is not so hard to see do approach a/q arbitrarily closely. You'll notice that at those points, the difference quotient is an integer; as Z is closed, the derivative is an integer. But f' is continuous and Q is dense in R and Z is still closed, so in fact f' lies in Z everywhere. But as R is connected and Z is discrete and f' is still continuous, f' is constant, i.e. f is a linear polynomial (with integer linear term, no less). And once you have that, the rest is easy. (The answer being that they're functions of the form l+x and l-x for l∈Z.)
B6. See top about how I tried to do this one; I tried various ways to show that it only depended on the value mod 2k+1 (without even getting into what happened for n<2k+1), but couldn't get any to work. The trick Calvin told me, though I haven't bothered to work out a full solution yet, is to realize that the number of k-local permutations is just the permanent of a 0-1 matrix with 1s in the spots (i,j) with |i-j|≤k, and that mod 2, a permanent is just a determinant, and so is not so hard to calculate. I've seen this sort of trick before; I'm going to have to start remembering it. Maybe I should look through A Course in Combinatorics a bit...
Later I'll actually take a look at the solutions for the other problems...
-Harry
no subject
Date: 2008-12-08 07:49 pm (UTC)