4. A positive integer n is given.Find the smallest $k$ such that we can fill a $3*k$ gird with non-negative integers such that: $\newline$ $i$) Sum of the numbers in each column is $n$. $ii$) Each of the numbers $0,1,\dots,n$ appears at least once in each row.
Problem
Source: 2023 Iran MO
Tags: combinatorics
18.05.2023 04:44
The sum of all the numbers in the grid is $n(k)$ and it is at least $0+1+2+...+n=\frac{n(n+1)}{2}$, so we have $k \geq \frac{(n+1)}{2}$ So we have $2$ cases depending on the parity of $n$. For each column we will denote the three numbers on it as $(a, b, c)$ Case 1) if $n$ is even, let $n=2p$ $\rightarrow k \geq \frac{(2p+1)}{2}, \rightarrow k \geq p+1$ so we will take this numbers in the $p+1$ columns $(2p, 0, 0); (2p-1, 1, 0);(2p-2, 2, 0);...;(p, p, 0)$ Case 2) if $n$ is odd, let $n=2p+1$ $\rightarrow k \geq \frac{(2p+2)}{2}, \rightarrow k \geq p+1$ so we will take this numbers in the $p+1$ columns $(2p+1, 0, 0); (2p, 1, 0);(2p-1, 2, 0);...;(p+1, p, 0)$
18.05.2023 16:31
Answer: $\left\lceil\frac{3}{2}(n+1)\right\rceil$. Bound: Consider such a $3\times k$ grid. Let $S$ be the sum of all numbers in the table. The sum of numbers in each row is at least $0+1+2+...+n=\frac{n(n+1)}{2}$. Hence $S\ge \frac{3n(n+1)}{2}$. On the other hand, condition $i)$ implies $S=kn$. Hence $kn\ge\frac{3n(n+1)}{2}$ so $k\ge\frac{3}{2}(n+1)$. Construction: We consider two cases, depending on the parity of $n$. Case 1. $n$ is odd. We will take the union of columns $(0,a,n-a);(n-a,0,a);(a,n-a,0)$, $0\le a\le\frac{n-1}{2}$. Case 2. $n$ is even. We will take the union of columns $(0,a,n-a);(n-a,0,a);(a,n-a,0)$, $0\le a\le\frac{n}{2}-1$ as well as the columns $\left(0,\frac{n}{2},\frac{n}{2}\right);\left(\frac{n}{2},\frac{n}{2},0\right)$.
01.05.2024 11:35
Surprisingly very easy. We claim that the answer is $k=\left \lceil \frac{3(n+1)}{2} \right \rceil$ for all positive integers $n$. We start off by proving the bound. Claim : If a $3 \times k$ grid can be filled as desired, then $k\geq \frac{3(n+1)}{2}$ Proof : Since each column has sum $n$, the sum of all entries of the grid is simply $nk$. Further, since each row has the numbers $1,2,\dots,n$ appearing atleast once, the sum of a row is atleast $\frac{n(n+1)}{2}$. Thus, \[\frac{3n(n+1)}{2} \leq S = nk \implies k \geq \frac{3(n+1)}{2}\]as claimed. Now, we provide a construction for which this $k$ is achievable. For odd $n$, the claimed minimum is $\frac{3(n+1)}{2}$ which is clearly divisible by 3. Thus, we partition our $3 \times \frac{3(n+1)}{2}$ gird into multiple $3 \times 3$ grids, placed side by side. Then, in the $(1,1) , (2,3)$ and $(3,2)$ squares of each of these smaller squares, we place zeroes. Then, in the $i^{\text{th}}$ small square, we place $i-1$ in the $(1,2) , (2,1)$ and $(3,3)$ squares while we place $n-i+1$ in the remaining 3 squares. Thus, clearly each column sums to $n$ and each of the numbers $0,1,2,\dots,n$ is used atleast once in each row by the nature of the construction. When $n$ is even, we do the exact same construction for all $i< \frac{n}{2}$ which leaves two columns unfilled. For these two columns, we place $\frac{n}{2}$, in the second and third rows of the first column and in the one before the last column and first and second rows of the last column which also satisfies all the desired condition, which finishes the construction.
28.08.2024 18:20
The minimum $k$ is $k=\lceil \frac{3(n+1)}{2} \rceil $ First, sum of numbers in every column in $n$ As there are $k$ columns such so sum of all numbers would be $kn$. Now every row contains each number from $0$ to $n$ atleast once. So sum of every number $\geq \frac{3n(n+1)}{2}$[as there are 3 rows] So now it is trivial to show $k \geq \frac{3(n+1)}{2}$ Now we will show $k=\lceil \frac{3(n+1)}{2} \rceil$ works. It is trivial it works for $n=1,k=3$ and $n=2,k=5$ Now we assume it is true for $n=m,k_m= \lceil \frac{3(m+1)}{2} \rceil$ We will prove for $n=m+2,k_{m+2}=\lceil \frac{3(m+3)}{2} \rceil$ Now suppose for $n=m$ such $3 \times k_m$ configuration is $C$ Denote a $group$ $(p,q,r)$ such $p,q,r$ in the same column of $C$ with $p,q,r$ being on the $1st,2nd$ and $3rd$ row respectively. Now there exists $groups$ $(m,0,0),(0,m,0),(0,0,m)$ in $C$. Now add $1$ to all the numbers in the $first$ and $2nd$ row unless any one of the numbers are part these $groups$.[If there is $(0,m,0)$ we will not add 1 to $0$ of the first row] Now for the $groups$ make them into these $(m+1,1,0),(0,m+1,1),(1,0,m+1)$ Let this new configuration be $D$. Now Note that in $D$ sum of numbers of every column is $m+2$ and all numbers of $0$ to $m+1$ exists in every column and the numbers of column is same as $C$ Now note that $k_{m+2}=k_m+3$ So $3 \times k_{m+2}$ box can be divided into two parts $A$ and $B$ such $A$ is $3 \times k_m$ and $B$ is $3 \times 3$ boxes. Let $A$ be $D$ and put entries into $B$ in these way $(0,0,m+2),(0,m+2,0),(m+2,0,0)$ Which works [Proved by $Induction$] $\square$