# A puzzle about the maximum number of favorable squares on a board of any given size.

I have come up with an interesting puzzle but I can't for the life of me figure out how to solve it.

It follows like this:

You have 2 types of squires that are congruent with one another. Let's call them A-squares and B-squares. They both have an area of n²

The rules are:

1. You can place as many B-squares on a square board with a side length of N as you want. (imagine placing Black squares on an empty chess board)

2. A-squares must be placed next to at least 1 B-square (they can be placed next to each other as long as both squares are touching at least 1 B-square)

The question is: What is the Maximum number of A-squares that is possible for any n-length square board?

If this question can't easily be answered I want to at least know if it's possible to calculate the maximum number of A-Squares that can fit into a 7x7 board.

This is an image of the two best configurations that i could come up with manually for a 7x7 board. (The green squares are A, blue squares are B and the the yellow/black squares outlines the board)

For context, I came up with this puzzle a long time ago when I wanted to create the most space-efficient sugarcane farm i could in minecraft seeing as how sugarcanes could only be planted adjacent to water blocks. I don't play minecraft anymore but I like the mathy-ness of many of it's aspects.

I'm still in high-school and i'm not good at programming. Sorry for all the trouble.

• This seems to be the same as asking how many (possibly overlapping) + pentominoes it takes to cover your board completely. – Henning Makholm Dec 1 '18 at 18:00
• Why can you place a solid row of A squares, then a solid row of B squares, then another row of A's etc.? That would give 28 A's on a $7\times 7$ board. – saulspatz Dec 1 '18 at 18:07
• You seem not to be placing the A squares next to each other although you say it is allowed. – Ross Millikan Dec 1 '18 at 19:14
• You have a "square of side length of $n$", yet the $A$- and $B$-squares "both have an area of $n^2$". Doesn't that mean that a single $A$ or $B$ will completely fill the board? – Blue Dec 1 '18 at 19:42
• @RossMillikan: There are a bunch of green A squares next to each other in both solutions. – Misha Lavrov Dec 1 '18 at 20:46

There is a straightforward bound saying that at least $$\frac15$$ of the $$A$$-squares and $$B$$-squares must be $$B$$-squares. Each $$A$$-square has an adjacent $$B$$-square, and each $$B$$-square has at most $$4$$ adjacent $$A$$-squares, so if there are $$a$$ $$A$$-squares and $$b$$ $$B$$-squares, then then number of $$A$$-to-$$B$$ adjacencies is at least $$a$$ and at most $$4b$$, giving $$4b \ge a$$.

This gives an upper bound of $$a \le \frac45 N^2$$ for $$N \times N$$ boards, which I expect to be approximately correct, with only the boundary causing problems. For the $$7\times 7$$ problem, however, this says only that we can't do better than $$10$$ $$B$$-squares and $$39$$ $$A$$-squares, whereas your second solution has $$b=12$$ and $$a=37$$. This is almost but not quite there. After several computer searches, though, I get the feeling that $$a=37$$ is the best we can do.

We can make partial progress and prove $$a \le 38$$ by looking at what happens in each corner square. If the corner square is an $$A$$-square, then one of the adjacent edge squares is a $$B$$-square and we get a "wasted" $$A$$-to-$$B$$ adjacency where it touches the side of the board. If the corner square is a $$B$$-square, we get two wasted adjacencies. If the corner square is empty, we lose the chance at having an $$A$$-square there.

So we have $$4b-s \ge a$$ and $$a+b \le 49-t$$, where $$s$$ is the number of occupied corners and $$t$$ is the number of empty corners. We can $$a \le 4b-s$$ and $$a\le 49-b-t$$ to get $$2a \le 49+3b-s-t$$ or $$2a \le 45+3b$$ (since $$s+t=4$$); in particular, $$2a \le 45 + 3(49-a)$$, which reduces to $$a \le 38.4$$. Because $$a$$ is an integer, we must have $$a\le 38$$.

I don't expect $$a=38$$ is possible, but I can't prove it yet.

