Difference between revisions of "Grandfather problem"
DroneBetter (talk | contribs) m (→Next levels: correct little-o to big-O (f(n)=o(g(n)) means lim_{n->∞} (f(n)/g(n)) = 0, not 1), forgo "equal to" (as apg did in citation) because it concerns asymptoticness, not equality) |
|||
(20 intermediate revisions by 5 users not shown) | |||
Line 9: | Line 9: | ||
|discoverer = mtve | |discoverer = mtve | ||
|discoveryear = 2016 | |discoveryear = 2016 | ||
|plaintext = true | |||
|rle = true | |rle = true | ||
|viewerconfig = #C [[ ZOOM 16 WIDTH 500 HEIGHT 500 ]] | |||
}} | }} | ||
The '''grandfather problem''' is the following question, posed by [[John Conway]] in 1972 in [[Lifeline Volume 6]],<ref name="lifelinevol6" /> along with the [[unique father problem]]: | The '''grandfather problem''' is the following question, posed by [[John Conway]] in 1972 in [[Lifeline Volume 6]],<ref name="lifelinevol6" /> along with the [[unique father problem]]: | ||
Line 15: | Line 17: | ||
:''Is there a configuration which has a father but no [[grandfather]]?'' | :''Is there a configuration which has a father but no [[grandfather]]?'' | ||
Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem remained open until May 2016, when | Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem of a '''grandfatherless''' pattern remained open until May {{year|2016}}, when [[mtve]] presented such a pattern.<ref name="mtve1" /> {{POTY|name=This pattern|year=2016|rank=3|behind=the [[copperhead]] and the [[Caterloopillar]]s}} | ||
==Generation== | ==Generation== | ||
The pattern was found with the [http://fmv.jku.at/picosat/ PicoSAT] SAT solver, using an algorithm similar to the one employed by [[Nicolay Beluchenko]] | The pattern was found with the [http://fmv.jku.at/picosat/ PicoSAT] SAT solver, using an algorithm similar to the one employed by [[Nicolay Beluchenko]] to discover {{OEIS|A196447}}:<ref name="mtve2" /> | ||
# Try setting the next cell on and off; | # Try setting the next cell on and off; | ||
# Skip first level [[ | # Skip first level [[Gardens of Eden]]; | ||
# Choose the minimum number of grandparents, where "minimum number" is not the exact number but a minimal distance between first and last. | # Choose the minimum number of grandparents, where "minimum number" is not the exact number but a minimal distance between first and last. | ||
Line 27: | Line 29: | ||
==Verification== | ==Verification== | ||
mtve's discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps:<ref name="sokwe" /> | |||
# Run a search to find all 1-generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern. | # Run a search to find all 1-generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern. | ||
Line 33: | Line 35: | ||
==Optimization== | ==Optimization== | ||
It is possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist<ref name="mtve3" /> | It is possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist.<ref name="mtve3" /> | ||
{{EmbedViewer | |||
|pname = grandfatherproblem22x22 | |||
|position = center | |||
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]] | |||
|caption = {{times|22|22}} grandfatherless pattern by mtve<ref name="mtve3" /> | |||
|style = width:300px; | |||
}} | |||
==Next levels== | ==Next levels== | ||
"A father and grandfather, but no great-grandfather" pattern<ref name="mtve4" /> | "A father and grandfather, but no great-grandfather" pattern<ref name="mtve4" /> and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern<ref name="mtve5" /> have also been constructed by the same method. | ||
{|style="margin:auto;width:300px;" | |||
|{{EmbedViewer | |||
|pname = greatgrandfatherproblem | |||
|position = center | |||
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]] | |||
|caption = Pattern with a father and grandfather, but no great-grandfather, by mtve in 2016<ref name="mtve4" /> | |||
}} | |||
|- | |||
|{{EmbedViewer | |||
|pname = greatgreatgrandfatherproblem | |||
|position = center | |||
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]] | |||
|caption = Pattern with a father, grandfather and great-grandfather, but no great-great-grandfather, by mtve in 2016<ref name="mtve5" /> | |||
}} | |||
|} | |||
On January 6, {{year|2022}}, [[Ilkka Törmä]] and [[Ville Salo]] solved a generalized version of the grandfather problem, proving that for every natural number n, there exists a pattern that has an n-tick predecessor but not an (n+1)-tick predecessor.<ref name="post139854" /> Furthermore, this pattern will fit in a box of diameter O(sqrt(log(n))).<ref name="post140273" /> | |||
==References== | ==References== | ||
Line 47: | Line 70: | ||
<ref name="lifelinevol6">{{CiteLifeline | <ref name="lifelinevol6">{{CiteLifeline | ||
|vol = 6 | |vol = 6 | ||
|pages = p. 1 | |pages = p. 1 | ||
}}</Ref> | }}</Ref> | ||
<ref name="mtve1">{{ | <ref name="mtve1">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |title = Re: Thread for your unsure discoveries | ||
| | |p = 30646 | ||
|date | |author = mtve | ||
|date = May 5, 2016 | |||
}}</ref> | }}</ref> | ||
<ref name="mtve2">{{ | <ref name="mtve2">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |||
|p = 30667 | |||
|author = mtve | |author = mtve | ||
|date = May 6, 2016 | |date = May 6, 2016 | ||
}}</ref> | }}</ref> | ||
<ref name="sokwe">{{ | <ref name="sokwe">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |title = Re: Thread for your unsure discoveries | ||
| | |p = 30694 | ||
|author = Matthias Merzenich | |||
|date = May 6, 2016 | |date = May 6, 2016 | ||
}}</ref> | }}</ref> | ||
<ref name="mtve3">{{cite web | <ref name="mtve3">{{cite web | ||
Line 94: | Line 113: | ||
|date = December 12, 2016 | |date = December 12, 2016 | ||
|accessdate = December 14, 2016 | |accessdate = December 14, 2016 | ||
}}</ref> | |||
<ref name="post139854">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Unproven conjectures | |||
|p = 139854 | |||
|author = Ilkka Törmä | |||
|date = January 6, 2022 | |||
}}</ref> | |||
<ref name="post140273">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Unproven conjectures | |||
|p = 140273 | |||
|author = Adam P. Goucher | |||
|date = January 13, 2022 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
==External links== | |||
{{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}} | |||
[[Category:Patterns discovered by pseudonymous users]] | [[Category:Patterns discovered by pseudonymous users]] |
Latest revision as of 12:26, 13 February 2023
Grandfather problem | |||||||
View static image | |||||||
Pattern type | Problem | ||||||
---|---|---|---|---|---|---|---|
Number of cells | 298 | ||||||
Bounding box | 24 × 23 | ||||||
Discovered by | mtve | ||||||
Year of discovery | 2016 | ||||||
| |||||||
|
The grandfather problem is the following question, posed by John Conway in 1972 in Lifeline Volume 6,[1] along with the unique father problem:
- Is there a configuration which has a father but no grandfather?
Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem of a grandfatherless pattern remained open until May 2016, when mtve presented such a pattern.[2] This pattern ranked third place in the Pattern of the Year 2016 competition on the ConwayLife.com forums, behind the copperhead and the Caterloopillars.[3]
Generation
The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko to discover A196447:[4]
- Try setting the next cell on and off;
- Skip first level Gardens of Eden;
- Choose the minimum number of grandparents, where "minimum number" is not the exact number but a minimal distance between first and last.
The final configuration has a total of 17920 parents, but no grandparents.
Verification
mtve's discovery was confirmed to solve the grandfather problem by Matthias Merzenich with JLS, using the following steps:[5]
- Run a search to find all 1-generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern.
- Mark all of unset cells with "X", increase the period by 1 and shift the pattern to the future by 1 generation. Set the outer cells to "X" in generation 0 and run another search, which eventually gives "Search finished: 0 solutions found".
Optimization
It is possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist.[6]
22 × 22 grandfatherless pattern by mtve[6] (click above to open LifeViewer) RLE: here Plaintext: here |
Next levels
"A father and grandfather, but no great-grandfather" pattern[7] and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[8] have also been constructed by the same method.
| ||
|
On January 6, 2022, Ilkka Törmä and Ville Salo solved a generalized version of the grandfather problem, proving that for every natural number n, there exists a pattern that has an n-tick predecessor but not an (n+1)-tick predecessor.[9] Furthermore, this pattern will fit in a box of diameter O(sqrt(log(n))).[10]
References
- ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
- ↑ mtve (May 5, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ Alexey Nigin (June 3, 2017). Pattern of the Year 2016 (Results) (discussion thread) at the ConwayLife.com forums
- ↑ mtve (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ Matthias Merzenich (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ 6.0 6.1 mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
- ↑ 7.0 7.1 mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
- ↑ 8.0 8.1 mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.
- ↑ Ilkka Törmä (January 6, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
External links
- Grandfatherless at the Life Lexicon