Gareth has nailed Q1 (which claimed earlier victims, who shall remain nameless). Q2 is certainly obvious; but the reasoning employed to support it is an example of what I have been seeking to eradicate: reliant on intuitions about geometry which (though undoubtedly reliable in an everyday context) require machinery which we would be pushed to make explicit. I'm looking for proofs involving only the lattice --- I hope that makes sense?! For example --- in the notation of Q3 --- e(x, y) equals the sum of e(x', y') over all neighbours (x', y') of (x, y) on shorter paths from (0,0) . Q3 I'm sure. But why does Gareth demur? [ Caveat --- please don't try posting the value(s) on math-fun!! ] WFL On 5/25/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
[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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun