An equilateral triangle with side length is coloured in white and partitioned into equilateral triangles with side length (called cells) through lines, parallel to the sides of . Two cells are called adjacent if they have at least one vertex in common. Ivan colors some of the cells in black. Without seeing which cells are black, Peter selects only once a set of cells (containing at least one) and asks Ivan if the number of blacks among the selected ones is even or odd. After receiving an answer, Peter is able to tell if the number of pairs of differently colored adjacent cells in is even or odd. Find all possible values of the number of elements of if that is always possible no matter the coloring of Ivan.
, 2022
Solution
For simplicity we write instead of Ivan and instead of Peter. The crucial idea is in the following
Lemma. In the graph all vertices are initially colored white. Let colors some of the vertices in black and asks about the parity of the number of blacks in a set from vertices, and with the answer can unambiguously determine the parity of the number of differently colored pairs adjacent/vertices in . Then must be the set of all vertices of odd degree in .
Proof. We will work by modulus . We write the number in each black vertex, the number in each white vertex and the sum of the numbers in its vertices on each edge. Each black vertex of odd degree contributes to the sum of the numbers on the edges, each black vertex of even degree contributes , and each white vertex also contributes . Therefore, the sum of the numbers on the edges in has the same parity as that of the number of black vertices of odd degree in . Thus, when asked about the set of the vertices of odd degree, we are ready. Conversely, for a question with a set other than , we cannot unambiguously restore the parity of the number of black vertices in and the lemma is proved.
It remains to count the number of cells with an odd number of adjacent cells in . Each cell that has no common point with the perimeter of has adjacent cells. The three cells on the perimeter, each of which is adjacent on the side of a corner cell in , have adjacent cells. Each cell with a side on the perimeter has adjacent cells, and each cell with a vertex (but not a side) on the perimeter (except the three mentioned above) has adjacent cells. Because each side of has at least one common point with cells, and each two sides have two common cells (as only one is of odd degree), the required number is .