Is it possible to fill the cells of a table of size $2019\times2019$ with pairwise distinct positive integers in such a way that in each rectangle of size $1\times2$ or $2\times1$ the larger number is divisible by the smaller one, and the ratio of the largest number in the table to the smallest one is at most $2019?$
Problem
Source: Kyiv mathematical festival 2019
Tags: Kyiv mathematical festival, combinatorics, number theory
19.05.2019 17:45
The answer is yes! I think that there are probably plenty of possible constructions, here is one. Let's let $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7.$ Let's index our table $a_{ij}$ for $1\le i,j \le 2019$ in the obvious way. First of all, observe that it suffices to fill the grid with positive rational numbers so that the conditions are satisfied, where $q_1 | q_2$ for $q_1, q_2 \in \mathbb{Q}^{+}$ if $\frac{q_2}{q_1} \in \mathbb{N}.$ This is because we can just scale the rationals by their collective common denominator in the end. With this in mind, let's define two sequences. For the first sequence $\{x_i\}$, we'll let $x_1 = 1$, and for $2 \le n \le 2019$ we will define our sequence by \[\displaystyle x_n = \left\{ \begin{array}{lr} \frac{x_{n-1}}{p_2} & \text{if}\ \ x_{n-1} > 1\\ x_{n-1} p_1 & \text{if}\ \ x_{n-1} \le 1 \end{array} \right.\]Define the sequence $\{y_i\}$ similarly by $y_1 = 1$ and using $p_4, p_3$ instead of $p_2, p_1$ in the above definition. With these two sequences defined, we're ready to construct our table. We claim that letting $a_{ij} = x_iy_j$ for all $1 \le i, j\le 2019$ is a valid construction. First of all, it's easy to see that no two different entries of $\{a_{ij}\}$ could be equal, since they must differ either in $v_2, v_3, v_5,$ or $v_7.$ The condition that one out of any two adjacent entries divides the other is also easily checked, since we always have that one of $x_{i-1}, x_i$ divides the other, for $2 \le i \le 2019$, and similarly for $y_{i-1}, y_i.$ Therefore, we only need to check that any two entries are within a factor of $2019$ of each other. Indeed, it's easily seen by induction that $x_i \in [\frac13, 2]$ and $y_i \in [\frac17, 5].$ Therefore, we always have that $\frac{1}{21} \le a_{ij} \le 10,$ for all $1 \le i,j \le 2019$. Therefore, since $\frac{10}{\frac{1}{21}} = 210 < 2019,$ we're done. $\square$