Anna and Bob, with Anna starting first, alternately color the integers of the set $S = \{1, 2, ..., 2022 \}$ red or blue. At their turn each one can color any uncolored number of $S$ they wish with any color they wish. The game ends when all numbers of $S$ get colored. Let $N$ be the number of pairs $(a, b)$, where $a$ and $b$ are elements of $S$, such that $a$, $b$ have the same color, and $b - a = 3$. Anna wishes to maximize $N$. What is the maximum value of $N$ that she can achieve regardless of how Bob plays?
Problem
Source: JBMO Shortlist 2022
Tags: combinatorics, game, Junior, Balkan, shortlist
27.06.2023 19:08
Replace $2022$ with $6m$, for $m=337$. We then claim the answer is $3m-3$. For $i \in \{1,2,3 \}$, let $A_i=\{s: \, 1 \leq s \leq 6m : s \equiv i \pmod 3 \}$. Then, Anna wishes to maximize the number of unordered pairs $(a,b)$ such that $a,b \in A_i$ for some $i$ and $a,b$ are of the same colour. For each $i$ and each $x \in A_i$, call $x-3$ and $x+3$ its neighbors. The problem splits into two parts. Part 1: Anna's strategy. Anna's strategy is to simply pick a coloured integer and colour one of its uncoloured neighbors with the same colour. This cannot be done only if for all $i$, all or no elements of $A_i$ are coloured, which will happen at most $3$ times during the process. Hence, Anna will increase $N$ by at least $1$ at least $3m-3$ times (she moves $3m$ times in total). Hence, this strategy guarantees that $N \geq 3m-3$. Part 2: Bob's strategy. Bob's strategy is to simply pick a coloured integer and colour one of its uncoloured neighbors with the other colour. This cannot be done only if for all $i$, all or no elements of $A_i$ are coloured. However, whenever Bob moves, an odd number of integers have been coloured, hence the above cannot happen. Therefore, Bob can always apply the above strategy. This strategy increases by at least one the number of pairs $(a,b)$ such that $a,b \in A_i$ and $a,b$ are of different colours. Thus, the number of these pairs $X$ in the end is $\geq 3m$, which implies that $N=(6m-3)-X \leq 3m-3$. To sum up, the answer to the problem is $\max N=3m-3$.
26.09.2024 21:14
well , I have not got any fancy notation stuff but there must be three trailings ,ie:$$1,2,3(mod3)$$respectively, $$1 ,4,7,10.....,2020$$$$2,5,......2021$$$$3,6,9,.....2022$$each with 674 elements ANAA'S STARTEGY:TO PICK A NUMBER(X) FROM ONE TRAILING AND COLUR IT WITH ANY COLOUR(RED) THEN BOB COULD COLOUR ANY OF ITS NEIGHBOUR ($X-3$,$x+3$),autmatically other neighbour would be done as anna's so pattern could be RBBRRBBRRBBRR....B EACH WITH $[673/2]$ PAIRINGS , HENCE ANSWER WOULD BE $[673/2]*3$