In each cell of a chessboard with $2$ rows and $2019$ columns a real number is written so that: There are no two numbers written in the first row that are equal to each other. The numbers written in the second row coincide with (in some another order) the numbers written in the first row. The two numbers written in each column are different and they add up to a rational number. Determine the maximum quantity of irrational numbers that can be in the chessboard.
Problem
Source: Peruvian IMO TST 2019, P1
Tags: irrational number, combinatorics
18.02.2019 10:11
28.02.2019 03:37
$Answer: 4032$. So ($I_1$+$I_2$=$Q_1$) ($I_i$ is a i-irrational number) ($Q_i$ is a i-rational number) An example is The $1$° column is ($I_1$,$I_2$), $2$° column is ($I_2$,$I_1$), $3$° column is ($I_3$,$I_4$), $4$° column ($I_4$,$I_3$),......, $2015$° column is ($I_2015$,$I_2016$), $2016$° column ($I_2016$,$I_2016$), $2017$°column ($Q_1$,$Q_2$), $2018$°column ($Q_2$,$Q_3$), $2019$°column ($Q_3$,$Q_1$). And ($a$,$b$). $a$ in first row, $b$ in second row. It is only to prove that it does not meet 4033,4034, ...., 4038. And that proof I have a little confuse : /
04.01.2025 12:15
Solved with stillwater_25. We solve the problem generally for an $2\times n$ grid where $n\ge 2$. We claim that if $M(n)$ denotes the maximum number of irrational numbers that can be on the chessboard then, \[M(n)=\begin{cases}2n & 2\mid n \\ 2n-6 & 2\nmid n \end{cases}\]Case 1 : $2\mid n$. This case is easy. Let $n=2k$ for some positive integer $k$. Then, consider irrational numbers $0<a_1<a_2<\dots < a_k < \frac{1}{2}$. Assign $a_1,a_2,\dots, a_k , (1-a_1) , (1-a_2) , \dots , (1-a_k)$ from left to right of the top row of the board. Note that no two of these entries are the same since $a_i \ne a_j$ and $(1-a_i) \ne (1-a_j)$ for all $i\ne j$ and $a_i\ne (1-a_j)$ for any $i,j$ since $a_i < \frac{1}{2}$ and $(1-a_j) > \frac{1}{2}$. In the bottom row, fill every entry such that the sum of each column is $1$. This clearly validly fills the chessboard and we have a total of $2n$ irrational numbers. Case 2 : $2\nmid n$. Let an irrational cycle be a sequence of distinct irrationals $a_1\to a_2 \to \dots \to a_k \to a_1$ such that $a_i$ and $a_{i+1}$ are in the same column of our chessboard for all $1\le i \le k$ (and let $a_{k+1}=a_1$). We have the following fundamental result about irrational cycles. Claim : An irrational cycle must be of even length. Proof : Consider an irrational cycle of odd length $k$. Let $r_i=a_i+a_{i+1}$ for all $1\le i \le k$ (and let $a_{k+1}=a_1$). Note that these are all rational numbers by the third condition. With some calculation we arrive at, \[a_k = r_k - r_{k-1} + \dots - r_2 + a_1\]Thus, \[a_1=r_1-a_k = r_1 - r_k + r_{k-2} - \dots +r_2 - a_1\]But then, \[a_1=\frac{r_1 - r_k + r_{k-2} - \dots +r_2}{2}\]which is quite clearly rational! This is a clear contradiction, so no irrational cycle of odd length can exist, proving the claim. Now, consider the $2\times n$ board. The maximum irrational cycle size is $n-1$ since they must be even. But this is impossible since then the remaining two cells of the board are in the same column, and they must be the same (to satisfy the second condition) which is a contradiction. Thus the maximum irrational cycle length is $n-3$. Now, note that the board excluding the entries which are in the irrational cycle also satisfies all the desired conditions, and is of odd size. We continue likewise deleting irrational cycles, until we have an odd sized board with exactly one irrational cycle. If this board is of size $m$ then the irrational cycle is off size at most $m-3$ (and we have no irrationals outside this cycle) and thus we have atleast 6 entries which are rational, proving the bound. For the construction, simply do the construction similar to the even case on an $2\times n-3$ grid and then place the integers $2 , 3 , 4$ and $4 , 2 , 3$ in the top and bottom row for the remaining three columns.