Baltic Way 2023 Shortlist

a. No, there is no such labelling. On the contrary, we show that for every labelling there exist two rook products whose difference is not divisible by $65$. Suppose that an $8\times 8$ chessboard is labelled with the numbers $1,2,\dots ,64$ such that no number is used twice. We can construct a rook product that is divisible by $13$ by placing a rook on the square with the label $13$ and the other seven rooks non attackingly, but otherwise arbitrarily. We can construct a rook product that is not divisible by $13$ as follows. Notice that only four labels are divisible by $13$, namely $13,26,39$, and $52$. These four labels are located in at most four rows; we denote the index set of these rows $R\subseteq \{1,8\}$. Similarly, there are at least four columns that do not contain any of these four labels; we denote the index set of these columns $C\subseteq \{1,8\}$. Since $|R|\le |C|$ it is possible to place non attacking rooks in rows $R$ using only columns from $C$. The remaining rooks are placed in the remaining rows non attackingly, but otherwise arbitrarily. The resulting rook product is not divisible by $13$ since the rooks avoid the squares whose labels are divisible by $13$.

The difference of the two rook products is not divisible by $13$, since one rook product is divisible by $13$ whereas the other one is not. Hence the difference is not divisible by $65$.

b. Yes, there is such a labelling. For $k\in [0,99]$ we define $a_k=2^k(\mathrm{mod}101)$; in other words, $a_k$ is the remainder of $2^k$ when divided by $101$. Note that $a_k\ne 0$ since no power of $2$ is divisible by $101$. Hence $1\le a_k\le 100$ for all $k\in [0,99]$.

Since $r<s$ and $s$ is the smallest positive integer with $2^s\equiv 1(\mathrm{mod}101)$, we must have $r=0$. In other words, $100$ is divisible by $s$; in other words, $s$ is a divisor of $100$. We claim that $s=100$. If this was not the case, we would have $s|20$ or $s|50$, which implies that $2^{20}\equiv 1(\mathrm{mod}101)$ or $2^{50}\equiv 1(\mathrm{mod}101)$. However $2^{10}=1024\equiv 14(\mathrm{mod}101)$, so that $2^{20}\equiv 14^2\equiv 196\equiv -6\not\equiv 1(\mathrm{mod}101)$ and $2^{50}\equiv (2^{20}{)}^2\cdot 2^{10}\equiv (-6{)}^2\cdot 14\equiv 504\equiv -1\not\equiv 1(\mathrm{mod}101)$. Now assume that $k,l\in [0,99]$ are positive integers with $k>l$ and $a_k=a_l$. Then we have $2^k\equiv 2^l(\mathrm{mod}101)$. We conclude that $0\equiv 2^k-2^l\equiv 2^l\cdot (2^{k-l}-1)(\mathrm{mod}101)$. Since $2^l$ and $101$ are coprime, it follows that $2^{k-l}-1\equiv 0(\mathrm{mod}101)$ and $2^{k-l}\equiv 1(\mathrm{mod}101)$. This cannot be true, since $k-l\in [1,99]$, but $s=100$ is the smallest positive integer with $2^s\equiv 1(\mathrm{mod}101)$. Hence $a_k\ne a_l$. We conclude that the numbers $a_k$ with $k\in [0,99]$ are a hundred pairwise different numbers from the set $[1,100]$, hence they are a permutation of the set $[1,100]$ as it was required.

---

Alternative solution.

Definition: Let $p$ be a prime. Consider an $n\times n$-square of elements $a_{i,j}\in {\mathbb{F}}_p^{\ast }$ (for $i,j=1,\dots ,n$), which are not necessarily distinct. We call it rooky, if all its rook-products are equal as elements in ${\mathbb{F}}_p^{\ast }$. We will provide a classification of all rooky squares. Of course, most of this is not necessary when writing down a solution to the given problem, but it may still be interesting...

Lemma: A square is rooky if and only if for all $i$, $j$, $k$, $\ell$: $$a_{i,j}\cdot a_{k,\ell }=a_{i,\ell }\cdot a_{k,j}(1)$$ Proof. If we swap the rows of two rooks and keep their columns, it turns one valid rook formation into another. When comparing their rook products, we can ignore all $n-2$ values of rooks that were not moved. The remaining values are $a_{i,j}\cdot a_{k,\ell }$ resp. $a_{i,\ell }\cdot a_{k,j}$ for certain $i$, $j$, $k$, $\ell$. This gives equality (1) for rooky squares. Conversely assume that (1) holds. Then we have to compare two arbitrary rook products. But they can be transformed into each other by a sequence of several swaps of two rooks. Due to (1) the rook product does not change at any of these steps, so the rook products of the original configurations are the same as well. $\square$

Lemma: A rooky square is uniquely determined by the elements of its first row and first column. Proof. Indeed the previous lemma implies that $$a_{i,j}\cdot a_{1,1}=a_{i,1}\cdot a_{1,j}$$ which determines $a_{i,j}$ uniquely because $a_{1,1}$ is a unit. $\square$

One can actually prove directly that the square obtained that way is rooky, but it is simpler to continue directly to

Proposition: Let ${\lambda }_i\in {\mathbb{F}}_p^{\ast }$ ($i=1,\dots ,n$) and ${\mu }_j\in {\mathbb{F}}_p^{\ast }$ ($j=1,\dots ,n$) be arbitrary elements. Then the square with $$a_{i,j}={\lambda }_i\cdot {\mu }_j$$ is rooky. Moreover any rooky square can be obtained this way.

Let us prove the converse: By the previous lemma, it suffices to find ${\lambda }_i$s and ${\mu }_j$s that recreate the values of the first row and column. For this simply set ${\lambda }_i=a_{i,1}$ and ${\mu }_j=\frac{a_{1,j}}{a_{1,1}}$. $\square$

Proposition: For any prime $p>n^2$, there exists a rooky square with only distinct elements. Proof. Choose any primitive root $\alpha \in {\mathbb{F}}_p^{\ast }$. Then set ${\lambda }_i={\alpha }^{i-1}$, ${\mu }_j={\alpha }^{n\cdot (j-1)}$ and $a_{i,j}={\lambda }_i\cdot {\mu }_j={\alpha }^{i-1+n\cdot (j-1)}$. This provides indeed a rooky square. The values in the square are ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{n^2-1}$. As we have chosen a primitive root, these are all distinct. $\square$

For $n=10$, $p=101$ and $\alpha =2$, this reproduces exactly the construction given in the previous solution.

Proof. The square with $a_{i,j}={\lambda }_i\cdot {\mu }_j$ is rooky, because any rook product has the value $$\prod _i{\lambda }_i\cdot \prod _j{\mu }_j.$$