4
$\begingroup$

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. enter image description here (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.

$\endgroup$
10
  • 1
    $\begingroup$ This seems to be the same as asking how many (possibly overlapping) + pentominoes it takes to cover your board completely. $\endgroup$ Dec 1, 2018 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – saulspatz
    Dec 1, 2018 at 18:07
  • $\begingroup$ You seem not to be placing the A squares next to each other although you say it is allowed. $\endgroup$ Dec 1, 2018 at 19:14
  • $\begingroup$ 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? $\endgroup$
    – Blue
    Dec 1, 2018 at 19:42
  • $\begingroup$ @RossMillikan: There are a bunch of green A squares next to each other in both solutions. $\endgroup$ Dec 1, 2018 at 20:46

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Dec 4, 2018 at 7:56
  • $\begingroup$ 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? $\endgroup$ Dec 4, 2018 at 8:15
  • $\begingroup$ I may just be talking gibberish though, as I barely understand what I'm saying in the comment above. Sorry about that. $\endgroup$ Dec 4, 2018 at 8:18
  • $\begingroup$ 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". $\endgroup$ Dec 4, 2018 at 15:38
2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

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