A rectangular table $ 9$ rows $ \times$ $ 2008$ columns is fulfilled with numbers $ 1$, $ 2$, ...,$ 2008$ in a such way that each number appears exactly $ 9$ times in table and difference between any two numbers from same column is not greater than $ 3$. What is maximum value of minimum sum in column (with minimal sum)?
Problem
Source: Federation of Bosnia, 3. and 4. Grades 2008.
Tags: floor function, combinatorics proposed, combinatorics
mahanmath
30.10.2009 17:30
Could someone help me with this problem ? I don`t know how start solving !!! (sorry for my bad English)
mahanmath
30.10.2009 19:05
Do you have any idea?
mahanmath
30.10.2009 23:17
I know that Dirichlet Principle hepls but How ???
mavropnevma
31.10.2009 08:30
We will denote by $ \sigma(c)$ the sum of the entries of column $ c$. We claim $ \max \min \sigma(c) = 24$, realized for example by the table with three columns equal to $ (1,1,1,3,3,3,4,4,4)$ (having $ \sigma(c) = 24$), one $ (2,2,2,2,2,5,5,5,5)$, one $ (2,2,2,2,5,5,5,5,5)$, and the rest $ (n,n,n,n,n,n,n,n,n)$, for $ 6\leq n\leq N=2008$. The $ k$ columns contaiming an entry equal to $ 1$ can only have their entries from the set $ \{1,2,3,4\}$. Since there are only $ 9\cdot 4$ such values available, it means that $ 9k \leq 9\cdot 4$, hence $ k\leq 4$. If $ k=1$, that column has $ \sigma(c_1) = 9\cdot 1 < 24$; If $ k=2$, those columns have $ \sigma(c_1) + \sigma(c_2) \leq 9\cdot 1 + 9\cdot 4 = 45$, hence one of them has $ \sigma(c) \leq \lfloor 45/2 \rfloor = 22 < 24$; If $ k=4$, those columns have $ \sigma(c_1) + \sigma(c_2) + \sigma(c_3) + \sigma(c_4) = 9\cdot 1 + 9\cdot 2 + 9\cdot 3 + 9\cdot 4 = 90$, hence one of them has $ \sigma(c) \leq \lfloor 90/4 \rfloor = 22 < 24$; If $ k=3$, finally, those columns have $ \sigma(c_1) + \sigma(c_2) + \sigma(c_3) \leq 9\cdot 1 + 9\cdot 3 + 9\cdot 4 = 72$, hence one of them has $ \sigma(c) \leq \lfloor 72/3 \rfloor = 24$. A model has been presented with the claim above.
mahanmath
31.10.2009 18:58
Nice !! thanks .