Maths Olympiad Prep

Library / /12 of 14

Combinatorics Difficulty 6.3 National olympiad Prove it Bulgaria

Let m>1m > 1 and n>1n > 1 be odd integers. Distinct real numbers are written in the cells of a table of mm rows and nn columns. A number is called good if:
1. it is the largest in its row (column);
2. it is the middle number of its column (row).
What is the maximal number of good numbers?

Solution

Let NcN_c be the set of good numbers that are largest in their column and middle in their row. Since no two of these numbers belong to one and the same row we have Ncm|N_c| \le m. Denote by aa the largest element of NcN_c and let a1,a2,,an12a_1, a_2, \dots, a_{\frac{n-1}{2}} be the numbers in the row of aa that are greater than aa. It is clear that there are no elements from NcN_c in the columns of a1,a2,,an12a_1, a_2, \dots, a_{\frac{n-1}{2}}. Since there is at most one element of NcN_c in every column it follows that Ncn+12|N_c| \le \frac{n+1}{2}. Thus,
Ncmin{m,n+12}. N_c \le \min \left\{ m, \frac{n+1}{2} \right\}.
Analogously we obtain that the number of good numbers that are largest in their rows is at most min{m,n+12}+min{n,m+12}\min\left\{m, \frac{n+1}{2}\right\} + \min\left\{n, \frac{m+1}{2}\right\}. We shall show that for every odd m>1m > 1 and n>1n > 1 there exists a table such that the number of good numbers equals min{m,n+12}+min{n,m+12}\min\left\{m, \frac{n+1}{2}\right\} + \min\left\{n, \frac{m+1}{2}\right\}.

1. If mnm \neq n without loss of generality assume that 1<m<n1 < m < n. Mark the cells of the table by the digits 1, 2, 3, 4 and 5 as shown on the figure. Next, fill in the cells by writing consecutively the numbers 1, 2, 3, ..., mnmn, starting with the cells marked by 1, then by 2 and so on. All numbers written in the cells marked by 2 or 4 are good. Their number equals:
Figure 1
min{m,n+12}+m+12=min{m,n+12}+min{n,m+12}. \min \left\{ m, \frac{n+1}{2} \right\} + \frac{m+1}{2} = \min \left\{ m, \frac{n+1}{2} \right\} + \min \left\{ n, \frac{m+1}{2} \right\}.

2. Let m=nm = n and 3<m3 < m. As in 1. we fill the following table. The good numbers are again in cells marked by 2 or 4. Their number equals:
Figure 2
n12+n12+2=n+1 \frac{n-1}{2} + \frac{n-1}{2} + 2 = n + 1

n12 \frac{n-1}{2}
3. If m=n=3m = n = 3, then the table (5,6,7 and 8 are good) shows that the number of good numbers is 4 and 4=22=2min{3,3+12}4 = 2 \cdot 2 = 2 \min \left\{ 3, \frac{3+1}{2} \right\}.

<table>
<tr><td>1</td><td>7</td><td>9</td></tr>
<tr><td>2</td><td>6</td><td>4</td></tr>
<tr><td>5</td><td>3</td><td>8</td></tr>
</table>

Answer: min{n,n+12}+min{n,n+12}. \text{Answer: } \min \left\{ n, \frac{n+1}{2} \right\} + \min \left\{ n, \frac{n+1}{2} \right\}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.