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