A small puzzle.

[\oo|- [-_-] -|oo/]

So, I was taking notes on something¹ and I noticed that each item usually had about two subitems. I allowed some space for them, but it was never enough. I always ended up writing tiny words at right angles, splitting, shuffling, and employing other conservation tactics that drastically reduced the readability of the notes.²

I decided that this was some BS, and tried making the headings like a genealogy tree, but that didn't work either. The lines were too long, the blocks collided, and it was even uglier. I began trying patterns to see what would work, but I couldn't figure anything out.

Anyway, here's the puzzle.



The nodes (black before reproducing, dark gray after) inhabit a grid. Each node grows two branches to reproduce (red, white). If a node doesn't have the space to reproduce and send out two shoots, it dies (blue). Nodes can't reproduce diagonally and can only reproduce to an adjacent square.

Questions:
1] Is there a way to direct the reproduction of nodes such that the pattern can grow indefinitely producing no dead nodes?
2] If not, what is the pattern that produces the lowest amount of dead nodes?
3] What's the pattern that produces the highest amount of dead nodes?
4] Is there a suicide pattern that terminates with only dead nodes?
5] What if this grid was three-dimensional and the nodes were cubes? That'd be a kick, I bet.


1. A video game
2. My engineer friend said to buy bigger paper, ho ho ha ha.

[antonfire]

I'll just pick off the easy ones.

Question 1:

Spoiler:

No, no matter what choices you make, the nodes eventually start dying.

If the pattern reproduces with no dead nodes, there are 2ⁿ nodes after n steps. But each of these nodes is at distance at most n from the origin, and there are only n² or so places that close to the origin. (n^d in higher dimensions.) 2ⁿ grows faster than n^d for any d, so in any dimension the nodes start dying after a while. Loosely, there just isn't enough room for them all to reproduce.

If you make this argument carefully, you can give explicit upper bounds on how long you can go before nodes start dying, and lower bounds on how many nodes must be dead after a given amount of time.

Question 4:

Spoiler:

No, no matter what choices you make, the pattern never dies.

At any point in the pattern, any dead node has at least three used up neighbors (otherwise it wouldn't be dead). This includes nodes that have already reproduced. However, if you pick a node that is further to the northeast than any other node, it can have at most two used up neighbors, south and west. So at any point in the pattern, a northwesternmost node is still alive, so the pattern never dies. The only exception to this is when the northwesternmost node is the starting node, after it's already reproduced, but then we can just look at, say, the southeasternmost node instead.

This argument is pretty specialized to two dimensions. In three dimensions, for instance, nodes that have reproduced still have three neighbors, so a priori it could be that all the "outermost" nodes are nodes that have reproduced. I wouldn't be terribly surprised if there was a suicide pattern in three dimensions, in fact.

[Yakk]

More on #4

Spoiler:

The suicide problem is the difficulty in "doubling back" to the main mass.

The NEmost node came from the S or W, which means it must have a child that is N or E, which is the new NEmost node which also has a S or W child.

In 3 dimensions, you might be able to "bend" back towards the core. Then a question is "can you make a 'surface' that traps the bending fast enough so that the bends can fit back inside that surface and be killed"?

[mfb]

4:

Spoiler:

In two dimensions, it is not possible, see above.
In three dimensions: building a surface of a cube with side length needs a/2 steps to begin (spread in all 6 directions at the same time) and a steps after that, plus a finite number to go into different directions at the same time. I think the interior can live longer than 3/2a steps (note that it can hit some already built borders even before), so growth of the interior might work. Maybe it is more tricky if you let each cell spread out to 3 new cells.

2/3:

Spoiler:

That is tricky and depends on the question: The lowest (highest) asymptotic growth for large step numbers? The lowest (highest) number of dead cells for step n?
To get a low (high) number of dead cells in step n it is good to let as many cells reproduce (die) as possible in the steps before, but that gives more (less) dead cells later.

An upper limit is n^2+(n-1)^2 dead cells after n steps, as that number is the total number of cells reachable in step n-1.
A lower limit is c*n-d for some unknown constants 0<c and d>0. As we already know, there is no suicide pattern, so each step generates at least 2 new cells. The total population of living cells cannot exceed (n+1)^2+n^2 cells, so growth cannot be faster than quadratic. That means that in the long run, at least one cell has to die in each step to avoid exponential growth. Insert some more rigid mathematical proof here.

Here an idea for linear growth for question 2:

Black is the initial cell, lighter grey -> later steps. R reproduced, D is dead. Each step generates three new dead cells, after 5 steps I have 7 dead cells, so my pattern for a low number of dead cells get 3n-8 dead cells after step n. Note that the order of the reproduction matters to get the right dead cells.

Edit: removed fragments from an old part of the post

[skeptical scientist]

Some further natural questions, which might be a bit easier than the harder questions above.

6] What's the pattern that produces the most nodes (total live+dead)?

