A white equilateral triangle $T$ with side length $2022$ is divided into equilateral triangles with side $1$ (cells) by lines parallel to the sides of $T$. We'll call two cells $\textit{adjacent}$ if they have a common vertex. Ivan colours some of the cells in black. Without knowing which cells are black, Peter chooses a set $S$ of cells and Ivan tells him the parity of the number of black cells in $S$. After knowing this, Peter is able to determine the parity of the number of $\textit{adjacent}$ cells of different colours. Find all possible cardinalities of $S$ such that this is always possible independent of how Ivan chooses to colour the cells.
Problem
Source: Bulgaria NMO 2022 P1
Tags: combinatorics, Parity, colouring
cadaeibf
18.04.2022 13:14
Assign a number $a_t\in\{0,1\}$ to every cell $t\in T$ ($T$ is the set of small triangles) where $a_t$ is $1$ iff $t$ is black. In the graph of triangles where two triangles have an edge between them (call this relation $\sim$) iff they are adjacent, let $n(t)$ be the number of neighbours of $t$. Then we want to look at the parity of $$\sum_{t\sim t'\in T} |a_t-a_{t'}|\equiv \sum_{t\sim t'}a_t-a_{t'}\equiv \sum_{t\in T}a_tn(t)\pmod{2}$$If $n(t)$ is even we don't need to know about the parity of $a_t$, and if $n(t)$ is odd we need to know about the value of $a_t$. Therefore, $|S|$ can be any number $\geq $ the number of cells with an odd number of neighbours. If $t$ is completely inside, it always has $12$ neighbors. If $t$ touches exactly one edge, it will always have $9$ neighbors. If $t$ touches $2$ edges, it will have $4$ neighbours (it can't touch three edges since the board is too big). Therefore, we just need to have $|S|\geq 3\cdot (2\cdot 2020-1)=12117$
Marinchoo
19.04.2022 08:41
Only $|S|=12120$ works.
Call the cells with an odd number of $\textit{adjacent}$ cells $\textit{nice}$ and the rest (those that have an even number of $\textit{adjacent}$ cells) $\textit{neutral}$. Notice that the parity of the number of $\textit{adjacent}$ cells of different colours depends only on the parity of the number of $\textit{nice}$ cells (this can be proven if you consider what changes as we colour a $\textit{nice}$ cells in black and respectively for a $\textit{neutral}$ cell). Now let the set of neutral cells be $N$. If $S$ doesn't contain every cell from $N$, then we can show two colourings with equal parity of black cells in $S$, but different parity of black cells in $N$, thus a different parity of $\textit{adjacent}$ cells of different colours. Thus $T\subseteq S$. However, if $S$ contains a cell outside of $T$, then we can do the same counterexample as above (by using $\textit{neutral}$ cells instead of $\textit{nice}$ one's). Thus we need to have $S\equiv T$. Now we only need to count $|T|$. The three cells sharing a vertex with the big triangle have 3 $\textit{adjacent}$ cells. The three cells which have a common side with these three corner cells have $6$ $\textit{adjacent}$ cells. The cells which have no common point with the sides of the big triangle have $12$ $\textit{adjacent}$ cells. The rest cells are the $\textit{side}$ cells (they have a common point with a side of the big triangle, but are not one of the $6$ such cells already mentioned) which have either $7$ or $9$ $\textit{adjacent}$ cells. Thus the number of $\textit{neutral}$ cells is (the cells with $12$ $\textit{adjacent}$ cells form a triangle with side $2019$ composed of cells):
\[3+(1+2+\ldots +2019)+(1+2+\ldots +2018)=3+\frac{2019\cdot 2020}{2}+\frac{2018\cdot 2019}{2}=3+2019^2\]Therefore the number of $\textit{nice}$ cells is:
\[|S|=|T|=\frac{2022\cdot 2023}{2}+\frac{2021\cdot 2022}{2}-(3+2019^2)=2022^2-2019^2-3=12120\]
math-w
28.12.2022 14:15
A quicker solution Claim: A cell will be chosen if an only if it adjacent with odd cells It looks simple. If you choose a cell adjacent with even cells, take it off or take it in. It’s a Contradiction Another side is the same. So just count how many cells is satisfy the request. The answer is 6n-12, especially it’s 12120 It’s so trivial