A "Hishgad" lottery ticket contains the numbers $1$ to $mn$, arranged in some order in a table with $n$ rows and $m$ columns. It is known that the numbers in each row increase from left to right and the numbers in each column increase from top to bottom. An example for $n=3$ and $m=4$: [asy][asy] size(3cm); Label[][] numbers = {{"$1$", "$2$", "$3$", "$9$"}, {"$4$", "$6$", "$7$", "$10$"}, {"$5$", "$8$", "$11$", "$12$"}}; for (int i=0; i<5;++i) { draw((i,0)--(i,3)); } for (int i=0; i<4;++i) { draw((0,i)--(4,i)); } for (int i=0; i<4;++i){ for (int j=0; j<3;++j){ label(numbers[2-j][i], (i+0.5, j+0.5)); }} [/asy][/asy] When the ticket is bought the numbers are hidden, and one must "scratch" the ticket to reveal them. How many cells does it always suffice to reveal in order to determine the whole table with certainty?
Problem
Source: 2023 Grosman MO, P2
Tags: combinatorics, Info, grid
07.01.2024 16:40
bump this
07.01.2024 17:54
Well now I've figured it out.Trivial one.The answer is (m-1)(n-1)
25.02.2024 13:55
Cool problem. Yes $(n-1)(m-1)$ is necessary and sufficient. Label grid $(r,c)$ with rows $r=1 \ldots n$ and $c=1 \ldots m$ For sufficiency we can check each diagonal (excluding the corners) $r+c=k$ all squares on the diagonal except the upper right most. This is $(n-1)(m-1)$ squares checked, and clearly the remaining unknown numbers forms a $m+n-1$ L shape which is increasing left to right and then down, so we can determine those values as well. For necessity note that in each diagonal $x+y=k$ we can skip checking at most one square. It is easy to construct labelings such that for a given pair of squares in a given diagonal we can fill in the other squares in such a way that swapping the numbers in the pair is still a lottery ticket, so it would be impossible to determine those numbers if both are left uncovered.