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]
Problem
Source: Dutch NMO 2020 p1
Tags: combinatorics
23.11.2020 23:34
473 158 926 has 3 circled numbers and 981 734 562 has 6 circled numbers
24.11.2020 08:01
RagvaloD wrote: 473 158 926 has 3 circled numbers and 981 734 562 has 6 circled numbers From here, it is clear that having 3 circled numbers is possible. But anything less than 3 is not possible because if we circle any 2 numbers, then we will be left with a row and a column each with no circled numbers. Since all the numbers in the grid are unique, thus this is not possible. Hence three is the minimum number of circles. I can't find a valid argument for the maximum. Any help will be appreciated!
24.11.2020 22:52
235 174 689 has 7 circled numbers Which is clearly the maximum since neither 1 nor 9 can be a circled number.
24.11.2020 22:55
Moreover a nice generalization could be: what is the min and max if for an $nxn$ square if we circled any median of a permutation of $\{1,2,\cdots,n\}$