A liberty puzzle

[yebellz]

Here’s one way to search for a solution. Place 6 (or 5 or 7) stones on the 5x5 board, while avoiding any one-space jump or kosumi (diagonally adjacent) relationship. Then count the liberties of those stones, which represents the total number of chains that could attach to those stones, which actually represent the eventual liberties for your actual solution. This quickly rules out a liberty placement without having to check how to place chains.

If you allow more than two colors of stones, it’s very easy to color stones around a liberty arrangement to maximize the number of chains supported by those liberties.

[antonTobi]

Here’s a super messy (basically stream-of-consciousness) argument that 19 chains, at least, is impossible on 5x5:

Each empty point can only be a liberty to at most 4 different chains, and each chain consists of at least 1 stone.

So for instance to get to 20 chains, we would need 5 isolated empty points, each connected to 4 chains, which is impossible. (we would have to place all the five empty points in the central 3x3 square, but then some chains willl get 2 liberties)

So let’s look at 19 chains and 6 empty. Number of connected chains for each empty point would need to distribute in one of these ways:

4 4 4 4 3 0
4 4 4 4 2 1
4 4 4 3 3 1
4 4 4 3 2 2
4 4 3 3 3 2
4 3 3 3 3 3

But actually, having three 4’s is impossible: once again they will all have to be in the central 3x3, but they then will end up too close to each other. So we are limited to the last 2 options above.

If we are to achieve 19 chains, each point that is not one of the 7 empty has to be a 1-stone chain. This makes what can happen in the corners quite limited. If a corner is not empty, there has to be an empty point next to it, which has at most 3 chains. If a corner is empty, it is connected to at most 2 chains. Thus in the scenario “4 4 3 3 3 2” from above, we can tell exactly where each empty point must be placed:

Two 4’s in the central 3x3
Three 3’s adjacent to three of the corners
And a 2 in the last corner.

Here none of the empty points are allowed to touch, and kosumi’s and jumps are forbidden as usual. Now it’s easy to see that this arrangement is impossible, since a stone at either of the circles makes all of the crosses forbidden:

(so after the three 3’s are placed next to the corners, there is not any space left for the two 4’s in the center)

Ok, one possible configuration left: “4 3 3 3 3 3”. None of the empty points are in the corners, so there must be four of them adjacent to corners, but then (looking at the above image again), the center is completely forbidden, so the last “4” is impossible to place.

If I didn’t make a mistake (very well might have with how messy this got), this proves that 19 chains on 5x5 is impossible (also I don’t think this assumed 2 colors?).

In many parts of this argument the given task seems not even close to working, so maybe with some tidying up a similar argument could prove 18 impossible?

[antonTobi]

I just realized I incorrectly placed an extra cross in the center in the image. Without that cross the argument for 4 3 3 3 3 3 becomes slightly more complicated, but it still works (that is, the argument for why that configuration doesn’t work, works): the last 4 could be placed in the center, but the 5th 3 has no valid place along the edge.

I must sound like a crazy person at the moment, I promise to present a cleaner argument after I’ve slept

[yebellz]

@shinuito

They can’t be a one point jump or kosumi from each other

The liberties could form a 2x2 or 2x3 empty space in the corner. However, I think the optimal solutions probably would not feature such an arrangement.

---

In my previous post, I posed a different way to look at it, but I don’t think I was very clear or precise. Let me try to formulate another riddle, which I think is actually equivalent to the 5x5, 1-liberty, multi-color chains problem:

Consider this equivalent(?) riddle

On a 5x5 board, place one or more stones, where the liberties adjacent to each individual stone do not overlap with the liberties adjacent to any other stone. What is the largest number of total liberties (directly adjacent to any stones) that can be formed?

A solution to this new problem could be turned in to a solution to the original 5x5, 1-liberty, multi-color chains problem, by replacing the stones with liberties, and their liberties with a uniquely colored stone (or with at least enough colors to avoid neighboring chains from having the same color), and then extending the chains to fill in the remaining space.

I think the way that I reworded the problem into this (hopefully) equivalent form might make it easier to search for a solution. For my new riddle, I think it can be solved as a more directly tessellation problem. Basically, it could be solved by consider packings within a 7x7 grid with non-overlapping tiles that look like this, and the objective is to have as many red circles within the 5x5 central part of the 7x7 grid.

Note1: For my new riddle, the yellow parts of these tiles represent the stones, while the red parts represent the liberties. For the original riddle, the yellow parts represent the liberties, while the red parts represent stones.

Note2: I’ve omitted some of the larger possible tiles, since we already know that the solution cannot use tiles with more than 7 yellows, and there is no valid 7-yellow tile.

[shinuito]

I think 16 chains are more fun

5 'liberties' but only 16 groups. But nice symmetry for fun

7 'liberties' but only 16 groups. But nice symmetry for fun

[antonTobi]

Just a note about the equivalent tiling problem: you need to fill up the central 5x5 completely, since an empty point that is not part of a tile gives unwanted liberties (but the 7x7 does not have to be filled completely)

