4

Given a 5x5 grid of 25 tiles, is it possible to place 13 counters so that no 2x2 internal square of the grid is repeated?

Each square can be considered binary, with either a counter or no counter.

Here is an example of a configuration of 13 counters that does not meet the criteria:

Example invalid grid with 13 counters

Is it possible to find a configuration that meets the criteria of all 2x2 squares being unique? I'd love to see a proof of some sort in regard to this problem, either proving or disproving that it is possible.

Phoebe J
  • 49
  • Hint: The first proof of the 4-color map theorem actually represented a computer search. $~\displaystyle \binom{25}{13} = 5,200,300.~$ My (vanilla) PC programming experiences have been that my PC can routinely handle $(10)^7$ cases, but will start to balk at $(10)^8$ cases. You will need a working knowledge of some language, like Java, C, or Python. If you are new to programming, I suggest Python. – user2661923 Dec 03 '22 at 03:35

1 Answers1

3

Let us use some basic convergent thinking in order to solve the problem.
Question: How many $2 \times 2$ squares are there in a $5 \times 5$ grid?
Answer: $16$.
Thus, by invoking the drawer principle 1, we need at least $16$ distinct configurations for a $2 \times 2$ square grid.

Now, let us use the numbers $1$ and $0$ to indicate the two possible states of any $1 \times 1$ square.

$0 0$
$0 0$

$0 0$
$0 1$

$0 0$
$1 0$

$0 1$
$0 0$

$1 0$
$0 0$

$1 1$
$0 0$

$0 0$
$1 1$

$1 0$
$1 0$

$0 1$
$0 1$

$1 0$
$0 1$

$0 1$
$1 0$

$1 1$
$1 0$

$1 1$
$0 1$

$1 0$
$1 1$

$0 1$
$1 1$

$1 1$
$1 1$

Hence, we have some bricks to build the wall… and they are enough, since we can constructively show that
$0 1 0 0 0$
$0 1 1 1 0$
$1 1 1 0 1$
$0 0 1 0 0$
$0 1 0 0 0$
is a solution.
And this affirmatively answers the original question (no program needed). Figure 1: The aforementioned solution

Marco Ripà
  • 1,062
  • 2
  • 19
  • That's a neat solution, how one of the specifications was that 13 counters were required. I have since confirmed that there are multiple solutions to this problem that use 13 counters, for example:

    1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1

     – Phoebe J Dec 03 '22 at 06:37
  • Oh, I missed it... anyway, $12$ or $13$ counters in our case, since $0 \leftarrow \rightarrow 1$. – Marco Ripà Dec 03 '22 at 08:10
  • Moreover, I think that this could be a valuable generalization: https://en.wikipedia.org/wiki/De_Bruijn_torus – Marco Ripà Dec 03 '22 at 08:14