From: gale@math.berkeley.edu
Sent: Sunday, October 13, 2002 5:53 AM
To: Andries.Brouwer@cwi.nl
Cc: xysun@euclid.math.temple.edu; zeilberg@math.rutgers.edu
Subject: Re: chomp

What a charming argument, and rather surprising. Most Chomp proofs are by 
induction, which was what I was attempting
(e.g. If q > 1  then f(q,r) - q <= r).
On another matter, do you know a nice proof that f(q,r) - q is eventually 
periodic? The proofs I have seen are rather cumbersome.

David

At 05:09 AM 10/13/02 +0200, you wrote:
> > though perhaps there is an easy proof.
>
>Yes, there is.
>
>When I talk about rows and columns, I am thinking
>of the picture with q horizontally, r vertically,
>f(q,r) as entries.
>
>Suppose f(q,q) is not the largest in that column,
>but f(q,r) with r < q is the largest.
>Then why is none of the numbers f(q,s) (r+1 <= s <= q)
>at the position (q,r)?
>
>The column (q,*) contains q+1 different numbers f(q,r),
>all positive integers, so f(q,r) > q.
>It follows that f(q,r) is the smallest element that does
>not occur earlier in the same row or column.
>Since the numbers f(q,s) are not at the (q,r) position,
>it follows that they all occur earlier in row (*,r),
>but not at (t,r) with t >= r since above the diagonal
>verticals are constant.
>So, they all occur at (t,r) with r+1 <= t <= q-1.
>But there are more numbers s than positions t,
>contradiction.
>
>So, indeed, f(q,q) is the largest in its column.
>
>Best regards,
>Andries Brouwer