login
Solution to Von Neumann stepping stone puzzle (see Comments).
1

%I #28 Mar 27 2021 03:58:54

%S 1,2,5,8,13,18,21,24,29,31,34,38,42,46

%N Solution to Von Neumann stepping stone puzzle (see Comments).

%C This is a variant of the stepping stone sequence (A337663), where any cell has just 4 neighbors (Von Neumann neighborhood). The game works as follows:

%C Start with an infinite square grid. Each cell has four neighbors. Place n 1's anywhere. Now place the numbers 2, 3, ..., m in order, subject to the rule that when you place k, the sum of its neighbors must equal k. Then a(n) is the maximum m that can be achieved.

%F a(n) >= 3n - 4 (found by _Thomas Ladouceur_).

%F The proof follows by this construction:

%F +----+----+----+----+----+----+----+

%F | 1 | 4 | 5 | 6 | 1 | 10 | 11 |

%F +----+----+----+----+----+----+----+

%F | 2 | 3 | 1 | 7 | 8 | 9 | 1 |

%F +----+----+----+----+----+----+----+

%F | 1 | | | | | | |

%F +----+----+----+----+----+----+----+

%e From code compiled by _Hugo van der Sanden_ and _Thomas Ladouceur_.

%e a(3) = 5, with 3 1's:

%e +----+----+----+

%e | 1 | 2 | 1 |

%e +----+----+----+

%e | 4 | 3 | |

%e +----+----+----+

%e | 5 | 1 | |

%e +----+----+----+

%e and

%e a(10) = 31, with 10 1's:

%e +----+----+----+----+----+----+----+----+----+----+

%e | | 9 | 8 | 1 | 11 | | | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | | 1 | 7 | 6 | 10 | | | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 28 | 27 | 12 | 5 | 4 | 1 | | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 1 | 14 | 13 | 1 | 3 | 2 | 1 | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 16 | 15 | | | 26 | 29 | 30 | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 17 | 1 | 21 | 22 | 23 | 1 | 31 | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 18 | 19 | 20 | 1 | 24 | 25 | | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%e | 1 | | | | | | | | | |

%e +----+----+----+----+----+----+----+----+----+----+

%Y Cf. A337663.

%K nonn,more,hard

%O 1,2

%A _Jeremy Rebenstock_, _Thomas Ladouceur_ Mar 12 2021

%E a(13)-a(14) from _Bert Dobbelaere_, Mar 19 2021