Some upper bounds:

Spoiler:

Each node at step n is within n squares of the original square (counting distance vertically/horizontally, not diagonally). This gives an upper bound of n²+(n+1)²=2n²+2n+1 on the number of nodes. You can do better by considering the configuration after 1 step, which is either an I-triomino or an L-triomino. The number of nodes within (n-1) squares of an I-triomino is n²+(n-1)²+2+4(n-1)=2n²+2n-1. The number of nodes within (n-1) squares of an L-triomino is smaller, so this gives an upper bound of 2n²+2n-1. Presumably even better bounds could be garnered by considering possible configurations after 2 steps, 3 steps, and so on, and hopefully these bounds would stabilize.

A lower bound:

Spoiler:

I have a pattern that produces 2n²+2n-9 nodes after n steps.

Code: Select all

...........
....F.F....
...FEFEF...
..FEDEDEF..
.FEDC.CDEF.
..FEBABEF..
.FEDC.CDEF.
..FEDEDEF..
...FEFEF...
....F.F....
...........

A, B, C, ... label generations. Hopefully it is clear how to continue the pattern.

So it is possible to get within 8 of the upper bound established above.

This pattern might also be useful for question 3. For large n, a good way of getting lots of dead nodes after n steps is to follow this pattern for nearly n steps, then spend a few steps killing off as much of the perimeter as possible.

7] What's the pattern that produces the fewest nodes (total live+dead)?

mfb's example would be a good candidate.

[Nitrodon]

6] What's the pattern that produces the most nodes (total live+dead)?

Some upper bounds:

Spoiler:

Each node at step n is within n squares of the original square (counting distance vertically/horizontally, not diagonally). This gives an upper bound of n²+(n+1)²=2n²+2n+1 on the number of nodes. You can do better by considering the configuration after 1 step, which is either an I-triomino or an L-triomino. The number of nodes within (n-1) squares of an I-triomino is n²+(n-1)²+2+4(n-1)=2n²+2n-1. The number of nodes within (n-1) squares of an L-triomino is smaller, so this gives an upper bound of 2n²+2n-1. Presumably even better bounds could be garnered by considering possible configurations after 2 steps, 3 steps, and so on, and hopefully these bounds would stabilize.

A lower bound:

Spoiler:

I have a pattern that produces 2n²+2n-9 nodes after n steps.

Code: Select all

...........
....F.F....
...FEFEF...
..FEDEDEF..
.FEDC.CDEF.
..FEBABEF..
.FEDC.CDEF.
..FEDEDEF..
...FEFEF...
....F.F....
...........

A, B, C, ... label generations. Hopefully it is clear how to continue the pattern.

So it is possible to get within 8 of the upper bound established above.

This pattern might also be useful for question 3. For large n, a good way of getting lots of dead nodes after n steps is to follow this pattern for nearly n steps, then spend a few steps killing off as much of the perimeter as possible.

Spoiler:

We only need to consider spaces within (n-1) squares of the endpoints of the I-triomino (not the center), so the upper bound is 2n²+2n-3. Continuing from the I-triomino, any choice for the second step seems to eliminate at least 4 more possible nodes (2 in a straight line in the directions not chosen from each of 2 reproducing nodes), giving an upper bound of 2n²+2n-7. The following pattern attains this bound:

Code: Select all

.............
.....F.......
....FEF.F....
...FEDEFEF...
..FEFCDEDEF..
.FEDCBABCDEF.
..FEDEDCFEF..
...FEFEDEF...
....F.FEF....
.......F.....
.............

[skeptical scientist]

8] Is there a pattern such that the height always stays bounded?

[Qaanol]

8] Is there a pattern such that the height always stays bounded?

Spoiler:

Code: Select all

 JIHGFEDCDEFGHIJ 
  JIHGFEBCDEFGHIJ
       DAD       
JIHGFEDCBEFGHIJ  
 JIHGFEDCDEFGHIJ 


Edit to show the lineages more clearly:

Spoiler:

Code: Select all

    J ― I ― H ― G ― F ― E ― D ― C ― D   E   F   G   H   I   J     
        |   |   |   |   |   |   |       |   |   |   |   |   |     
        J   I   H   G   F   E   B ― C ― D ― E ― F ― G ― H ― I ― J
                                |   |                                         
                            D   A   D                                         
                            |   |                                               
J ― I ― H ― G ― F ― E ― D ― C ― B   E   F   G   H   I   J           
    |   |   |   |   |   |       |   |   |   |   |   |   |           
    J   I   H   G   F   E   D ― C ― D ― E ― F ― G ― H ― I ― J     

