2
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – AgentS
    Commented Mar 10, 2018 at 12:56

1 Answer 1

0
$\begingroup$

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.

EDIT:

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

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

You must log in to answer this question.

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