1 Problem

You will need a box of matches. Divide the matches into a number of piles, not necessarily the same number of matches in each pile. For example, you might lay out:

7, 5, 4, 7, 6, 19, 3 You are allowed to pick any of two piles. If the piles are equal, put them

together to make one pile; if the piles are not equal, take from the larger the number of matches that are in the smaller and add them to the smaller.

Using the example above, if you select the 5 and the 3, you get: 7, 2, 4, 7, 7, 6, 19, 6

If you then select the two piles of 6 you get:

7, 2, 4, 7, 12, 19 If you then select the second 7 and the 19, you get:

7, 2, 4, 14, 12, 12 You carry on in this way, repeatedly acting on the piles you got from your

previous action. Your target is to collect all the matches into one large pile. Sometimes that is possible, sometimes it is not.

For which of the following layouts is it possible to collect all the matches into one pile?

A. 17, 4, 5, 5, 1, 2, 3, 15, 12. B. 17, 4, 5, 5, 9. C. 51, 72, 57, 78, 78, 48. D. 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 23. (Enigma 648: Piles of Fun, Keith Austin, New Scientist, 11 January 1992).

2 Solution

For an array A, define

SUM(A) = Sum of elements of A,
GCD(A) = Greatest common divisor of elements of A,
A/f = Array of values A[i]/f,
odds(A) = {i | odd(A[i])},

and let move(x, y) implement the pairwise move specified in the problem. Show

{b = B ∧ S = SUM(B) ∧ (∃e : N · S = 2^{e} GCD(B))}

{invariant I: SUM(b) = S ∧ (∃e : N · S = 2^{e} GCD(b))} {bound t: S/GCD(b) + |odds(b/GCD(b))| − 2} do GCD(b) < SUM(b) → Choose (i, odds(b/GCD(b))) ;

Choose (j, odds(b/GCD(b)) − {i}) ;

move (b[i], b[j])

od

{∃i : 0 . . n − 1 · ∀j : 0 . . n − 1 · ((i = j ⇒ b[j] = S) ∧ (i ≠ j ⇒ b[j] = 0))}.

n is the size of the initial array B. Choose selects an element from a set. An equivalent bound function is (∑_{i}⌈b[i]/2 GCD (b)⌉) − 1.

Also, show that if the invariant is true after an arbitrary application of move, it must have been true before:

∀i : 0 . . n − 1 · ∀j : 0 . . n − 1 · i ≠ j ⇒ (wp(“move(b[i], b[j])”, I) ⇒ I)