Two players, the builder and the destroyer, plays the following game. Builder starts and players chooses alternatively different elements from the set $\{0,1,\ldots,10\}.$ Builder wins if some four integer of those six integer he chose forms an arithmetic sequence. Destroyer wins if he can prevent to form such an arithmetic four-tuple. Which one has a winning strategy?
Problem
Source: Finland 2011, Problem 5
Tags: arithmetic sequence, combinatorics unsolved, combinatorics
bozzio
07.05.2013 19:39
We will show that D has a winning strategy. The arithmetic progression can have the distance d of the element equal to 1,2,3. Those with 3 are: $0,3,6,9$ $1,4,7,10$ Those with two are: $0,2,4,6$ $2,4,6,8$ $4,6,8,10$ $1,3,5,7$ $3,5,7,9$ Now we have two cases, the one with B picking 4 as first number and the other. If B doesn't choose 4 D chooses it . In this way he delete 4 sequence with d>1 for B. After the second move of B, D chooses an element in order to destroy the sequence of d=1 or otherwise he picks an element in order to destroy an other 2 sequence with d>1 (it is possible). At the third move D have to stop the d=1 sequence or the d>1 sequence B is trying to do (the last available). So he picks an element in order to stop the d=1 sequence (it can have at most 2 element) or destroys the last sequence. In the following moves D has to stop the d=1 sequences or try to destroy the d>1 sequence at each step. (With this strategy every two element in arithmetic progression D pick the third not allowing B to have two possibilities to win after a three element progression). Now the case B picks 4. In this case D has to destroy as many sequence with the 4 as possible. So D takes 6. Now the best move B can do is to pick number 3. So D takes number 5 leaving 1,4,7,10 as the only d>1 sequence. At this point B can try to pick 2 or 1 to continue with his remaning sequence. So D takes 2 or 1 destroing the d=1 sequence. In the next move D destroyes the very last d>1 sequence and eventually he destroyes every d=1 sequence.