5
$\begingroup$

Take an $m \times n$ checkered board and one-at-a-time add a piece to an empty square. At what point are you guaranteed to have an $s \times t$ sub-board where all of its squares are filled?

Here I don't demand that the $s$ rows or $t$ columns be adjacent. Any selection of $s$ rows and $t$ creates a sub-board -- namely, the $s \cdot t$ intersection squares.

Thanks!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ A good answer to this question, when restricted to the (s,t)=(2,2) case, would also afford an answer to this recent MO Question on Finite Projective Planes $\endgroup$
    – ARupinski
    Commented Apr 5, 2015 at 22:27
  • $\begingroup$ @ARupinski -- Thanks! I wonder if an upper bound could be obtained for my question using some theorems of projective planes or design theory, like was the case for $s=t=2$, as your link shows. $\endgroup$
    – JC1111523
    Commented Apr 5, 2015 at 22:52

1 Answer 1

Reset to default
2
$\begingroup$

This is likely useless, but for $n{=}m{=}8$, an $8 \times 8$ chessboard, and $s{=}t{=}2$, a $2 \times 2$ subboard, with $k$ pieces added randomly (the horizontal axis), the probability (vertical axis) of a filled $2 \times 2$ subboard occuring somewhere on the $8 \times 8$ chessboard, in $100$ random trials, was:

          SubMatricesn8s2
By $k{=}21$, the observed frequency is $97$%. More precisely, here are the counts out of $100$: $$ \left( \begin{array}{cccccccccccccccc cccccccc} 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ 1 & 2 & 2 & 8 & 12 & 22 & 21 & 38 & 43 & 57 & 63 & 68 & 84 & 91 & 95 & 95 & 97 & 98 & 98 & 99 \\ \end{array} \right) \;. $$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .