## Unique differences

Four friends, Alice, Bob, Charlie and Dave, meet one Sunday afternoon to play a game of cards. There are 35 cards, each labelled with a unique positive integer between 1 and 35, inclusive. They are placed face-up on a table. In each round, each player takes turns removing one card from the table.

In the first round, a player is allowed to remove any card. From the second round onwards, a player is allowed to remove any card labelled with a number which is the difference of the numbers of two cards that have been removed before. The game ends when nobody can remove a card. The last one to remove a card from the table wins.

In each round, Alice takes the first turn, followed by Bob, Charlie and David, in that order. Alice did not remove a card with a multiple of 7 in the first round. Who can definitely win the game?

[SOLVED]

#### Ryan Batterman solved this puzzle:

The winner of the game is determined entirely by the first round. After the first round, there is a limited number of cards which can be obtained by the subtraction algorithm mentioned in the problem statement. The number of these cards determines the winner of the match.

Let N(A, B, C, D) denote the total number of cards removed after running the aforementioned algorithm when the game ends where A, B, C and D are the cards chosen in the first round. For instance, N(2, 1, 3, 6) = length of (2, 1, 3, 6, 5, 4) = 6. The N() function has an interesting property: N = max(A, B, C, D) if gcd(A, B, C, D) = 1. This can be demonstrated by examining the relationship between N() and the Euclidean algorithm.

The Euclidean algorithm determines the gcd of two numbers by means of successive subtractions. For example: gcd(9, 3) = gcd(9 - 3, 3) = gcd(6, 3) = gcd(6 - 3, 3) = gcd(3, 3) = 3. The same algorithm can be applied, in this problem, to remove a card which is the gcd of two other cards. Thus, for example, if we have A = 7, B = 3, some player can remove a 1-card during the game.

If it is possible to create a 1-card using any combinations of 2 cards, then N(A, B, C, D) = max(A, B, C, D). With a 1-card, the players in the difference algorithm subtract that 1 repeatedly from the maximum card to obtain every card with a value below that of the maximum.

But what if there are no 2 cards with a gcd of 1, but gcd(A, B, C, D) = 1? It's best to illustrate this case with an example: (A, B, C, D) = (33, 30, 28, 26). If the gcd of all 4 cards is 1, then it is possible to remove a 1-card using combinations of gcd's of two pairs. In this case, we can get gcd(33, 30) = 3 and gcd(28, 26) = 2. So, the 3-card and 2-card would be removed. Now, we get gcd(3, 2) = 1 and so the 1-card can also be removed.

We can easily determine that if gcd(A, B, C, D) > 1, then N(A, B, C, D) = max(A, B, C, D) / gcd(A, B, C, D).

Each player wants to manipulate the N() function such that he is the last one to draw a card. Alice wants N mod 4 = 1, Bob wants N mod 4 = 2, Charlie wants N mod 4 = 3, and David wants N mod 4 = 0. But who can definitely win the game?

It turns out that Charlie can win the game, every time, by choosing 35 if it has not been chosen already. gcd(A, B, 35, D) = 1 or 5 because A is not a multiple of 7 (given in problem statement). It's possible for the gcd to be 5 if all the cards are multiples of 5; e.g. (5, 10, 35, 20). If gcd(A, B, 35, D) = 5, then N(A, B, C, D) = max(A, B, 35, D) / 5 = 7. 7 mod 4 = 3. Charlie wins.

When gcd(A, B, C, D) = 1, N(A, B, C, D) = max(A, B, 35, D) = 35. 35 mod 4 = 3. Charlie wins again! Since he wins in both cases, Charlie has an assured victory.

#### Willem commented:

Charlie can definitely win the game. He takes the card with number 35.

If all other players took multiples of 5, then only multiples of 5 can be taken, which is 7 cards, so he wins in the 2nd round.

Otherwise, all 35 cards can be taken and he wins in the 9th round.

Now, to actually prove this takes a lot more work I'm afraid.

That's right and if 35 has already been taken he wins anyway.

It doesnt allow him to win if Alice and Bob both choose multiples of 7 ⇒ choosing 35 leads to a win for Alice. But the OP specifically discounts this possibility, and so Charlie can always win.

Proof: The game after round 1 is actually rather mechanical — just taking cards from a set which is complete under absolute differences. So the length of the set, mod 4, identifies the winner.

The length of the set is determined by its initial four seeds. If any two are coprime then by Euclid's algorithm the completed set must be all whole numbers from 1 to the maximum seed.

If 35 is in the set and any other seed is coprime to it then Charlie wins because 35 ≡ 3 (mod 4).

The only special case (other than the excluded one) is where all numbers are multiples of 5, generating the set {5, 10, 15, 20, 25, 30, 35} also of length 3 (mod 4).

### Credit

This is an original puzzle from cotpi.