• Thank you for answering. I noticed in your answer that I made a slight mistake in my question. The board should (as you've rightly assumed) have a side length of N so that it becomes an N x N board. N could be defined as X²∙(n²), probably? – David Arnryd Dec 4 '18 at 7:56
• Another thing, as the total number of A-squares is.*a ≤ 4/5 N²* given a board of NxN. Couldn't it be possible to then count all A-squares in a board with the size of (N+1)x(N+1), with the rules that B-squares can only exist within the normal NxN board. Then as the last operation maybe it could be possible to "count" how many "sides of B-squares" are touching the border. It would then be simple to subtract "the number of B-square-sides touching the border" from the total amount of A-squares to get the resulting number of A-squares that can fit into the NxN board, right? – David Arnryd Dec 4 '18 at 8:15
• I may just be talking gibberish though, as I barely understand what I'm saying in the comment above. Sorry about that. – David Arnryd Dec 4 '18 at 8:18
• It's hard to say much about what happens in the border, since you don't have any requirements on what happens. I considered what would happen on a board that wrapped around (so that no squares are on the boundary) and in that case it still doesn't look like we can do better than $37$ for a $7\times 7$ board but I have no good explanation for why beyond "the squares just don't fit together right". – Misha Lavrov Dec 4 '18 at 15:38

Inspired by @MishaLavrov answer, here's a slightly improved accounting method that proves $$a=$$ no. of A-squares $$=38$$ is impossible, and therefore $$a=37$$ is optimal, for the $$7\times 7$$ board.

First consider any board with empty (non-A, non-B) squares. Since the optimality criterion is no. of A-squares, we can change all empty squares into B squares without affecting optimality. Therefore, from now on, without loss we can consider only boards filled with A & B squares (i.e. no empty squares).

Incidentally, this is why @HenningMalkolm is right that this problem is equivalent to covering the board using + pentominoes (overlap allowed). In the following I will use B-square and + pentomino somewhat interchangeably.

Anyway, let $$b =$$ no. of B-squares. So $$a+b = 49$$.

Any B-square can "enable" $$4$$ A-squares. Imagine you place the B-squares one by one, and for each one, count the increase in the total number of enabled A-squares. This number is often $$4$$, but can be $$<4$$. We will consider any deficit from $$4$$ as a "wastage" of A-squares. E.g. a B-square at a corner has a wastage of $$2$$ (assuming no overlap with previous + pentominoes), a B-square along an edge has a wastage of $$1$$ (assuming no overlap with previous + pentominoes) and a B-square whose + pentomino overlaps $$1$$ square with a previous pentomino (e.g. B-squares at $$(i,j)$$ and $$(i, j+2)$$) has a wastage of $$1$$ (at $$(i,j+1)$$ where the two + pentominoes overlap), etc. Let $$w=$$ the total no. of wastages. By definition, $$4b = a + w$$.

Thus we have $$2$$ equations with $$3$$ unknowns. If $$a=38$$, this would imply $$b=11$$ and $$w=6$$. To show that $$a=38$$ is impossible, all we need is to show $$w=6$$ is impossible. In fact we will now show $$w \ge 8$$.

Lemma: Consider any $$2\times 2$$ corner. Filling this corner alone would require $$w \ge 2$$.

Proof: Consider the case of $$\{(0,0), (0,1), (1,0), (1,1)\}$$. If $$(0,0)$$ is a B-square we are done. If it isn't, then without loss let $$(0,1)$$ be a B-square, which causes a wastage of $$1$$. To fill $$(1,0)$$, we would need $$(1,0)$$ or $$(2,0)$$ to be a another B-square (another wastage of $$1$$) or, even worse, $$(1,1)$$ to be a B-square (another wastage of $$2$$, since it is next to the $$(0,1)$$ B-square). QED

On a $$7\times 7$$ board, the $$4$$ separate $$2\times 2$$ corners are far apart so that each would cause a wastage of $$\ge 2$$. Thus filling these $$16$$ squares alone would cause $$w \ge 8$$.