Let $n$ be a positive integer. A German set in an $n \times n$ square grid is a set of $n$ cells which contains exactly one cell in each row and column. Given a labelling of thecells with the integers from $1$ to $n^2$ using each integer exactly once, we say that an integer is a German product if it is the product of the labels of the cells in a German set. (a) Let $n=8$. Determine whether there exists a labelling of an $8 \times 8$ grid such that the following condition is fulfilled: The difference of any two German products is alwaysdivisible by $65$. (b) Let $n=10$. Determine whether there exists a labelling of a $10 \times 10$ grid such that the following condition is fulfilled: The difference of any two German products is always divisible by $101$.
Problem
Source: Baltic Way 2023/20
Tags: number theory
11.11.2023 20:41
a_507_bc wrote: Let $n$ be a positive integer. A German set in an $n \times n$ square grid is a set of $n$ cells which contains exactly one cell in each row and column. Given a labelling of thecells with the integers from $1$ to $n^2$ using each integer exactly once, we say that an integer is a German product if it is the product of the labels of the cells in a German set. (a) Let $n=8$. Determine whether there exists a labelling of an $8 \times 8$ grid such that the following condition is fulfilled: The difference of any two German products is alwaysdivisible by $65$. (b) Let $n=10$. Determine whether there exists a labelling of a $10 \times 10$ grid such that the following condition is fulfilled: The difference of any two German products is always divisible by $101$. (a) We have $65=5\cdot13$. In $\{1,2,\ldots,64\}$ there are $12$ intergers divisible by $5$ and $4$ integer divisible by. So there must be a German set with product divisible by $65$ and another German set with product not divisible by $13$. So there is no $(8\times8)$-grid satisfying the conditions. (b) $101$ is a prime. So there is a primitive root $g\pmod{101}$. Write $g^{10a+b}\pmod{101}$ in the cell in the $a$-th row and $b$-th coloum for $0\leq a,b\leq 9$. Since $g$ is a primitive root $\pmod{101}$ this covers all $100$ residue classes in $(\mathbb{Z}/101\mathbb{Z})^*$ The the product of any German set is $g^{(0+1+\ldots+9)(10a+b)}$. So the conditions are satisfied.
12.11.2023 03:20
Bro, at least change the numbers when you steal a problem... Serbia National Round 2010 P5 one of my favourite problems with primitive roots which I like to give in classes.
10.12.2023 22:07
Assassino9931 wrote: Bro, at least change the numbers when you steal a problem... Bro, at least be a bit more respectful with other members of the olympiad community! As is well-known, there are more math competitions than a single person (or even a single jury) can possibly know of. It will thus necessarily happen that a problem (particularly if it uses such a nice idea!) will be created independently over and over again. In this particular case, although I am not the original proposer, I can assure that you that neither the proposer nor any member of the jury was aware of the fact that this problem already appeared in another competition when it was selected! It also appears that no student in the competition was aware of this fact... So let us not accuse each other of "stealing" and rather enjoy the beautiful mathematics...