On 13 Nov 2004 12:31:19 -0800, firstname.lastname@example.org (Chris) wrote:
>My 11 year old cousin got this question for homework.
I never got homework this hard when I was 11 (or when I was 18, for that matter)!
>I cannot find a solution.
I think I'm on the way to a solution, but it's past my bedtime, so I'll reluctantly have to stop.
>Am I missing something very obvious
I don't *think* so ...
>or is there simply no solution? > ><a href="http://geocities.com/chrissmith_156/question.gif">http://geocities.com/chrissmith_156/question.gif</a> > >By "repeat this process until you stop" I assume it means >until each corner turns to zero,
It's badly worded, but I also assume that's what it means.
>which usually only takes 3-7 recursions. Unless >you start using very big numbers...
I couldn't face experimenting with lots of numerical examples ...
... so I tried working backwards, i.e. looking at all configurations requiring 0 steps, then 1 step, then 2 steps, and so on.
This got a little too complicated --- quite quickly --- so I deviated from the logic a bit. Here are the cases I've looked at so far:
[A] All four numbers are zero. Then 0 steps are required.
Assume from now on that not all four numbers are zero. Then some positive number of steps is required.
[B] All four numbers are equal (but nonzero). Then one step (exactly) is required.
Assume from now on that not all four numbers are equal. Then more then one step is required.
(Easy so far!) :)
[C] Any two numbers diagonally opposite one another are equal (but not all four are equal). Then 2 steps (exactly) are required.
[D] Two numbers diagonally opposite one another are equal, *and* the sum of one diagonal pair is equal to the sum of the other diagonal pair [*but* still not all four numbers are equal, i.e. the other two diagonally opposite numbers are *not* equal to one another]. Then, again, 2 steps (exactly) are required.
[E] Two numbers diagonally opposite one another are equal, *but* the other two diagonally opposite numbers are not equal to one another (so cases [A]--[C] are excluded), *and* the sum of one diagonal pair is not equal to the sum of the other diagonal pair (so case [D] is also excluded). Then 4 steps (exactly) are required.
Proof: Without loss of generality ["w.l.o.g."] the sequence of numbers (cyclically permuted if necessary) is (b, c, d, c) where b + d \neq 2c ["\neq" = "not equals"], i.e. b - c \neq c - d, but also b - c \neq d - c (because b \neq d), whence |b - c| \neq |c - d|, so we have (b, c, d, c) --> (p, q, q, p), where p \neq q, and then (p, q, q, p) --> (s, 0, s, 0) --> (s, s, s, s) --> (0, 0, 0, 0), where s = |p - q| (\neq 0).
In all remaining cases, no two numbers diagonally opposite one another are equal, *and* more than 2 steps are required.
[I should spell out the logic of this more clearly, but it's now *way* past my bedtime! Briefly, cases [C] and [D] exhaust the configurations in which exactly 2 steps are required --- as is pretty easy to show, unless I've slipped up in some stupid way.]
There is another "easy" case to consider, before trying to tackle the remaining general case:
[F] The sum of one diagonal pair is equal to the sum of the other diagonal pair, *but* no two numbers diagonally opposite one another are equal. Then 3 steps (exactly) are required.
Proof: The sequence is (w, x, y, z) where w \neq y, x \neq z, and w - x + y - z = 0. Putting p = |w - x| = |y - z|, and q = |x - y| = |w - z|, we have (w, x, y, z) --> (p, q, p, q) --> (s, s, s, s) --> (0, 0, 0, 0), where s = |p - q|.
Note that we cannot have both p = 0 and q = 0, because then w = x = y, contrary to hypothesis. Nor can we have s = 0, because then p = q, in which case: either (i) w - x = y - x, contradicting w \neq y; or (ii) z - y = x - y, contradicting x \neq z. So the full 3 steps above really are required.
[Strictly speaking, the second paragraph of that argument was redundant, assuming that no error was made previously and therefore that cases [A]--[D] really *do* exhaust the configurations for which at most 2 steps are required. But it's nice to have a check --- especially in such a messy, still-unfinished proof.]
We are now reduced to the case where no two numbers diagonally opposite one another are equal, *and* the two pairs of diagonally opposite numbers do not sum to the same value.
Unfortunately, this case still seems to have many subcases requiring separate consideration; and so far, I have only begun to look at that group of cases where [after a cyclic permutation if necessary] the numbers are in non-decreasing order, either clockwise or anticlockwise. (Note that the given example does not meet this condition.)
We are looking at (w, x, y, z), where w \neq y, x \neq z, w + y \neq x + z, and (for the moment) w <= x <= y <= z.
We have (w, x, y, z) --> (p, q, r, p + q + r), where p = x - w, q = y - x, and r = z - y.
All of p, q, r are non-negative, of course. And from our hypotheses, it follows that at most one of p, q, r can be zero: e.g. if p = r = 0, then w = x and y = z, therefore w + y = x + z, contrary to hypothesis.
So far, I have only disposed of the cases where there is equality between some pair [as we have just seen, it can only be one pair] of numbers:
[G1] w = x (x \neq y, y \neq z):
(w, x, y, z) --> (0, q, r, q + r) --> (q, |q - r|, q, q + r).
[G1a] If q = r (i.e. if x, y, z are in arithmetic progression), 4 steps are required.
[G1b] If q > r (cf. case [D] above]), again 4 steps are required.
[G1c] If q < r (cf. case [E] above]), 6 steps are required. (You can prove this directly without appealing to [E].)
[G2] x = y (w \neq x, y \neq z):
(w, x, y, z) --> (p, 0, r, p + r) --> (p, r, p, r).
[G2a] If p = r (i.e. if w, x, z are in arithmetic progression), 3 steps are required.
[G2b] Otherwise, 4 steps are required.
[G3] y = z (w \neq x, x \neq y):
(w, x, y, z) --> (p, q, 0, p + q) --> (|p - q|, q, p + q, q).
This is equivalent to case [G1], by a cyclic permutation, so I won't bother to write out a detailed analysis (at 3 a.m. ...)
[... much more work to do ...]
I hope someone (probably on the other side of the world!) can finish this off (while I sleep ...), and that I haven't just made a simple problem more complicated than necessary. (I should probably have left it for an 11-year-old to do!)