Problem

Source: Dutch NMO 2020 p1

Tags: combinatorics



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. [asy][asy] unitsize (0.8 cm); int i; for (i = 0; i <= 3; ++i) { draw((0,i)--(3,i)); draw((i,0)--(i,3)); } draw(Circle((0.5,2.5),0.3)); draw(Circle((2.5,2.5),0.3)); draw(Circle((1.5,1.5),0.3)); draw(Circle((2.5,1.5),0.3)); draw(Circle((1.5,0.5),0.3)); label("$8$", (0.5,2.5)); label("$1$", (1.5,2.5)); label("$2$", (2.5,2.5)); label("$7$", (0.5,1.5)); label("$6$", (1.5,1.5)); label("$3$", (2.5,1.5)); label("$9$", (0.5,0.5)); label("$5$", (1.5,0.5)); label("$4$", (2.5,0.5)); [/asy][/asy]