I haven't fully digested Gareth's argument yet, but at first blush it does look both much simpler and more informative than my approach, for these two particular cases anyway. But immediately I wonder how easy it might be to generalise to other gradients. And whether, having done so, one might establish monotonicity relations between spatially neighbouring values in the same class (A1 etc), via some combinatorial injection that would bypass an analytical hole into which I have recently been digging myself ... Fred Lunnon On 6/4/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 03/06/2014 16:51, Fred Lunnon wrote:
<< Denote e(x, y) the number of shortest knight paths from (0,0) to (x,y) . Prove that e(1999999999, 3) = e(1500000000, 1499999998) . >>
A week ago I half-promised a solution for this question; so below follows a sketch glossing over the more gruesome details. ... If you have managed to struggle through to here, maybe now you understand why I'd like to see a more straightforward solution!
OK, so here is one, along previously advertised lines but hopefully less wrong. I'll take our two points to be A := (4N-1,3) and B := (3N,3N-2).
1. We can get to either point in 2N steps. (Easy.)
2. We can't get to either point in <= 2N-1 steps. (Dot product with (1,0) increases by at most 2 per step and must reach 4N-1 for A; dot product with (1,1) increases by at most 3 per step and must reach 6N-2 for B.)
(So we are counting paths of 2N steps.)
3. The deficit in that dot product, relative to its max attainable value, must end up being exactly 1 in case A and 2 in case B.
4(A). For a deficit of 1, we must have one move that's either (1,2) or (1,-2), and all the rest must be (2,1) or (2,-1).
If we have a (1,2) then we need a(2,1)+b(2,-1)=(4N-2,1) whose unique solution is (a,b)=(N,N-1).
If we have a (1,-2) then we need a(2,1)+b(2,-1)=(4N-2,5) whose unique solution is (a,b)=(N+2,N-3).
So the number of solutions is (2N;N,N-1,1) + (2N;N+2,N-3,1).
4(B). For a deficit of 2, we must have one move that's either (2,-1) or (-1,2), and all the rest must be (2,1) or (1,2).
If we have a (2,-1) then we need a(2,1)+b(1,2)=(3N-2,3N-1) whose unique solution is (a,b)=(N-1,N).
If we have a (-1,2) then we need a(2,1)+b(1,2)=(3N+1,3N-4) whose unique solution is (a,b)=(N+2,N-3).
So the number of solutions is (2N;N,N-1,1) + (2N;N+2,N-3,1).
5. These numbers are the same in both cases. (Indeed we could see this without the last lines of 4(A) and 4(B).)
I don't know whether this is really simpler than your proof but it requires no nontrivial algebra, no explicit invocation of induction, no special cases near 0, and no use of the complicated distance formula.
Just by way of confirmation, let's check the case N=3, for which allegedly 66 is the right answer. We get (6;3,2,1) + (6;5,0,1) = 60 + 6 = 66 as required.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun