We have $2021$ colors and $2021$ chips of each color. We place the $2021^2$ chips in a row. We say that a chip $F$ is bad if there is an odd number of chips that have a different color to $F$ both to the left and to the right of $F$. (a) Determine the minimum possible number of bad chips. (b) If we impose the additional condition that each chip must have at least one adjacent chip of the same color, determine the minimum possible number of bad chips.
Problem
Source: Spain Mathematical Olympiad 2021 P3
Tags: combinatorics, Spain, Parity
11.05.2021 04:48
Of the $2021$ chips of each colour, call the first, third, etc. odd and the others even. Likewise, out of the $2021^2$ possible positions, call the first, third, etc. odd and the rest even. Then a chip is bad iff the parity of its position is the opposite of its parity. (a) Note that there are $1011\cdot 2021$ odd chips, but only $\frac{2021^2+1}2$ odd locations. So, at least $1011\cdot 2021 - \frac{2021^2+1}2 = 1010$ chips are bad. To achieve this, place the chips of colours $c = 1, \ldots, 2020$ in the positions $2022c-2021,2022c-2020,\ldots,2022c-1$ and place the chips of colour $c=2021$ in the positions $2022,4044,\ldots,2022\cdot 2020, 2021^2$. In this way, the only bad chips are the $1^\text{st},3^\text{rd},\ldots, 2019^\text{th}$ chips of colour $c=2021$; there are $1010$ of these. (b) Note that for every odd chip in an even position, at least one of its neighbours must be an even chip of the same colour in an odd position. Conversely, for every bad even chip, at most two of its neighbours are bad odd chips of the same colour. Suppose there are $a$ bad odd chips and $b$ bad even chips. The number of pairs of adjacent bad chips of the same colour is at least $a$, but at most $2b$. So $a\le 2b$. On the other hand, we also have (by counting the number of odd/even chips/locations) $a-b = 1010$. So $a = 1010+b \le 2b$, i.e. $b \ge 1010$. Hence the number of bad chips is $a+b = 2b + 1010 \ge 3030$. To construct the equality case, place the chips of colours $c = 1, \ldots, 2018$ in the positions $2024c-2023,2024c-2022,\ldots,2024c-3$. This leaves us with $2017$ gaps of length $3$, each starting with an even location. Additionally, we also have $12$ empty spaces at the end; these go even, odd, ..., odd. Now, divide put the first $2019$ chips of colour $2019$ in the first $673$ gaps, the first $2019$ chips of colour $2020$ in the next $673$ gaps, and the first $2013$ of the last colour in the next $671$ gaps. This gives us $3\left(\frac{673+1}2 + \frac{673+1}2 + \frac{671+1}2\right) = 3030$ bad chips. Now, we have $2$ chips each of colours $2019$ and $2020$, and $8$ of colour $2021$. Just place them in that order, and they will not be bad.