|
%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
| 