Let $d \in \mathbb{N}$. For simplicity, let's assume that $d$ is an integer multiple of $4$. Now, suppose that we have a large square, made up of $d \times d$ smaller squares. In addition, suppose that every smaller square is either empty, or marked by an X. For example, if $d = 8$, we could have something as follows: $$\begin{array}{c|cccccccc|} &1&2&3&4&5&6&7&8\\\hline 1&×&&&×&&&&\\\hline 2&×&×&&&×&&&\\\hline 3&&×&×&&&×&&\\\hline 4&&&×&×&&&×&\\\hline 5&&&&×&×&&&×\\\hline 6&&&&&×&×&&\\\hline 7&×&&&&&×&×&\\\hline 8&&×&&&&&×&×\\\hline \end{array} $$

Now, suppose that we select $d'$ rows and columns of the larger square, where $0 < d' < d$. The square obtained by removing all the other, non-selected, rows and columns from the larger square, we refer to as a subsquare. So, for example, if we select rows $1$ and $7$, and columns $1$ and $4$, we obtain the following subsquare of dimensions $2 \times 2$: $$\begin{array}{c|cc|} &1&2\\\hline 1&×&×\\\hline 2&×&\\\hline \end{array} $$

Finally, let's refer to a square that is completely filled with X's as a completely marked square.

Question 1: How many squares in a $d \times d$ square have to be marked, in order to ensure that there is a completely marked subsquare of dimensions $d/4 \times d/4$?

Question 2: If question 1 cannot be solved easily, how tight can we upper bound the number of marked squares required in a $d \times d$ square in order to ensure that there is a completely marked subsquare of dimensions $d/4 \times d/4$?

If I'm not mistaken the above $8 \times 8$ example does not have a completely marked $2 \times 2$ marked subsquare. As there are $22$ marked squares in this example, we find that when $d = 8$, we must have at least $23$ marked squares in order to ensure that there is a $2 \times 2$ completely marked subsquare.

My attempts: I didn't get all that far myself. Obviously, if there are more than $d^2-3d/4$ squares marked, there are $d/4$ rows and columns that are completely marked, and hence their intersection trivially is completely marked too. I do not have the illusion that this bound is tight, but I have no idea how to proceed from here in order to produce lower upper bounds on the number of squares that is necessary. I would really appreciate it if someone could give me a push into the right direction.

  • $\begingroup$ As a start, for 8x8 example, notice that a minimum of 9 marked squares guarantees the existence of at least two rows with marked squares in the same column. $\endgroup$ – rsadhvika Mar 10 '18 at 12:56

Suppose the $8\times8$ square has 26 squares marked.
The most even spread is six rows of three and two rows of four.
Each row of three crosses contains ${3\choose2}=3$ pairs of crosses, and the rows with four crosses contains six pairs each. The total number of these pairs is $6\times3+2\times6=30$.
There are only ${8\choose2}=28$ pairs of columns, so one of these pairs of columns appears twice, and a rectangle is present with all four corners marked.

Suppose the $12\times12$ square has 85 squares marked.
The most even spread is 11 rows of 7 and 1 row of 8. There are $11{7\choose3}+1{8\choose3}=441$ trios, spread around ${12\choose3}=220$ column trios. So one column trio appears three times, and you have a full square.


The same idea extends to $4d\times4d$ squares. Suppose each row has $4d-k$ squares marked, on average. A $d\times d$ marked square must appear if $$4d{4d-k\choose d}>(d-1){4d\choose d}$$ This gives, in the limit $$k={\ln4\over\ln{4/3}}\approx4.81$$ So almost all squares must be marked before this idea guarantees a marked square.

The following patterns have no $d\times d$ marked squares. As $d$ increases, I think the marked squares will approach $80\%$ of available squares. enter image description here

  • $\begingroup$ Yes, that's the type of argument I was looking for. Thanks a lot! :) $\endgroup$ – arriopolis Mar 10 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.