Professor Halfbrain and the 9x9 chessboard (Part 2)

Question

This puzzle is the continuation of Professor Halfbrain and the 9x9 chessboard (Part 1). The difference is that "distance at least $2$" has now become "distance more than $2$".

---

Professor Halfbrain has spent the last few days with placing pawns on a $9\times9$ chessboard; each of the $81$ squares on the chessboard had side length $1$. Halfbrain always started with an empty board, and then one by one placed (point-sized) pawns onto it. Every pawn was placed precisely in the middle of one of the little chessboard squares. Whenever Halfbrain placed a new pawn, its distance to each of the pawns placed before was more than $2$.

Professor Halfbrain has proved two extremely deep theorems on such placements of pawns.

Professor Halfbrain's first theorem: It is possible to place three pawns according to the above rules.

Professor Halfbrain's second theorem: It is not possible to place $81$ pawns according to the above rules.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "three pawns" in the first theorem may be replaced by "$x$ pawns", and so that "$81$ pawns" in the second theorem may be replaced by "$x+1$ pawns" (again yielding true statements, of course).

Answer 1

I've been thinking on this problem for a long time, and I think I nailed it. I will expand on the ideas I used for the solution of part 1 of this puzzle, and also on the reasoning of Michael Seifert's answer.

We may convert this problem into an analagous problem, in which we have a $9 \times 9$ board and cross pieces:

The central red square represents the pawn. We want to find the maximum number of cross pieces we can place on the board, subject to:

• No two pieces overlap;
• The central red square of a piece always lies inside the board.

It is allowed for orange squares to not lie on the board. Because of this, a placement of crosses on the board may feature up to $12$ 'extra' squares, which do not lie on the board itself. One example of such placement is given below.

This means that, in theory, up to $81 + 12 = 93$ squares are available for use. Since each piece covers $5$ squares, we may therefore not place $19$ pieces on the board, ($19 \times 5 = 95 > 93$). We will improve this estimate by analyzing the placement of crosses along the boundary (those are the ones that generate the additional squares).

Let $S$ be the big square (with side length $9$) that is the boundary of the board. We will consider the possible configurations of crosses along $S$ and show that, for each of its sides, the net gain of extra squares will never reach $9$ or more, so that one may not place $18$ crosses on the board (because there will never be $81 + 9 = 90$ or more squares available for use).

Now, for each side of $S$, the outer squares of that side are the squares that are not on the board and contain an edge entirely on that side of $S$. Notice that each side of $S$ contains at most $3$ outer squares. For each configuration of crosses along a side of $S$, the net gain of extra squares (along that side) will be the number of outer squares minus the number of squares that must remain cross-free as a consequence of the configuration itself. We divide it in cases:

Case $1$

Each X indicates that one of the two squares must be free of cross pieces, so this case gives us a net gain of one additional square.

Case $2$

The X indicates that one of the two squares must be free of cross pieces, so this case gives us a net gain of two additional squares.

Case $3$

Each X indicates that one of the two squares must be free of cross pieces, so this case gives us a net gain of one additional square.

Case $4$

Case $4$ is separated in two other cases.

If a square touching the boundary is not covered by a cross piece, then at least two other squares touching it will also not be covered. This is shown in the picture to the bottom left. Hence, in this case, no additional squares will be gained.

On the other hand, if both squares touching the boundary are covered, then two of the squares with the big X over them (in the bottom right picture) must be free of cross pieces. Therefore, this case results in a single additional square.

Case $5$

Each X indicates that one of the two squares must be free of cross pieces, so this case gives us a net gain of one additional square.

It’s easy to see that these cover all possible configurations of three crosses on a side of $S$, up to symmetry (reflection). Additionally, if a side of $S$ has two or fewer crosses, the net gain will necessarily be two or less. All of this implies that the net gain of each side is never above two, so the total net gain is never above $8$, and in particular never above $9$, as claimed.

Now, an attentive reader might point out that cases $1$, $2$ and $3$ allow for overlap of cross-free areas. In other words, it might happen that we count a cross-free square twice, so the ‘actual’ net gain is higher. Visually, it should look like this:

_{(source: gyazo.com)}

The first observation is that this ‘confluence’ may occur at most two times, on opposite corners of the board. The second observation is that if one of the sides of the confluence falls into case $1$ or case $3$, the total net gain for both sides of the confluence will be at most $6 – 2 = 4$, so we’re still good. Thus, we need only consider confluences in which both sides fall into case $2$.

To that end, we refine our analysis of case $2$ itself. If the lone square touching the boundary is cross-free, the total net gain of the confluence will once again be at most $4$ and we’re good. Suppose then that the square is covered; the situation looks like this:

_{(source: gyazo.com)}

It’s easy to see that at least one of the purple squares must be cross-free. The following picture shows the whole confluence. At least one of the purple squares and at least one of the pink squares must be cross-free. Hence, the total net gain for both sides of the confluence is $6 – 3 =3$.

_{(source: gyazo.com)}

Finally, observe that a confluence like the one above may happen at most once; in other words, there can be no additional overlap with the purple or pink squares. With this, I believe all cases are covered, so the highest desired integer is $x = 17$.

Sorry for the lengthy answer, but it ended up being the simplest approach I could find.

Answer 2

It looked like the other answers had some room left to work with, so starting with them and messing around a bit, I managed:

I also found a symmetrical way to do this:

So

Professor Halfbrain's first theorem: It is possible to place 17 pawns according to the above rules.

Professor Halfbrain's second theorem: It is not possible to place 18 pawns according to the above rules.

