Competition problem — Combinatorics

Library / /53 of 56

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it JBMO

Problem:

Alice and Bob play the following game: Alice picks a set $A=\{1,2, \ldots, n\}$ for some natural number $n \geqslant 2$ . Then starting with Bob, they alternatively choose one number from the set $A$ , according to the following conditions: initially Bob chooses any number he wants, afterwards the number chosen at each step should be distinct from all the already chosen numbers, and should differ by 1 from an already chosen number. The game ends when all numbers from the set $A$ are chosen. Alice wins if the sum of all of the numbers that she has chosen is composite. Otherwise Bob wins. Decide which player has a winning strategy.

Solution

Solution:

To say that Alice has a winning strategy means that she can find a number $n$ to form the set $A$ , so that she can respond appropriately to all choices of Bob and always get at the end a composite number for the sum of her choices. If such $n$ does not exist, this would mean that Bob has a winning strategy instead.

Alice can try first to check the small values of $n$ . Indeed, this gives the following winning strategy for her: she initially picks $n=8$ and responds to all possible choices made by Bob as in the list below (in each row the choices of Bob and Alice are given alternatively, starting with Bob):

$\begin{array}{llllllll}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}2 & 3 & 1 & 4 & 5 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}2 & 3 & 4 & 1 & 5 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}3 & 2 & 1 & 4 & 5 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}3 & 2 & 4 & 5 & 1 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}3 & 2 & 4 & 5 & 6 & 1 & 7 & 8\end{array}$
$\begin{array}{llllllll}4 & 5 & 3 & 6 & 2 & 1 & 7 & 8\end{array}$
$\begin{array}{llllllll}4 & 5 & 3 & 6 & 7 & 8 & 2 & 1\end{array}$
$\begin{array}{llllllll}4 & 5 & 6 & 7 & 3 & 2 & 1 & 8\end{array}$
$\begin{array}{llllllll}4 & 5 & 6 & 7 & 3 & 2 & 8 & 1\end{array}$
$\begin{array}{llllllll}4 & 5 & 6 & 7 & 8 & 3 & 2 & 1\end{array}$
$\begin{array}{llllllll}5 & 4 & 3 & 2 & 1 & 6 & 7 & 8\end{array}$
$\begin{array}{llllllll}5 & 4 & 3 & 2 & 6 & 7 & 1 & 8\end{array}$
$\begin{array}{llllllll}5 & 4 & 3 & 2 & 6 & 7 & 8 & 1\end{array}$
$\begin{array}{llllllll}5 & 4 & 6 & 3 & 2 & 1 & 7 & 8\end{array}$
$\begin{array}{llllllll}5 & 4 & 6 & 3 & 7 & 8 & 2 & 1\end{array}$
$\begin{array}{llllllll}6 & 7 & 5 & 4 & 3 & 8 & 2 & 1\end{array}$
$\begin{array}{llllllll}6 & 7 & 5 & 4 & 8 & 3 & 2 & 1\end{array}$
$\begin{array}{llllllll}6 & 7 & 8 & 5 & 4 & 3 & 2 & 1\end{array}$
$\begin{array}{llllllll}7 & 6 & 8 & 5 & 4 & 3 & 2 & 1\end{array}$
$\begin{array}{llllllll}7 & 6 & 5 & 8 & 4 & 3 & 2 & 1\end{array}$
$\begin{array}{llllllll}8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\end{array}$

In all cases, Alice's sum is either an even number greater than $2$ , or else $15$ or $21$ , thus Alice always wins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.