Bengt wants to put out crosses and rings in the squares of an $n \times n$-square, so that it is exactly one ring and exactly one cross in each row and in each column, and no more than one symbol in each box. Mona wants to stop him by setting a number in advance ban on crosses and a number of bans on rings, maximum one ban in each square. She want to use as few bans as possible of each variety. To succeed in preventing Bengt, how many prohibitions she needs to use the least of the kind of prohibitions she uses the most of?
Problem
Source: 2022 Swedish Mathematical Competition p6
Tags: combinatorics, combinatorial geometry
29.07.2024 17:20
Claim 1. Mona cannot prevent Bengt if she has at most $n-2$ prohibitions of each kind. Proof. Assume the contrary. Colour the $n \times n$-board with colours $1,2, \ldots, n$ such that square $(i,j)$, where $1 \leq i \leq n$ and $1 \leq j \leq n$, has the same colour as the remainder when $i+j-1$ is divided by $n$. Note that by construction, each row and column contain exactly one of every colour and the board contains exactly $n$ squares of each colour. For brevity, call such a set of $n$ squares good if all the squares have the colour. Since Mona is at disposal at most $n-2$ prohibitions of each kind, then she can block at most $n-2$ different good sets with rings and at most $n-2$ different good sets with crosses, thus leaving at least two goods sets $A$ and $B$ such that $A$ is free from cross-prohibitions and $B$ is free from ring-prohibitions. In other words, Bengt can place crosses in $A$ and rings in $B$, which means Mona has failed her goal. The claim is proven. This means that Mona has to use at least $n-1$ prohibitions of at least one of the two kinds, ie. we have achieved a lower bound of $n-1$. Claim 2. Using $n-1$ of each prohibitions is sufficient. Proof. An example (among many) which supports this claim is when Mona places $n-1$ prohibitions against rings in the topmost row, ignoring the first square, and $n-1$ prohibitions against crosses in the leftmost column, ignoring the first square. Hence the minimum is $n-1$.