Given positive integers$ m,n$ such that $ m < n$. Integers $ 1,2,...,n^2$ are arranged in $ n \times n$ board. In each row, $ m$ largest number colored red. In each column $ m$ largest number colored blue. Find the minimum number of cells such that colored both red and blue.
Problem
Source: Day 2 Poblem 2
Tags: Gauss, combinatorics proposed, combinatorics
Little Gauss
05.06.2008 15:42
??? I think the answer is $ m^{2}$, which can occur in the case if you simply write down $ 1\sim n^{2}$. Pick up and mark the largest number in the board. Do this until there exist a row or column which has $ m$ marked number. Then erase other numbers in that row/column. We call this row or column is full. Now mark numbers same way. When a row or column become having $ m$ marked numbers, erase others in the row or column. Do this until we have $ m$ full row or $ m$ full column. Then all marked number would be points colored both red and blue. If the process was ended, there are $ m$ full row/column, always we have least $ m^{2}$ marked points.
jgnr
06.06.2008 12:06
Isn't it too trivial?
Aerxis
28.08.2010 05:47
Little Gauss, apply your method with m=2 to this board: 5, 4, 3 7, 8, 9 6, 1, 2
Dumel
28.08.2010 21:48
it becomes easy when we notice that the number of cells colored red and blue doesn't change, when we exchange the numbers k and k+1