Consider a chessboard that is infinite in all directions. Alex the T-rex wishes to place a positive integer in each square in such a way that: No two numbers are equal. If a number $m$ is placed on square $C$, then at least $k$ of the squares orthogonally adjacent to $C$ have a multiple of $m$ written on them. What is the greatest value of $k$ for which this is possible?
Problem
Source: Mexico National Olympiad Mock Exam 2021 P5
Tags: combinatorics
12.11.2021 07:22
The answer is $k = 2$. First, two adjacent squares can't both divide each other so $k \neq 4$. To show $k$ can't be $3$, consider a square with a number $a$ and say the number $ka$ is written next to it. Also WLOG let the number not divisible by $a$ adjacent to it be to its left. Then below $ka$, there must be a multiple of it, say its $akb$. But then the square to the left of this has to be a multiple of both $a$ and $akb$, so can't divide either of them. For $k = 2$, a construction is as follows. First place the numbers $1,2,4,8$ in a $2 \times 2$ square. I claim we can just keep adding a new row or column to the current rectangle while still maintaining the condition, which finishes. But this is easy, since pick the top right square and add a multiple of it to its right. Then below it, take a multiple of the product of numbers on the left and top(take the multiples big enough to ensure distinctness). This works. $\blacksquare$
12.11.2021 14:07
We prove that $k=2$.We prove that that $k$ cannot be $3$.Assume the contrary.Just choose any cell with say $m$ written on it and neighbours $a,b$,such that they form an L and $a,b>m$.Now,let $n$ be the other common neighbour of $a,b$.WLOG,$a>b$,now since $m<a$,so $n>a>b$ but ,then $n$ has atmost $2$ such neighbours,which is a contradiction. For the construction,start with a row,which extends infinitely right.,number it $1$.Then fill the $ith$ cell in the row with number $2.3^i$,with $i$,increasing right. Then add rows on top of it and for row $j$,fill it with numbers $2^j.3^i$,similarly.This clearly works as every number divides the number on top and right of it.
13.11.2021 08:53
Original (and harder) statement: Let $n$ be a positive integer. We say that the two points in $n$-dimensional Euclidean space with integer coordinates $(x_1,x_2,\dots,x_n)$ and $(y_1,y_2,\dots,y_n)$ are $\textit{adjacent}$ if and only if $$|x_1-y_1|+|x_2-y_2|+\dots+|x_n-y_n|=1.$$ Alex the T-rex wishes to place a positive integer in every point with integer coordinates in $n$-dimensional Euclidean space in such a way that: No two numbers are equal. If a number $m$ is placed on point $P$, then at least $k$ of the points adjacent to $P$ have a multiple of $m$ written on them. What is the greatest value of $k$ for which this is possible?