Competition problem — Combinatorics

Library / /16 of 24

Combinatorics Difficulty 6.8 National olympiad Prove it Netherlands

Daan distributes the numbers $1$ to $9$ over the nine squares of a $3 \times 3$ table (each square receives exactly one number). Then, in each row, Daan circles the median number (the number that is neither the smallest nor the largest of the three). For example, if the numbers $8$ , $1$ , and $2$ are in one row, he circles the number $2$ . He does the same for each column and each of the two diagonals. If a number is already circled, he does not circle it again.

He calls the result of this process a *median table*. Above, you can see a median table that has $5$ circled numbers.

a. What is the smallest possible number of circled numbers in a median table?
*Prove that a smaller number is not possible and give an example in which a minimum number of numbers is circled.*

b. What is the largest possible number of circled numbers in a median table?
*Prove that a larger number is not possible and give an example in which a maximum number of numbers is circled.*

Solution

a. The smallest possible number of circled numbers is $3$ . Fewer than $3$ is not possible since in each row at least one number is circled (and these are three different numbers).

On the right, a median table is shown in which only $3$ numbers are circled. In the rows, the numbers $7$ , $5$ , $3$ are circled, in the columns the numbers $3$ , $5$ , $7$ , and on the diagonals the numbers $5$ and $5$ . Together, these are three different numbers: $3$ , $5$ , and $7$ .

b. The largest possible number of circled numbers is $7$ . More than $7$ is not possible, since the numbers $9$ and $1$ are never circled, hence no more than $9 - 2 = 7$ numbers are circled.

On the right, a median table is shown in which $7$ numbers are circled. In the rows, the numbers $2$ , $6$ , $8$ are circled, in the columns the numbers $7$ , $5$ , $3$ , and on the diagonals the numbers $4$ and $5$ . Together, these are the numbers $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ .

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.