You Sign Me Right Round (Extended Edition)

Question

I wanted to ask more questions about variations on This Problem. If you hadn't seen that one, check it out. It's required reading (and probably more fun).

In the original problem, these were the rules about sign placement:

• Each sign placed must point to the next sign placed
• Placed signs become obstacles, so future signs cannot point through them
• Every new sign turns right (90 deg clockwise of last sign)
• An older sign may not become blocked by newer signs

In the original problem, Weather Vane found that the maximum density of signs on a 9x9 board (starting in the middle) was:

50 / 81

So first an easy question:

A) If the board were instead very large (many billions of cells, for example), what limit could we place on the maximum sign density?

Let us say the limit has to be a simple fraction. Same is true for the second question:

B) Again on a very large board, what limit could we place on the sign density if we eliminate the 4th rule and allow older signs to be blocked?

Hint/suggestion on part B:

In part A, the answer comes from knowing that there's a cute little pattern that fills a corridor 3 cells wide. For a large board, you can imagine that pattern zig-zagging back and forth and filling any space. Around the perimeter, there may some little inefficiencies from turning around, but for a very large board that has no meaningful impact on the overall density. That same idea applies for part B. Imagine something like a 3-cell wide perimeter where you can connect adjacent patterns as needed, and then only really worry about making a pattern that fits next to itself well. As for the start location, don't worry too much about starting in the middle.

The reason I thought this makes for a interesting question is that without the 4th rule, you wouldn't think it would be hard to do better than part A, but something about it makes that very difficult. It took me days to finally come up with a repeating pattern that was more dense, and it was sort of an "ah-ha moment" which is why I thought it might make for a good question. Also it is very different from working in a small 9x9 board.

To help answer part B you may (or may not) want to try solving the original 9x9 board without the 4th rule. I'm not asking that as it's own question, but if you want to try it I guess we can call that question C.

If you want to post some examples, I found that using Excel's "conditional formatting" helps for readability, now that things can become more confusing. Like this:

Answer 1

Update: I don't know if my solution for

B) Again on a very large board, what limit could we place on the sign density if we eliminate the 4th rule and allow older signs to be blocked?

is the same as OP had in mind, but its coverage is

approaching 100%

The answer is an extension of what I already wrote for B) which I have expanded to show it can cover most of a large area.



Each "unit" leaves 2 squares unfilled. In my example the unit is only 11 cells in length, but the same will apply when each unit is 1000001 cells long - only 2 cells are wasted out of 2000002.

At the edge of the plane, some cells are wasted and the pattern marches back the other way, nesting with the regions already filled. There might be a more efficient way to do the turn-round.

---

Previously:

A) If the board were instead very large (many billions of cells, for example), what limit could we place on the maximum sign density?

I think the following pattern is the most efficient.


The pattern is a 4x3 repeating unit, with a ratio of 8/12 or 0.666667.

On an infinite size board, of course the 3-unit strip will continue for ever, but on a very large board, the wastage needed to switch to another 3-unit strip will be negligible.

Looking at the solutions for boards with odd length side, they are
3x3 6/9 = 0.666667
5x5 15/25 = 0.600000
7x7 30/49 = 0.612244
9x9 50/81 = 0.617283

B) Again on a very large board, what limit could we place on the sign density if we eliminate the 4th rule and allow older signs to be blocked?

This type of pattern fills all the available space.


And this one fills the edges of the space, leaving the middle to be filled by another means.


On an infinite size board, of course those patterns do not have any ends so they only make sense on a very large board. There will be an overhead moving to another position.

I was trying to find a tiling pattern made of blocks, with the grids themselves working outwards spirally around a centre - similar to the logarithmic spiral. This was one idea, but I suppose the blocks would get larger as they progress.


But I could not solve it, and I don't have a definitive answer for the coverage. This example uses 5/6 of the space, 0.833333.

The actual solutions for boards with odd length side are
3x3 6/9 = 0.666667
5x5 16/25 = 0.640000
7x7 40/49 = 0.816326
9x9 67/81 = 0.827160 (incomplete, may be better)

C) Solutions for odd-size boards, with and without rule 4

Answer 2

Weather Vane did get it right, but I made a nice picture when I solved part B and wanted to show it off.

The green cells move up and to the left, the red cells move down and to the right, and the blue cells are the "border cells". I came up with a set of equations to describe the density of this pattern for any square board size, and also for a chosen length of "building block" (which is just 5 in this example). Even if you treat the blue area as having 0 density, you can still get the total board sign density above 99% when you hit 1 billion cells, and the ideal building block length is in the hundreds (which is smaller than I thought it would be).

Additionally, this pattern is not very good on small boards. I'm sure Weather Vane's program would do better for any board size if it had enough computing time. Anyway... yeah... answer is no simple limit on density.