[yebellz]

I think you could always extend one of the chains to fill those spaces.

[antonTobi]

Ah yes, I thought this might reduce the number of chains, but with multiple colors we can assume that all the chains connected to an empty point have different colors, and just choose one of them to place in the empty spot.

There could be trouble if an empty spot were next to a yellow stone in the tiling, but of course that never happens with these tiles!

[antonTobi]

Another way to get to 17 with 2 colors:

This arises quite naturally from trying to place the empty points at knight moves, but I don’t think any of us has posted it yet so wanted to have it here for reference.

Also just to illustrate yebellz’s tiling with an example, this would be equivalent to this (different colors added to see the different tiles easier):

Notice that this configuration requires extending a single white chain two times to fill empty spots, but if we allowed more colors we would be able to do it by extending two chains one time:

As far as I can tell this is always possible, showing that the tiling problem is truly equivalent.

[shinuito]

@le_4TC

Another way to get to 17 with 2 colors:

This arises quite naturally from trying to place the empty points at knight moves, but I don’t think any of us has posted it yet so wanted to have it here for reference.

It’s nice to have an example with 16 one stone groups and a three stone group

@yebellz

Consider this equivalent(?) riddle

On a 5x5 board, place one or more stones, where the liberties adjacent to each individual stone do not overlap with the liberties adjacent to any other stone. What is the largest number of total liberties (directly adjacent to any stones) that can be formed?

A solution to this new problem could be turned in to a solution to the original 5x5, 1-liberty, multi-color chains problem, by replacing the stones with liberties, and their liberties with a uniquely colored stone (or with at least enough colors to avoid neighboring chains from having the same color), and then extending the chains to fill in the remaining space.

I think that was more or less what I was doing - but this is a much clearer formulation of it. Makes it simpler to understand what to do.

[antonTobi]

As a first step to proving 18 chains impossible, lets’ prove it’s impossible to fit 7 “+”-tiles into this shape:

I’ve removed the corners since they can never be filled by any of the tiles (even allowing larger tiles than the small “+”).

Fitting 6 is easy:

(this corresponds to a 17-chain solution with 3 colors equivalent to one shinuito posted earlier)

But now consider how we could possibly fit a 7th “+” in the above image. There are 15 empty spaces in that picture, so after 7 plusses there would only be 10 empty spaces. But notice that in the above image, each “side” has at least 3 empty spaces. We could never get down to 2 empty spaces along one side (that would require 3 plusses side by side, giving a total width of 9 which is larger than 7).

Thus there is at a minimum 3 * 4 = 12 empty points along the sides alone. This proves that 7 “+”-tiles can’t fit on the 7x7-board.

[antonTobi]

Next, how about one “double plus” (the tile corresponding to two adjacent liberties) and 5 regular plusses? The double plus consists of 8 stones, so this leaves

7x7 board - 4 corners - 5 plusses with 5 stones - 1 double plus with 8 stones =
= 49 - 4 - 5 * 5 - 8 = 12 empty spaces

In this case though, 3 empty spaces along the side is no longer the minimum, one of the sides could have 2 empty spaces like here:

Clearly this can only happen for one of the sides though. Furthermore, the above arrangement is the only way (up to rotations/reflections) to get 3 stones along one side, since placing the blue tile one step to the right leaves no room for another tile touching the side.

Can we fit 4 more plusses from the starting point above? Notice that we can’t fill both the red-white spots here:

This means that to get down to the required 12 empty spaces, we still need exactly 3 empty spaces along the remaining 3 sides (and also we have to fill one of the red-white spots).

Now note that either of these two placements, on its own, makes it impossible to fit two tiles touching the upper side.

Thus we’re forced into this placement:

But placing two more plusses here is clearly impossible.

This completely rules out the case where we have 2 empty spots along one side. The alternative is exactly 3 empty spots along each side, with no empty spots allowed in the center. I’ll try to do that in the next post since this one is getting long.

[yebellz]

I think we should just check with a script. The tiling perspective has already greatly reduced the complexity of the search.

[antonTobi]

So in this case, each tile touches each side at most once. A tile can never touch the middle of a side, since this would block any other tile from touching that side:

Also, neither type of tile can touch the spot next to the middle along a side, since this messes up the adjacent side. For instance, here the right side can no longer have two different tiles touching it:

This leaves only this possibility:

(since we already ruled out placing the “double plus” in a corner before).

But now there is essentially only one way of placing the double plus:

And then placing the 5th regular plus is impossible.

This shows that this tiling is impossible, which should also prove that 18 chains is impossible? I’ll need to take a step back to consider the details of the equivalence again.

Edit: To summarize what I’ve proved so far, placing either 7 plusses or 5 plusses and one double-plus is impossible on the 7x7-board. I believe this should imply that 18 chains with 1 liberty each is impossible on the 5x5 board (regardless of number of colors allowed), but I’m not 100% sure on that implication at the moment.

[Leira]

A better solution to the initial puzzle.