Answer 3

UPDATE: Based on the suggestion by f'' in the comments, my original statements can be greatly improved:

To each pawn, we can associate its own square and the four squares surrounding it, making a plus-shaped tile with an area of 5 square units. Any two such tiles that abut will automatically have a distance of at least $\sqrt{5}$ between their centers (i.e., the pawn locations). Moreover, the total area not on the original chessboard covered by these tiles will be at most 12 square tiles; we can fit at most three such tiles along each edge, meaning that at most three "squares" from our plus-shaped tiles can stick out over the edge. The total area covered by tiles is thus at most $9 \times 9 + 3\times 4 = 93$ square units, and so $N < 93/5 = 18.6$.

Thus, a significantly better version of Professor Half-Brain's Second Theorem is

It is not possible to place 19 pawns according to the above rules. Note that the bound is substantially better both because we have increased the "size" of the tiles and reduced the maximum amount of area they can cover.

---

Below this line are some weaker bounds from my original answer.

A slightly different approach:

The closest any two pawns can be to each other, given the above rules, is $\sqrt{5}$ (when the pawns are a "knight's move" away from each other.) This means that we should be able to draw a circle of radius $\sqrt{5}/2$ around each pawn, and that none of the circles will intersect. Moreover, all of the circles will be contained in a square of side $8 + \sqrt{5}$, centered on the original chessboard. (Note that the circle corresponding to a pawn on the edge will go "off the edge" of the original chessboard somewhat.)

.

We are thus presented with the problem of how many circles of radius $\sqrt{5}/2$ can be packed into a square of side $8 + \sqrt{5}$, such that the center of each circle is on a grid point of the original chessboard. Right off the bat, we can place a bound on the number of circles that can be fit. Since none of the circles overlap, the area of all the circles can be no greater than the area of our new square. The area of each circle is $5\pi/4$; thus, $N < (8 + \sqrt{5})^2/(5\pi/4) \approx 26.7.$

Thus, we can refine Professor Half-Brain's Second Theorem to read:

It is not possible to place 27 pawns according to the above rules.

This can be refined slightly by noting that

if we remove the restriction that the pawns be on grid points, the best we can do is to pack the circles into a hexagonal grid. Thus, around each pawn we can draw a hexagon such that the radius of the circle (our original circles) inscribed in the hexagon is $\sqrt {5}/2 $. Note that the hexagons can now reach out a little further from our original chessboard than the circles could; the distance from the center to a vertex of one of these hexagons will be $\sqrt{5/3}$, and so all of the hexagons must now be contained inside a square of side $8 + 2 \sqrt{5/3}$. The area of our hexagons is $5\sqrt {3}/ 2 $, and by the above logic, we must have $N < \frac {(8 + 2 \sqrt {5/3})^2} {5\sqrt {3}/2}\approx 25.9.$

Thus, a slightly refined version of Professor Half-Brain's Second Theorem is

It is not possible to place 26 pawns according to the above rules.

In fact, if we view the problem in this way, we can actually look at the literature for guidance:

The smallest square into which one can pack $n$ circles of radius 1 into a square has been solved for $n \leq 20$; the solutions can be found here. In our case, we can rescale our circles so that they have radius 1; the square in which they must all fit is therefore of side $(8 + \sqrt{5})/(\sqrt{5}/2) \approx 9.15542.$ Unfortunately, it is not known whether 21 circles can fit into a square of this size; the best known packing is into a square of side 9.358... So it seems likely that you cannot place 21 pawns according to the above rules, but this is not a proof.

Note that none of these are strict upper bounds;

the fact that we must place the pawns on square grid points will mean that we cannot optimally pack our circles/hexagons, and so some of the square's area will be "wasted". Basically, for the first two theorems, we have proven an upper bound among all possible pawn placements on the chessboard; any placement for which the pawns are on grid points will necessarily be no greater than this bound. Most likely, the smallest number of pawns that cannot be placed is less than 25 (or 21, if you believe the "non-proof" in the previous paragraph.)

Answer 4

Note: This solution is DISPROVED.

Here's what I think:

I have shown three configurations A, B, C. The main thing I kept in mind while making these grids is that the board should be closely packed with pawns. Now you may ask how is B different than C and A that it have more pawns.

I think the reason is

their slopes. The magnitude of slope for the line joining the pawns in slant position is more for B than A and it is more in such a way that the line contains most number of pawns by the given rules. In situation C, it makes both kind of angles, therefore having mixture of both kind of slopes.

Therefore

Professor Halfbrain's corrected first theorem:

It is possible to place 16 pawns according to the rules.

Professor Halfbrain's corrected second theorem:

It is not possible to place 17 pawns according to the rules.

Answer 5

If I use the same logic as was used here, then I can

Stagger the placement of the pawns to that, vertically and horizontally, they are no closer than 3 units away from each other, and diagonally, they are $\sqrt{5}$ units away from each other. This gives us:


Further staggering only results in a shifted/rotated version of the same configuration. Note that no squares in the last column (or last row, if you attempted the same pattern rotated 90 degrees) can be used, as 2 is the maximum distance from a "used" square. OK, it turns out I was extremely wrong about this—something told me that if it wasn't symmetrical in some way, or if there was inconsistent spacing, it was not an "optimized" configuration. I was wrong about that.

I believe I can say

Professor Halfbrain's first theorem: It is possible to place 15 pawns according to the above rules.

Professor Halfbrain's second theorem: It is not possible to place 16 pawns according to the above rules.