|
|
Re: 11 year olds homework
Posted:
Nov 13, 2004 9:56 PM
|
|
On 13 Nov 2004 12:31:19 -0800, chrissmith_156@yahoo.co.uk
(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 ...
>Any ideas?
... 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!)
--
Angus Rodgers
(angus_prune@ eats spam; reply to angusrod@)
Contains mild peril
|
|
