41st Balkan Mathematical Olympiad

The minimal value of $k$ with this property is $n^2$. We first show that in order for Florian to be able to deduce the entire tiling, we must have $k\ge n^2$. If Julia picks an independent tiling on each of $n^2$ disjoint $2\times 2$ regions, then Florian needs to reveal at least one domino from each region to deduce the entire tiling. Hence $k\ge n^2$.

Now colour the squares of the board with 4 different colours, such that the colouring is periodic with period 2 squares in both horizontal and vertical direction. We show that if Florian reveals the dominos covering the $n^2$ squares of one colour class, then there is at most one tiling of the board that contains this arrangement of revealed dominos.

Let red be one of the 4 colours and assume that we have two distinct tilings $A$ and $B$ of the board that agree on all the dominos covering a red square. We call a square of the board augmented if it is covered in a different way by $A$ and $B$. Given an augmented square $s$, let $a(s)$ and $b(s)$ be the two squares covered by the same domino in the tiling $A$ and $B$, respectively. By definition, we have $a(s)\ne b(s)$ and $a(s)$ and $b(s)$ must both be augmented as well. Repeating this argument, we find distinct augmented squares $s_1,s_2,s_3,\dots ,s_m$ with $$(a(s_k),b(s_k))=(s_{k+1},s_{k-1}),$$ where indices are taken modulo $m$. Hence, there is a closed path $P$ of orthogonally neighbouring squares that does not contain a red square and that is tiled by the restriction of both tilings $A$ and $B$.

Now, since the tilings $A$ and $B$ tile the path $P$, they must also tile the odd sized region enclosed by $P$. This is impossible since every domino covers exactly 2 squares, contradicting our initial assumption. We conclude that if two tilings agree on the red squares, they must in fact be the same tiling. Hence, if Florian knows how the red squares are tiled, there is a unique way to complete this tiling to the entire board, which he can deduce by searching though all the finitely many tilings of the board.