In each cell of $5 \times 5$ table there is one number from $1$ to $5$ such that every number occurs exactly once in every row and in every column. Number in one column is good positioned if following holds: - In every row, every number which is left from good positoned number is smaller than him, and every number which is right to him is greater than him, or vice versa. - In every column, every number which is above from good positoned number is smaller than him, and every number which is below to him is greater than him, or vice versa. What is maximal number of good positioned numbers that can occur in this table?
Problem
Source: Bosnia and Herzegovina Junior Balkan Mathematical Olympiad TST 2017
Tags: combinatorics, board, positioned, maximum
24.09.2019 07:10
Solution?
24.09.2019 14:44
It's $5$. This can be achieved as follows: $$1 4 2 3 5$$$$3 5 1 4 2$$$$2 1 3 5 4$$$$4 2 5 1 3$$$$5 3 4 2 1$$ Where the $1$s and $5$s in the corners, and the $3$ in the centre, are all good. Motivation for construction: the $1$s and $5$s are easy to make good, because they just have to be in the corner; then make the $3$ good, and it's easy to finish the table from there. We now show that this is maximal: A number $k$ can only be good if it is in either the $k$th or $(6-k)$th column, and the $k$th or $(6-k)$th row, because it needs $k-1$ numbers above or below it, and $k-1$ to the left or right. This means that only the following numbers can be good: The $1$ in the first column; the $2$ in the second column. The $1$ in the fifth column; the $2$ in the fourth column. The $3$ in the third row. The $4$ in the fourth column; the $5$ in the fifth column. The $4$ in the second column; the $5$ in the first column. Notice that I've paired most of these up; I'll now show that only one in each pair can be good, leaving only $5$ as the maximum. I'll show that the $2$ in the second column and the $1$ in the first column cannot both be good; the argument proceeds in the same way for the other pairs. If the $2$ in the second column is good, it must be in the second or fourth row and have a $1$ to its left. This means that the $1$ in the first column cannot be in the first or fifth row, so it cannot be good. Applying a similar argument for the other pairs, we see that only one in each pair can be good, and the four pairs and the $3$ in the centre give the only possibilities for a good number, so at most $5$ numbers can be good. As shown, this maximum can be achieved.