[math-fun] Atropa Belladonna
How to destroy any ability at chess which you may previously have enjoyed. 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. Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps. 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) . Fred Lunnon
What does "every point" refer to here? --Dan On May 24, 2014, at 1:54 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
How to destroy any ability at chess which you may previously have enjoyed. 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.
Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps.
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) .
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The Cartesian lattice in 2-space. WFL On 5/24/14, Dan Asimov <dasimov@earthlink.net> wrote:
What does "every point" refer to here?
--Dan
On May 24, 2014, at 1:54 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
How to destroy any ability at chess which you may previously have enjoyed. 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.
Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps.
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) .
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
[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
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
On 25/05/2014 14:59, Fred Lunnon wrote:
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 don't believe my solution relied on any appeals to intuition. It was admittedly *inspired* by geometric intuition, but there's no harm in that. Adam's beautiful one-liner is more obviously not dependent on geometric intuition (though it has a clear family resemblance to the Euclidean-distance-based solution: replace "distance" simpliciter with "distance in direction (2,1) and streamline). I have to confess I don't see much harm in making use of the extra structure the lattice has. Suppose we had some more "intrinsic" presentation of it and didn't know how it lives on an integer grid, and suppose someone answered your Q2 by saying "well, to begin with we can embed this thing in ZxZ, see, and now consider 2x+y and we're done." I think the response would be pretty positive.
Q3 I'm sure. But why does Gareth demur?
Because I made a conjecture about how many shortest paths there were in each case (and what they were), counted them and found that one number was substantially larger, then wrote a little computer program to check the results by brute-force search (for a smaller case, obviously) and found that it agreed with me for one side of the alleged equality and disagreed for the other -- having found some extra shortest paths to the point that I'd already thought had more. So it's possible that there's both a bug in my code and another error in my reasoning that goes in the other direction, and I wouldn't be *astonished* -- but I would be a bit surprised. -- g
I do like Adam's "energy" argument for Q2; tho' I'd probably prefer to (boringly) expand it into an induction. I'll be the first to admit that I have not properly worked out what the criteria for a proper combinatorial proof for this class of problem ought to be --- maybe discussing these puzzles might help firm things up! Virtually everything I have seen published about the knight's move metric appears to me full of unconvincing hand-waving. Partly perhaps because the physical situation is so familiar, authors are tempted into reliance on intuitive shortcuts which are horribly prone to mislead. A good example is Q1 : it is "obvious" that any point has a neighbour that is further away from the origin; unfortunately, it's also false. Anyway, if Gareth cares to show me (or all of us) his A3, I'll show him mine ... Fred Lunnon On 5/26/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 25/05/2014 14:59, Fred Lunnon wrote:
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 don't believe my solution relied on any appeals to intuition. It was admittedly *inspired* by geometric intuition, but there's no harm in that.
Adam's beautiful one-liner is more obviously not dependent on geometric intuition (though it has a clear family resemblance to the Euclidean-distance-based solution: replace "distance" simpliciter with "distance in direction (2,1) and streamline).
I have to confess I don't see much harm in making use of the extra structure the lattice has. Suppose we had some more "intrinsic" presentation of it and didn't know how it lives on an integer grid, and suppose someone answered your Q2 by saying "well, to begin with we can embed this thing in ZxZ, see, and now consider 2x+y and we're done." I think the response would be pretty positive.
Q3 I'm sure. But why does Gareth demur?
Because I made a conjecture about how many shortest paths there were in each case (and what they were), counted them and found that one number was substantially larger, then wrote a little computer program to check the results by brute-force search (for a smaller case, obviously) and found that it agreed with me for one side of the alleged equality and disagreed for the other -- having found some extra shortest paths to the point that I'd already thought had more.
So it's possible that there's both a bug in my code and another error in my reasoning that goes in the other direction, and I wouldn't be *astonished* -- but I would be a bit surprised.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 26/05/2014 17:50, Fred Lunnon wrote:
Anyway, if Gareth cares to show me (or all of us) his A3, I'll show him mine ...
OK. Note that the following is full of handwaving that I'm not strongly motivated to make more rigorous, especially as it may well just be wrong. So, we're interested in the number of shortest paths - from (0,0) to A := (4N, 3), and - from (0,0) to B := (3N, 3N-2). I think the shortest paths from O to A are made up of N-1 NEE, N SEE, 2 NNE -- (2N+1 choose N-1;N;2) or else N+1 NEE, N-2 SEE, 1 NNE, 1 SSE -- (2N+1 choose N+1;N-2;1;1) and the shortest paths from 0 to B are made up of N NNE, N-1 NEE, 1 SEE -- (2N choose N;N-1;1) If so, then the paths to A greatly outnumber the paths to B for large N. I should repeat at this point that I am by no means confident that any of this is correct. -- g
Immmediate reaction: why doesn't either formula give the correct answer when N = 1 , and both counts should equal 2 ? WFL On 5/26/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2014 17:50, Fred Lunnon wrote:
Anyway, if Gareth cares to show me (or all of us) his A3, I'll show him mine ...
OK. Note that the following is full of handwaving that I'm not strongly motivated to make more rigorous, especially as it may well just be wrong.
So, we're interested in the number of shortest paths - from (0,0) to A := (4N, 3), and - from (0,0) to B := (3N, 3N-2).
I think the shortest paths from O to A are made up of N-1 NEE, N SEE, 2 NNE -- (2N+1 choose N-1;N;2) or else N+1 NEE, N-2 SEE, 1 NNE, 1 SSE -- (2N+1 choose N+1;N-2;1;1)
and the shortest paths from 0 to B are made up of N NNE, N-1 NEE, 1 SEE -- (2N choose N;N-1;1)
If so, then the paths to A greatly outnumber the paths to B for large N.
I should repeat at this point that I am by no means confident that any of this is correct.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 26/05/2014 22:28, Fred Lunnon wrote:
Immmediate reaction: why doesn't either formula give the correct answer when N = 1 , and both counts should equal 2 ?
Immediate metareaction: Why would you expect them to in so special a case? Further remark: the following paths from (0,0) to (4,3) all have length 3, which is obviously best possible since the length must be odd and cannot be 1: 0,0 -NNE-> 1,2 -NNE-> 2,4 -SEE-> 4,3 0,0 -NNE-> 1,2 -SEE-> 3,1 -NNE-> 4,3 0,0 -SEE-> 2,-1 -NNE-> 3,1 -NNE-> 4,3 so either I have terribly misunderstood the problem statement or the answer cannot be 2. Furtherer remark: my formula for the RHS in the case N=1 is (2 choose 1;0;1) which does in fact equal 2. To summarize. You claim - The formulae should apply when N=1. - In this case, LHS = RHS = 2. - In this case, my formula gives different, hence wrong, results for both LHS and RHS to which I reply - If the formulae turned out wrong for very small N it would not surprise me (though actually I think they don't). - In this case, LHS > 2 since I have exhibited 3 distinct elements of the set being counted. - In this case, my formula for the RHS gives the answer you say is right. As usual, though, I think it eminently possible that I'm just confused and have misunderstood or misremembered the problem or done 2+2=3 somewhere or something equally daft. What am I getting wrong? -- g
Apologies --- I didn't read your previous post sufficiently carefully. So I must rephrase my critique: you stated << So, we're interested in the number of shortest paths - from (0,0) to A := (4N, 3), and - from (0,0) to B := (3N, 3N-2).
at which I might have more helpfully enquired why we should be interested in the first number at all?
Aliter, your understandable suspicion of small cases happens to be unjustified here: shortest paths with length 2 from (0,0) to (3,3) and (3,1) both number 2. [But imprecision over factorial arguments could possibly stiff your formulae with 0/0 instead.] WFL On 5/27/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2014 22:28, Fred Lunnon wrote:
Immmediate reaction: why doesn't either formula give the correct answer when N = 1 , and both counts should equal 2 ?
Immediate metareaction: Why would you expect them to in so special a case?
Further remark: the following paths from (0,0) to (4,3) all have length 3, which is obviously best possible since the length must be odd and cannot be 1:
0,0 -NNE-> 1,2 -NNE-> 2,4 -SEE-> 4,3 0,0 -NNE-> 1,2 -SEE-> 3,1 -NNE-> 4,3 0,0 -SEE-> 2,-1 -NNE-> 3,1 -NNE-> 4,3
so either I have terribly misunderstood the problem statement or the answer cannot be 2.
Furtherer remark: my formula for the RHS in the case N=1 is (2 choose 1;0;1) which does in fact equal 2.
To summarize. You claim - The formulae should apply when N=1. - In this case, LHS = RHS = 2. - In this case, my formula gives different, hence wrong, results for both LHS and RHS to which I reply - If the formulae turned out wrong for very small N it would not surprise me (though actually I think they don't). - In this case, LHS > 2 since I have exhibited 3 distinct elements of the set being counted. - In this case, my formula for the RHS gives the answer you say is right.
As usual, though, I think it eminently possible that I'm just confused and have misunderstood or misremembered the problem or done 2+2=3 somewhere or something equally daft. What am I getting wrong?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 27/05/2014 14:05, Fred Lunnon wrote:
Apologies --- I didn't read your previous post sufficiently carefully. So I must rephrase my critique: you stated << So, we're interested in the number of shortest paths - from (0,0) to A := (4N, 3), and - from (0,0) to B := (3N, 3N-2).
at which I might have more helpfully enquired why we should be interested in the first number at all?
Oh. Because I misread, obviously. (In a rather odd way.) OK, so actually it's (4N-1,3) and (3N,3N-2), and for the former the shortest paths are "obviously" those with N of NEE, N-1 of SEE, 1 of NNE, which does indeed give the same trinomial coefficient as for the latter.
[But imprecision over factorial arguments could possibly stiff your formulae with 0/0 instead.]
Only if I were foolish enough to write them in terms of factorials. Why would I do that? -- g
<< Only if I were foolish enough to write them in terms of factorials. Why would I do that? >> Because e(11, 3) = e(9, 7) = 66 , perhaps? WFL On 5/27/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 27/05/2014 14:05, Fred Lunnon wrote:
Apologies --- I didn't read your previous post sufficiently carefully. So I must rephrase my critique: you stated << So, we're interested in the number of shortest paths - from (0,0) to A := (4N, 3), and - from (0,0) to B := (3N, 3N-2).
at which I might have more helpfully enquired why we should be interested in the first number at all?
Oh. Because I misread, obviously. (In a rather odd way.) OK, so actually it's (4N-1,3) and (3N,3N-2), and for the former the shortest paths are "obviously" those with N of NEE, N-1 of SEE, 1 of NNE, which does indeed give the same trinomial coefficient as for the latter.
[But imprecision over factorial arguments could possibly stiff your formulae with 0/0 instead.]
Only if I were foolish enough to write them in terms of factorials. Why would I do that?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 28/05/2014 03:44, Fred Lunnon wrote:
<< Only if I were foolish enough to write them in terms of factorials. Why would I do that? >>
Because e(11, 3) = e(9, 7) = 66 , perhaps?
If so then my trinomial-coefficient formula is wrong, which would be no surprise at all, but I still don't see the motivation for writing either my (presumably wrong) answer or whatever the correct answer is in terms of factorials. (Binomial and multinomial coefficients are usually best left as they are rather than decomposed into products and quotients of factorials. So it seems to me, anyway. At least one way of writing the correct answer to a question of this sort will surely be as a multinomial coefficient, or a sum of a few of them, because each combination of so-many (2,1), so-many (1,2), etc., will give rise to a multinomial term. There will be only finitely many such terms because getting too far away from the "obvious" paths from (0,0) to the vicinity of (4N,0) or (3N,3N) will imply a path longer than the optimum. Handwave, handwave.) I should add that there might well be a proof that the shortest-path counts are equal that doesn't involve finding explicitly what they are. For instance, one might hope for a sort of eighth-turn operation that maps (2,1) to (1,2) to (-1,2) to (-2,1) etc. My brief attempts at a solution along these lines were not successful. -- g
Re factorials versus binomial coefficients --- `left as they are' assumes that the expression has been arrived at in the first place using the kind of argument you have been employing; but that is not necessarily the case. My own approach involved starting from an extensive table, developing a plausible Ansatz (good word, that), completing the result via interpolation, and confirming it via induction. The entire process was akin to pulling teeth while standing on a bucket, and it would be a welcome improvement to motivate and clarify such theorems in some more direct fashion. At the same time, as I was trying to say earlier, I suspect that reasoning about these problems intuitively, though seductive, is ultimately both limited and error-prone. For instance, your current approach is vitiated by the lack of any formal calculus to identify reliably those path shapes which are relevant. Apart from obvious D_4 symmetries of the board, a few (finitely many?) sporadic instances, and `fully stretched-out' e(2d, d) = 1 , the sequence e(2d, 3) = e(3d/2, 3d/2 - 2) of numerical coincidences appears to be unique: even the alternate (odd distance d ) points along these two infinite paths have different shortest-path counts. So any exotic `symmetry' sending one set of points to the other would have to send all other lattice points not isomorphic to them into non-lattice points. Fred Lunnon On 5/28/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 28/05/2014 03:44, Fred Lunnon wrote:
<< Only if I were foolish enough to write them in terms of factorials. Why would I do that? >>
Because e(11, 3) = e(9, 7) = 66 , perhaps?
If so then my trinomial-coefficient formula is wrong, which would be no surprise at all, but I still don't see the motivation for writing either my (presumably wrong) answer or whatever the correct answer is in terms of factorials.
(Binomial and multinomial coefficients are usually best left as they are rather than decomposed into products and quotients of factorials. So it seems to me, anyway. At least one way of writing the correct answer to a question of this sort will surely be as a multinomial coefficient, or a sum of a few of them, because each combination of so-many (2,1), so-many (1,2), etc., will give rise to a multinomial term. There will be only finitely many such terms because getting too far away from the "obvious" paths from (0,0) to the vicinity of (4N,0) or (3N,3N) will imply a path longer than the optimum. Handwave, handwave.)
I should add that there might well be a proof that the shortest-path counts are equal that doesn't involve finding explicitly what they are. For instance, one might hope for a sort of eighth-turn operation that maps (2,1) to (1,2) to (-1,2) to (-2,1) etc. My brief attempts at a solution along these lines were not successful.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I brain-stormed
Apart from obvious D_4 symmetries of the board, a few (finitely many?) sporadic instances, and `fully stretched-out' e(2d, d) = 1 , the sequence e(2d, 3) = e(3d/2, 3d/2 - 2) of numerical coincidences appears to be unique: even the alternate (odd distance d ) points along these two infinite paths have different shortest-path counts.
That list is incomplete, to put it mildly. The entire Pascal triangle is also replicated essentially twice: e(2d, d - 2t) = d_C_t = e(2d - t, d + t) for 0 <= t <= d . In particular, setting t = 1 shows that every integer occurs in both these subsets; so every other value is involved in some "sporadic" coincidence with them eventually! WFL On 5/28/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Re factorials versus binomial coefficients --- `left as they are' assumes that the expression has been arrived at in the first place using the kind of argument you have been employing; but that is not necessarily the case.
My own approach involved starting from an extensive table, developing a plausible Ansatz (good word, that), completing the result via interpolation, and confirming it via induction. The entire process was akin to pulling teeth while standing on a bucket, and it would be a welcome improvement to motivate and clarify such theorems in some more direct fashion.
At the same time, as I was trying to say earlier, I suspect that reasoning about these problems intuitively, though seductive, is ultimately both limited and error-prone. For instance, your current approach is vitiated by the lack of any formal calculus to identify reliably those path shapes which are relevant.
Apart from obvious D_4 symmetries of the board, a few (finitely many?) sporadic instances, and `fully stretched-out' e(2d, d) = 1 , the sequence e(2d, 3) = e(3d/2, 3d/2 - 2) of numerical coincidences appears to be unique: even the alternate (odd distance d ) points along these two infinite paths have different shortest-path counts.
So any exotic `symmetry' sending one set of points to the other would have to send all other lattice points not isomorphic to them into non-lattice points.
Fred Lunnon
On 5/28/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 28/05/2014 03:44, Fred Lunnon wrote:
<< Only if I were foolish enough to write them in terms of factorials. Why would I do that? >>
Because e(11, 3) = e(9, 7) = 66 , perhaps?
If so then my trinomial-coefficient formula is wrong, which would be no surprise at all, but I still don't see the motivation for writing either my (presumably wrong) answer or whatever the correct answer is in terms of factorials.
(Binomial and multinomial coefficients are usually best left as they are rather than decomposed into products and quotients of factorials. So it seems to me, anyway. At least one way of writing the correct answer to a question of this sort will surely be as a multinomial coefficient, or a sum of a few of them, because each combination of so-many (2,1), so-many (1,2), etc., will give rise to a multinomial term. There will be only finitely many such terms because getting too far away from the "obvious" paths from (0,0) to the vicinity of (4N,0) or (3N,3N) will imply a path longer than the optimum. Handwave, handwave.)
I should add that there might well be a proof that the shortest-path counts are equal that doesn't involve finding explicitly what they are. For instance, one might hope for a sort of eighth-turn operation that maps (2,1) to (1,2) to (-1,2) to (-2,1) etc. My brief attempts at a solution along these lines were not successful.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Re factorials versus binomial coefficients --- `left as they are' assumes that the expression has been arrived at in the first place using the kind of argument you have been employing; but that is not necessarily the case.
You mentioned factorials as a possible source of problems for the formulae I was offering. Those formulae (though no doubt wrong, and for all I know unfixable), did not contain any factorials.
At the same time, as I was trying to say earlier, I suspect that reasoning about these problems intuitively, though seductive, is ultimately both limited and error-prone. For instance, your current approach is vitiated by the lack of any formal calculus to identify reliably those path shapes which are relevant.
That would be why I've repeatedly said I'm only guessing at the answer, may well be wrong, etc. You've now protested twice at my alleged appeals to intuition. The first time, what I gave was a rigorous proof with no appeals to intuition in it. The second time, I wasn't purporting to offer anything other than handwaving. I agree that there is such a thing as unsound appeal to intuition, and I'm sure I've been guilty of it many a time -- but in the present instance I must demur. -- g
One possible way to approach these things that maybe has more of the "intrinsic" feel Fred is looking for: Let F : Z^4 -> Z^2 map the four standard basis vectors to four "basis" vectors of the knight's-move lattice; so it's represented by, say, the matrix (1 1 2 2; 2 -2 1 -1). The preimages of any point in Z^2 form a 2-dimensional lattice within Z^4 (offset by some single preimage) whose basis vectors are, if I've not messed up the routine calculations to get them, (1;-1;-2;2) and (-2;-2;1;1). Now questions about distances and shortest paths for a knight on the chessboard become questions about distances and shortest paths from the origin to *any point of that lattice* in Z^4. Or, equivalently, consider only the preimage lattice of 0 and ask about distances from some single preimage to *any point of that lattice*. So, for instance, the question about (2n,n) is the same as: show that of all points (a-2b;-a-2b;n-2a+b;2a+b), the one with the smallest L1-norm is (0;0;n;0). It's not obvious to me that this actually makes anything easier, but I think there's a fair chance that there's some single further bit of technique that makes all these questions, viewed from this perspective, routine. -- g
<< 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. The infinite chess-board lattice |Z^2 centred at the origin is subdivided into 8 sectors of alternating types: "A-regions" clustering about axes y = 0 & x >= 0 etc, and "B-regions" clustering about diagonals y = x & x,y >= 0 etc. The sectors are approximately separated by boundary lines along dilated knight moves x = 2y etc, though not exclusively: adjacent sectors intersect in common "C-region" bands spanning 4 lattice points wide. e(P) counts shortest knight paths from O = (0, 0) to P = (x, y) , of length in knight steps d(P) . By symmetry, we can assume x >= y >= 0 for the P under discussion (this may not necessarily hold for its neighbours). We also assume that d > 4 in order to avoid special cases near O , smaller cases being resolved by inspection. Then the distance formula simplifies to d(P) = x-y - 2t with t = [(x - 2y)/4] for P in A-region; x-y + 2t with t = [(2y - x)/3] for P in B-region. Note that e(P) equals the sum of e(P') , where P' ranges over "nearer" neighbours having d(P') = d(P) - 1 . As a first step, consider "type 0" paths, stretched as tautly as possible in some given direction: type A0 where P = (2d, d - 2t) ; type B0 where P = (2d - t, d + t) . Via the distance formula, such P can be shown to have (usually) 2 nearer neighbours: for type A0 , P' = (x-2, y+1), (x-2, y-1) ; for type B0 , P' = (x-1, y-2), (x-2, y-1) ; both P' are also of type A0 and B0 respectively. With a suitable change of coordinates, either set of e(P) becomes a Pascal triangle, so the answer is simply a binomial coefficient: for type 0 , ### e(2d, d - 2t) = e(2d - t, d + t) = d_C_t . ### Moving on, "type 1" paths have more wiggle room: type A1 where P = (2d - 1, d - 1 - 2t) ; type B1 where P = (2d - 1 - t, d - 1 + t) . Now there are (usually) 2+2 nearer neighbours: for type A1 , P' = (x-1, y+2), (x-1, y-2), (x-2, y+1), (x-2, y-1) ; for type B1 , P' = (x+1, y-2), (x-2, y-1), (x-1, y-2), (x-2, y-1) ; their types are A0,A1 and B0,B1 respectively. This yields a recurrence for e(P) in terms of nearer values and binomial coefficients. An appropriate ansatz (phwoar!) and some graft with difference tables on precomputed values delivers ### e(P) = ( d^2 - (2t+1)d + 2t(t+1) ) * (d+1)_C_(t+1) / (d+1) for type A1 ; e(P) = ( d^3 - 3t d^2 + (3t^2 - 1)d ) * (d+2)_C_(t+1) / (d+1)(d+2) for type B1 . ### These can then be verified via tedious induction; potentially hideous complications as t approaches its end-points near 0,d can be averted utilising the common C-region. We could continue on now, to types A2, B2, A3. Fortunately there's no need, because the question requires the special cases of A1 and B1 when d is even and t = d/2 - 1 . For such arguments there occurs this striking coincidence: after simplification and re-arrangement, ### e(2d-1, 3) = e((3/2)d, (3/2)d-2) = 2 d_C_(d/2 - 1) + d d_C_(d/2 - 2) . ### QED. The values for distance d = 0(2)12 are e = 2, 2, 12, 66, 336, 1620; for d = 10^9 , e has around 3.10^8 decimal digits. If you have managed to struggle through to here, maybe now you understand why I'd like to see a more straightforward solution! Fred Lunnon On 5/30/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
One possible way to approach these things that maybe has more of the "intrinsic" feel Fred is looking for:
Let F : Z^4 -> Z^2 map the four standard basis vectors to four "basis" vectors of the knight's-move lattice; so it's represented by, say, the matrix (1 1 2 2; 2 -2 1 -1).
The preimages of any point in Z^2 form a 2-dimensional lattice within Z^4 (offset by some single preimage) whose basis vectors are, if I've not messed up the routine calculations to get them, (1;-1;-2;2) and (-2;-2;1;1).
Now questions about distances and shortest paths for a knight on the chessboard become questions about distances and shortest paths from the origin to *any point of that lattice* in Z^4. Or, equivalently, consider only the preimage lattice of 0 and ask about distances from some single preimage to *any point of that lattice*.
So, for instance, the question about (2n,n) is the same as: show that of all points (a-2b;-a-2b;n-2a+b;2a+b), the one with the smallest L1-norm is (0;0;n;0).
It's not obvious to me that this actually makes anything easier, but I think there's a fair chance that there's some single further bit of technique that makes all these questions, viewed from this perspective, routine.
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
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
Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps.
Consider the `energy' E = 2x + y as a function of time. This can increase by at most 5 per move, and clearly the only move that increases it by 5 is (+2, +1). Quod erat demonstrandum. Sincerely, Adam P. Goucher
participants (4)
-
Adam P. Goucher -
Dan Asimov -
Fred Lunnon -
Gareth McCaughan