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

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.