A rectangular array has $9$ rows and $2004$ columns.

In the $9 \times 2004$ cells of the table we place the numbers from $1$ to $2004$, each $9$ times.

And we do this in such a way that two numbers, which stand in exactly the same column are differ at most by $3$.

Find the smallest possible sum of all numbers in the first row.

My attempt :

Let $a_1, a_2, \ldots, a_{2004}$ be numbers in the first row.

WLOG, $a_1 \leq a_2 \leq \ldots \leq a_{2004}$.

Since the two numbers in the same column are differ by at most $3$, so

$a_1 \geq 1, a_2 \geq 1, a_3 \geq 1$

$a_{2004} \geq 2004-3 = 2001$.

Since $2004$ appears in at least one column,

suppose there exists one column that $2004$ appears 9 times, then $a_{2004} = 2004$.

Otherwise, $2004$ appears in the the same column with $a_i$, where $i \not= 2004$,

so $a_i \geq 2004-3 = 2001$, then $a_{2003} \geq 2001$

enter image description here


I suspect the answer is $2,006,004$.

If all rows were the same and consisted of the numbers $1,2,3,4,\ldots, 2004$ we would have an upper bound for the sum of the first row, which would be $2,009,010$. So we are looking for a smaller number.

If a column contains a $1$, the only other numbers it is possible to have in that column are $1,2,3,4$. We want as many $1$'s as possible in the first row, so how many are possible?

enter image description here

In the table above we see that we have four $1$'s in the first row and that all the $1$'s, $2$'s, $3$'s and $4$'s have been used in the first $4$ columns. It is clear that it is not possible to have more $1$'s in the first row (or any row). It is also clear that the sum of the first four numbers in any row will be greater than or equal to the sum in row one.

We now do the same distribution for the next lowest available number, which is $5$. And then for the next lowest available number, which is $9$, etc. The end result (using this strategy) is that the minimum sum of row one is $$\sum_{i=1}^{2004}{i}-6 \cdot \frac{2004}{4} = 2,006,004$$

  • $\begingroup$ Thank you for your help, Jens. Please see my construction above. I fill the number from the rightmost lowest cell and get the smaller sum, 2,005,004 but still get stuck on how to prove. $\endgroup$ – carat Nov 7 '17 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.