6
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ I've added a hint in the question. I'm a little worried this question isn't too good, but I thought it had a neat answer, so hopefully somebody will appreciate it. $\endgroup$ – Dark Thunder Jul 5 at 14:08
3
$\begingroup$

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.

enter image description here

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.

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

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

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

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

enter image description here

$\endgroup$
  • $\begingroup$ You got 65?! That pattern looks like chaos, too... that's why I didn't want to ask about it. That was all computer, right? I got 59 by hand. Anyway for part B I'm not sure I follow... surely you can't superimpose those patterns mentioned. $\endgroup$ – Dark Thunder Jun 27 at 14:18
  • $\begingroup$ @DarkThunder I have revised the answer. I found a better (but not definitive) solution for the 9x9, and stick to the question as asked. I'll delete the earlier comments. $\endgroup$ – Weather Vane Jun 28 at 12:03
  • $\begingroup$ 67 now! Nice. I also like where your part B is at. I'm not sure this helps or not, but my intention on the phrasing of the question was that I am essentially asking about an infinite board, but I just didn't want the outside perimeter to be completely forgotten about. I typically dislike using "infinite" in anything that isn't calculus. $\endgroup$ – Dark Thunder Jun 28 at 12:37
  • $\begingroup$ @DarkThunder IMO it is the border that (generally) hampers the efficiency of the smaller boards. My idea for part B is something like this but I got distracted by other puzzles. It suits the idea of an infinite board. $\endgroup$ – Weather Vane Jun 28 at 12:43
  • 1
    $\begingroup$ And it is right! I will post my picture on it for any future reference but that's exactly what I wanted to see in an answer. I was just wondering if I should answer this thing myself and let it fade away. Now I don't have to! Yay! $\endgroup$ – Dark Thunder Jul 23 at 12:36
1
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ On the occasion of my final answer, I didn't use a program, but worked by hand on quadrille paper before using Excel as a drafting tool. $\endgroup$ – Weather Vane Jul 23 at 13:01
  • $\begingroup$ @WeatherVane Oh, sorry, I was referring to your "part C" program. Let that thing spend a few billion eons on a 100,000 square board and I'm sure it would beat my 99%. $\endgroup$ – Dark Thunder Jul 23 at 13:03
  • $\begingroup$ The earlier code was slow enough even on a small board >= 9, so I knew that was a futile exercise. That's proven by the fact that it needs a large board to be effective, although it might have been possible to simulate that. I think the key is how it makes the turns to reverse the journey. $\endgroup$ – Weather Vane Jul 23 at 13:06

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.