[Fred posed some problems. I have answers, which may of course be wrong. Spoiler space follows in case they're right.] ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... ... SPOILER SPACE ... OK, here goes. On 24/05/2014 21:54, Fred Lunnon wrote:
Playing from the centre of an infinite open board ---
Q1. Prove that Every point has some knight-move neighbour at smaller knight-move distance from the origin if and only if Every point has some knight-move neighbour at greater knight-move distance from the origin.
Trick question. (0,0) is a silly counterexample to the first clause, and (2,2) a not-so-silly counterexample to the second. Perhaps there's some modest d such that every point of distance >= d from (0,0) has neighbours of both greater and lesser distance?
Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps.
This one's trivial. A "knight path" of r steps is a polygonal path made up of r segments of length sqrt(5); the Euclidean distance between its ends is therefore <= r sqrt(5) with equality iff all segments are in the same direction. The obvious path from (0,0) to (2r,r) is such a path. Any other path of length r starting at (0,0) either (a) doesn't have all segments in the same direction and hence can't get as far as (2r,r) or (b, 7 cases) goes to one of the obvious 7 other places like (2r,r); in particular none of these goes to (2r,r). QED.
Q3. Denote e(x, y) the number of shortest knight paths from (0,0) to (x,y) . Prove that e(1999999999, 3) = e(1500000000, 1499999998) .
How sure are you that this is true? I have some reason to think LHS > RHS here but I may well have miscalculated. -- g