Grandfather problem: Difference between revisions
Jump to navigation
Jump to search
→Next levels: replace rle with pname in viewer |
Haycat2009 (talk | contribs) m →Optimization: Remove redundant |
||
| (6 intermediate revisions by 5 users not shown) | |||
| Line 6: | Line 6: | ||
|bx = 24 | |bx = 24 | ||
|by = 23 | |by = 23 | ||
|symmetry = C1 | |||
|synthesis = 0 | |synthesis = 0 | ||
|discoverer = mtve | |discoverer = mtve | ||
| Line 19: | Line 20: | ||
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}} | 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]] to discover {{OEIS|A196447}}:<ref name="mtve2" /> | 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" /> | ||
| Line 28: | Line 29: | ||
The final configuration has a total of 17920 parents, but no grandparents. | The final configuration has a total of 17920 parents, but no grandparents. | ||
==Verification== | == Verification == | ||
mtve's discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps:<ref name="sokwe" /> | mtve's discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps:<ref name="sokwe" /> | ||
| Line 34: | Line 35: | ||
# 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". | # 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== | == Optimization == | ||
It is possible to reduce the size of this pattern by removing some cells, and | It is possible to reduce the size of this pattern by removing some cells, and other patterns with the same property exist.<ref name="mtve3" /> | ||
{{EmbedViewer | {{EmbedViewer | ||
| Line 45: | Line 46: | ||
}} | }} | ||
==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;" | {|style="margin:auto;width:300px;" | ||
| Line 64: | Line 65: | ||
|} | |} | ||
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 | 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 == | ||
<references> | <references> | ||
<ref name="lifelinevol6">{{CiteLifeline | <ref name="lifelinevol6">{{CiteLifeline | ||
| Line 120: | Line 121: | ||
|author = Ilkka Törmä | |author = Ilkka Törmä | ||
|date = January 6, 2022 | |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== | == External links == | ||
{{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}} | {{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}} | ||
[[Category:Patterns discovered by pseudonymous users]] | [[Category:Patterns discovered by pseudonymous users]] | ||
Latest revision as of 08:43, 3 October 2024
| Grandfather problem | |||||||
| View static image | |||||||
| Pattern type | Problem | ||||||
|---|---|---|---|---|---|---|---|
| Number of cells | 298 | ||||||
| Bounding box | 24 × 23 | ||||||
| Static symmetry | C1 | ||||||
| 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 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