And another option for displaying them:

Spoiler:

Code: Select all

░░░░░░░░░░░░░░░░░░░
░▫╦╦╦╦╦╦╦╦╕╓╓╓╓╓╓▫░
░░▫╜╜╜╜╜╜╠╦╩╩╩╩╩╩╩▫
░░░░░░░░╖╫╙░░░░░░░░
▫╦╦╦╦╦╦╦╩╣╓╓╓╓╓╓▫░░
░▫╜╜╜╜╜╜╘╩╩╩╩╩╩╩╩▫░
░░░░░░░░░░░░░░░░░░░

Code: Select all

░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
░ ▫ ╦═╦═╦═╦═╦═╦═╦═╦═╕ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░
░ ░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╠═╦═╩═╩═╩═╩═╩═╩═╩ ▫
░ ░ ░ ░ ░ ░ ░ ░ ╖ ╫ ╙ ░ ░ ░ ░ ░ ░ ░ ░
▫ ╦═╦═╦═╦═╦═╦═╦═╩═╣ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░ ░
░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╘═╩═╩═╩═╩═╩═╩═╩═╩ ▫ ░
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░

[\oo|- [-_-] -|oo/]

Spoiler:

Code: Select all

░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
░ ▫ ╦═╦═╦═╦═╦═╦═╦═╦═╕ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░
░ ░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╠═╦═╩═╩═╩═╩═╩═╩═╩ ▫
░ ░ ░ ░ ░ ░ ░ ░ ╖ ╫ ╙ ░ ░ ░ ░ ░ ░ ░ ░
▫ ╦═╦═╦═╦═╦═╦═╦═╩═╣ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░ ░
░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╘═╩═╩═╩═╩═╩═╩═╩═╩ ▫ ░
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░

6 6 6 g Q a (enter)

[Qaanol]

Spoiler:

Code: Select all

░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
░ ▫ ╦═╦═╦═╦═╦═╦═╦═╦═╕ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░
░ ░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╠═╦═╩═╩═╩═╩═╩═╩═╩ ▫
░ ░ ░ ░ ░ ░ ░ ░ ╖ ╫ ╙ ░ ░ ░ ░ ░ ░ ░ ░
▫ ╦═╦═╦═╦═╦═╦═╦═╩═╣ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░ ░
░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╘═╩═╩═╩═╩═╩═╩═╩═╩ ▫ ░
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░

6 6 6 g Q a (enter)

What? Are you trying to say my post didn’t show up properly for you? Here is what it is supposed to look like:

Screen shot 2011-11-10 at 8.47.32 PM.PNG (10.66 KiB) Viewed 1169 times

[\oo|- [-_-] -|oo/]

Not at all. What I meant was, it looked like Nethack.

[madprocess]

How is the order of reproduction determined? It looks like it's radiating outward from the center, but I'm having trouble figuring out the preferences. For instance, in generations 2 and 3, the topmost cell reproduces to North and West, while in generation 4 the topmost cell reproduces to North and East. I assume it has something to due with the ordering of reproduction, but I would have thought that since the cell to its West was unoccupied it would have gone there.

[Qaanol]

We, the omniscient overseers, choose which squares reproduce at each time-step. The puzzle is to determine what outcomes are possible, given that we must make our choices obey the given rules.

[WarDaft]

Can we build a bounded height tree in three dimensions? Death is a bit less convenient there.

If we can, is there a least dimensionality which does not permit us to bound the structure in at least 1 direction? What about at least N directions?

Another question, of a slightly extended puzzle: If we add another type of note, the connecting line, such that a note can have its sub notes connected by straight orthogonal lines of finite length, can we find room for all notes? Or is it always a loosing battle, with the time to the first note death determined by the particular lengths we have chosen?


For the moment, I am finding myself resorting to Minecraft to experiment with the 3rd dimension. Is this a bad thing? (1 hour later) This is a bad thing.

[mfb]

Another question, of a slightly extended puzzle: If we add another type of note, the connecting line, such that a note can have its sub notes connected by straight orthogonal lines of finite length, can we find room for all notes? Or is it always a loosing battle, with the time to the first note death determined by the particular lengths we have chosen?

For nodes with maximal spread length d, the reachable area after step n is O((nd)^2), while we get 2^n living nodes if nothing dies. The second one will surpass the first one at some point, and we have to have dying nodes.

>> Can we build a bounded height tree in three dimensions?
I think it is possible to build a suicide pattern in d>2 dimensions, if that is true the bounded height is trivial. Nodes tend to die a bit later, but building walls and change the direction of growth is much easier.