Let $m,n > 2$ be even integers. Consider a board of size $m \times n$ whose every cell is colored either black or white. The Guesser does not see the coloring of the board but may ask the Oracle some questions about it. In particular, she may inquire about two adjacent cells (sharing an edge) and the Oracle discloses whether the two adjacent cells have the same color or not. The Guesser eventually wants to find the parity of the number of adjacent cell-pairs whose colors are different. What is the minimum number of inquiries the Guesser needs to make so that she is guaranteed to find her answer?(Czech Republic)
Problem
Source: Czech-Polish-Slovak Match 2016,P2,day 1
Tags: combinatorics
ThE-dArK-lOrD
02.11.2017 17:42
We color the boundary of $m\times n$ board red. Denote a score to each cell of the $m\times n$ boards by one, if the color of that cell is black, and by zero, if the color of that cell is white. The Oracle knows all the score of every cell. Note that the information the Oracle provides to the Guesser in each inquiry is $u+v \pmod{2}$ where $u$ and $v$ are the scores of two adjacent cells the Guesser chose, and we denote that number to be the score of the common edge of $u$ and $v$. The Guesser wants to compute the parity of the sum of the score of every possible common edge. Easy to see that it's enough for the Guesser to compute the parity of the sum of the score of every cell with odd number of non-red edges. These cells can be partitioned to disjoint non-adjacent two $1\times (n-2)$ rectangles and two $1\times (m-2)$ rectangles. Since $n-2$ and $m-2$ are even, we can partition each such rectangle to some dominoes and the Guesser can ask the sum of scores of cells in each domino. Hence, the Guesser can complete her goal with $\frac{(m-2)+(n-2)+(m-2)+(n-2)}{2}=m+n-4$ inquiries. Also, if there's some way to complete the goal with less than that amount of inquiries, there will be at least one cell in those $4$ rectangles that she has no information, so the score of that cell can be anything, and so does the sum of the scores she wanted to compute. Finally, we conclude that the minimum number of inquiries she needs to make to complete her goal is $m+n-4$.
parmenides51
11.12.2022 19:56
Let $m,n > 2$ be even integers. Consider a board of size $m \times n$ whose every cell is colored either black or white. The Guesser does not see the coloring of the board but may ask the Oracle some questions about it. In particular, she may inquire about two adjacent cells (sharing an edge) and the Oracle discloses whether the two adjacent cells have the same color or not. The Guesser eventually wants to find the parity of the number of adjacent cell-pairs whose colors are different. What is the minimum number of inquiries the Guesser needs to make so that she is guaranteed to find her answer? (Czech Republic)