ech (09/07/82)
#N:whuxlb:7200011:000:1941 whuxlb!ech Sep 7 10:39:00 1982 Kayles, Hint 8 and Wrap-up (collect them all!) Kayles: given two piles of stones, remove any number of stones from either pile, or an equal number of stones from each. Pick up the last stone. Safe configuration: one for which the second player has a forced win. Warmup: find a "safe configuration generator", and demonstrate correctness. Tougher: find a closed-form expression for the n-th safe configuration. ______ Hint 7 showed that, for any n,m > 0, floor (phi * n) != floor (phi^2 * m) We will now show that every positive integer is expressible in one form or the other, by induction. For a basis, we need merely calculate that the first few integers indeed qualify: 1 = floor(phi), 2 = floor(phi^2), 3 = floor(2 phi), 4 = floor(3 phi), 5 = floor(2 phi^2), ... For the inductive step, assume that 1,...,n-1 can be so expressed for n>3. We shall say that integers expressible as floor(phi*i) are 's' integers and those expressible as floor(phi^2*i) are 't' integers. We also observe that successive s's are separated by either 1 or 2 (since 1 < phi < 2), and similarly that successive t's are separated by either 2 or 3 (2 < phi^2 < 3). Finally, we need to remember that the s's and t's are disjoint, i.e. no positive integer is both an s and a t [hint 7]. We can now proceed by cases: 1) If n-1 is a t, then n-2 and n must be s's, since successive s's can't have a difference greater than 2. 2) Similarly, if n-2 and n-1 are s's, then n-3 and n must be t's. 3) If n-2 is a t, and n-1 is an s, then the next s and next t must BOTH be <= n+1. But since they can't both be equal to n+1, n must be either an s or a t. This concludes the proof that phi (in this curious sense!) partitions the positive integers, and (see note 5) it follows directly that the safe configurations for Kayles are just the pairs made up of successive s's and t's. Send all gripes/corrections/etc. by mail. Hope it's been fun! =Ned Horvath=
rhm (09/08/82)
It would have been a hell of a lot more fun if we had seen the problem rather than about half the hints! What is going on?