A small puzzle.

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

A small puzzle.

Postby \oo|- [-_-] -|oo/ » Tue Nov 08, 2011 6:43 am UTC

So, I was taking notes on something1 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.2

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.

Image

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.
User avatar
\oo|- [-_-] -|oo/
 
Posts: 9
Joined: Sat May 05, 2007 1:48 am UTC

Re: A small puzzle.

Postby antonfire » Tue Nov 08, 2011 7:38 am UTC

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 2n nodes after n steps. But each of these nodes is at distance at most n from the origin, and there are only n2 or so places that close to the origin. (nd in higher dimensions.) 2n grows faster than nd 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.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
User avatar
antonfire
 
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: A small puzzle.

Postby Yakk » Tue Nov 08, 2011 3:08 pm UTC

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"?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10439
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A small puzzle.

Postby mfb » Tue Nov 08, 2011 9:20 pm UTC

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:
Image
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
Last edited by mfb on Wed Nov 09, 2011 10:49 am UTC, edited 1 time in total.
mfb
 
Posts: 838
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: A small puzzle.

Postby skeptical scientist » Wed Nov 09, 2011 3:28 am UTC

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 n2+(n+1)2=2n2+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 n2+(n-1)2+2+4(n-1)=2n2+2n-1. The number of nodes within (n-1) squares of an L-triomino is smaller, so this gives an upper bound of 2n2+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 2n2+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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6150
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A small puzzle.

Postby Nitrodon » Wed Nov 09, 2011 5:38 am UTC

skeptical scientist wrote: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 n2+(n+1)2=2n2+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 n2+(n-1)2+2+4(n-1)=2n2+2n-1. The number of nodes within (n-1) squares of an L-triomino is smaller, so this gives an upper bound of 2n2+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 2n2+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 2n2+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 2n2+2n-7. The following pattern attains this bound:

Code: Select all
.............
.....F.......
....FEF.F....
...FEDEFEF...
..FEFCDEDEF..
.FEDCBABCDEF.
..FEDEDCFEF..
...FEFEDEF...
....F.FEF....
.......F.....
.............
Nitrodon
 
Posts: 466
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: A small puzzle.

Postby skeptical scientist » Wed Nov 09, 2011 7:44 am UTC

8] Is there a pattern such that the height always stays bounded?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6150
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A small puzzle.

Postby Qaanol » Wed Nov 09, 2011 8:16 am UTC

skeptical scientist wrote: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
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
░ ▫ ╦═╦═╦═╦═╦═╦═╦═╦═╕ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░
░ ░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╠═╦═╩═╩═╩═╩═╩═╩═╩ ▫
░ ░ ░ ░ ░ ░ ░ ░ ╖ ╫ ╙ ░ ░ ░ ░ ░ ░ ░ ░
▫ ╦═╦═╦═╦═╦═╦═╦═╩═╣ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░ ░
░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╘═╩═╩═╩═╩═╩═╩═╩═╩ ▫ ░
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
Small Government Liberal
User avatar
Qaanol
 
Posts: 2551
Joined: Sat May 09, 2009 11:55 pm UTC

Re: A small puzzle.

Postby \oo|- [-_-] -|oo/ » Fri Nov 11, 2011 1:42 am UTC

Qaanol wrote:
Spoiler:
Code: Select all
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
░ ▫ ╦═╦═╦═╦═╦═╦═╦═╦═╕ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░
░ ░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╠═╦═╩═╩═╩═╩═╩═╩═╩ ▫
░ ░ ░ ░ ░ ░ ░ ░ ╖ ╫ ╙ ░ ░ ░ ░ ░ ░ ░ ░
▫ ╦═╦═╦═╦═╦═╦═╦═╩═╣ ╓ ╓ ╓ ╓ ╓ ╓ ▫ ░ ░
░ ▫ ╜ ╜ ╜ ╜ ╜ ╜ ╘═╩═╩═╩═╩═╩═╩═╩═╩ ▫ ░
░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░


6 6 6 g Q a (enter)
User avatar
\oo|- [-_-] -|oo/
 
Posts: 9
Joined: Sat May 05, 2007 1:48 am UTC

Re: A small puzzle.

Postby Qaanol » Fri Nov 11, 2011 1:49 am UTC

\oo|- [-_-] -|oo/ wrote:
Qaanol wrote:
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
Screen shot 2011-11-10 at 8.47.32 PM.PNG (10.66 KiB) Viewed 1207 times
Small Government Liberal
User avatar
Qaanol
 
Posts: 2551
Joined: Sat May 09, 2009 11:55 pm UTC

Re: A small puzzle.

Postby \oo|- [-_-] -|oo/ » Sat Nov 12, 2011 12:03 am UTC

Not at all. What I meant was, it looked like Nethack.
User avatar
\oo|- [-_-] -|oo/
 
Posts: 9
Joined: Sat May 05, 2007 1:48 am UTC

Re: A small puzzle.

Postby madprocess » Mon Nov 14, 2011 12:11 pm UTC

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.
User avatar
madprocess
 
Posts: 65
Joined: Mon Sep 18, 2006 9:35 pm UTC

Re: A small puzzle.

Postby Qaanol » Mon Nov 14, 2011 6:33 pm UTC

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.
Small Government Liberal
User avatar
Qaanol
 
Posts: 2551
Joined: Sat May 09, 2009 11:55 pm UTC

Re: A small puzzle.

Postby WarDaft » Mon Nov 14, 2011 7:09 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A small puzzle.

Postby mfb » Wed Nov 16, 2011 4:04 pm UTC

WarDaft wrote: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.
mfb
 
Posts: 838
Joined: Thu Jan 08, 2009 7:48 pm UTC


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 5 guests