Задача для 6-го класса, оказавшаяся не по зубам

[gipokrat]

Расставьте в строку как можно больше различных двузначных чисел так, чтобы в любой тройке подряд идущих сумма первых двух делилась на третье (как, например, в тройке 20, 70, 30).

Источник задачи: https://mmmf.msu.ru/archive/20102011/z6/26.html (задача номер 3).

С помощью компьютерного поиска мне удалось найти допустимую строку из 69 различных двузначных чисел, так что ответ точно не что-то вроде 10 или 20. Теперь охочусь за настоящим потолком.

Вот строка из 69 чисел:

72, 24, 48, 36, 84, 12, 96, 18, 38, 28, 66, 94, 80, 58, 46, 52, 98, 10, 54, 16, 70, 86, 39, 25, 64, 89, 51, 35, 43, 26, 69, 19, 22, 41, 21, 62, 83, 29, 56, 85, 47, 33, 20, 53, 73, 63, 17, 40, 57, 97, 77, 87, 82, 13, 95, 27, 61, 44, 15, 59, 37, 32, 23, 11, 34, 45, 79, 31, 55.

Пожалуйста, помогите решить.
Заранее благодарю!

(Капелька юмора)

Вообще-то у среднестатистического шестиклассница (или шестиклассницы) зубов побольше, чем у меня. Поэтому неудивительно, что шестиклассникам эта задача по зубам, а мне не по зубам.

===UPD===

ChatGPT помог найти строку из 71 числа: 48, 60, 12, 72, 84, 78, 54, 66, 30, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 36, 79.

Но максимум ли это, вот в чём вопрос!

[Gagarin1968]

Построил строку из 44 чисел: 57, 24, 81, 15, 48, 21, 69, 30, 11, 41, 13, 27, 20, 47, 67, 19, 43, 62, 35, 97, 33, 65, 49, 38, 87, 25, 14, 39, 53, 46, 99, 29, 64, 31, 95, 63, 79, 71, 75, 73, 37, 55, 23, 26.
Но без компьютерного поиска и всяких ИИ. Начал с 57, потому что это год моего рождения.
Правда, убил полтора часа своей жизни.

[wrest]

gipokrat в сообщении #1734338 писал(а):

ChatGPT помог найти строку из 71 числа:

Ну я обычно прошу написать скрипт на pari.gp или программу на Си, которая найдёт максимальное решение. Пробовали? Питон не рекомендую - будет медленно если вычислений много. pari/gp иногда оказывается труден для ИИ по синтаксису, а вот Си/Си++ идёт на ура. Причём ИИ легко пишет многопоточные программы, так что если в компе достаточно ядер, ускорение заметное будет. Но это конечно если долго считать.

[gipokrat]

Gagarin1968 в сообщении #1734342 писал(а):

Построил строку из 44 чисел: 57, 24, 81, 15, 48, 21, 69, 30, 11, 41, 13, 27, 20, 47, 67, 19, 43, 62, 35, 97, 33, 65, 49, 38, 87, 25, 14, 39, 53, 46, 99, 29, 64, 31, 95, 63, 79, 71, 75, 73, 37, 55, 23, 26.
Но без компьютерного поиска и всяких ИИ. Начал с 57, потому что это год моего рождения.
Правда, убил полтора часа своей жизни.

Gagarin1968, спасибо! 44 числа вручную за полтора часа, по-моему, очень даже неплохо.

Кстати, Вашу строку уже нельзя просто продлить с краёв: справа подошло бы только 49, а слева 15, 39, 63 или 87, но все эти числа уже использованы. Интересно, как Вы её строили: только дописывали числа или приходилось возвращаться назад и переделывать?

-- добавлено через 3 минуты --

wrest в сообщении #1734344 писал(а):

Ну я обычно прошу написать скрипт на pari.gp или программу на Си, которая найдёт максимальное решение. Пробовали? Питон не рекомендую - будет медленно если вычислений много. pari/gp иногда оказывается труден для ИИ по синтаксису, а вот Си/Си++ идёт на ура. Причём ИИ легко пишет многопоточные программы, так что если в компе достаточно ядер, ускорение заметное будет. Но это конечно если долго считать.

wrest, спасибо! Да, ChatGPT уже написал программу на C++. Она строит строки справа налево и использует отсечение по НОД двух крайних левых чисел. По результатам полного перебора максимальная длина получается 71.

Исходник есть, но хотелось бы независимой проверки полноты перебора и корректности отсечений. А ещё интереснее было бы получить доказательство верхней границы без компьютерного перебора.

[Gagarin1968]

gipokrat в сообщении #1734345 писал(а):

Интересно, как Вы её строили: только дописывали числа или приходилось возвращаться назад и переделывать?

Да, приходилось возвращаться и переделывать. Сначала я быстро получил цепочку из 20 чисел, а потом, каждый раз исправляя и возвращаясь назад, довёл до 44.
И таки да, продлить её уже нельзя.

[Dmitriy40]

gipokrat в сообщении #1734345 писал(а):

По результатам полного перебора максимальная длина получается 71.

Исходник есть, но хотелось бы независимой проверки полноты перебора и корректности отсечений.

Подтверждаю, максимальная длина 71, вот все такие цепочки:

24, 96, 40, 68, 36, 52, 88, 10, 98, 54, 76, 26, 34, 60, 94, 22, 58, 80, 46, 18, 32, 50, 82, 66, 74, 70, 72, 71, 13, 42, 55, 97, 38, 45, 83, 64, 21, 85, 53, 69, 61, 65, 63, 16, 79, 95, 29, 31, 15, 23, 19, 14, 33, 47, 20, 67, 87, 77, 41, 59, 25, 12, 37, 49, 43, 92, 27, 17, 11, 28, 39

48, 96, 72, 56, 64, 20, 84, 52, 68, 12, 80, 46, 42, 88, 10, 98, 54, 76, 26, 34, 60, 94, 22, 58, 16, 74, 45, 17, 62, 79, 47, 18, 65, 83, 37, 30, 67, 97, 41, 69, 55, 31, 86, 39, 25, 32, 57, 89, 73, 81, 14, 19, 33, 13, 23, 36, 59, 95, 77, 43, 15, 29, 11, 40, 51, 91, 71, 27, 49, 38, 87

72, 96, 84, 60, 36, 24, 30, 18, 48, 22, 10, 32, 42, 74, 58, 66, 62, 16, 78, 94, 86, 12, 98, 55, 51, 53, 26, 79, 21, 50, 71, 11, 82, 93, 35, 64, 33, 97, 65, 81, 73, 77, 25, 34, 59, 31, 15, 23, 38, 61, 99, 20, 17, 37, 54, 13, 67, 80, 49, 43, 46, 89, 27, 29, 56, 85, 47, 44, 91, 45, 68

72, 96, 84, 60, 36, 12, 48, 30, 78, 54, 66, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43

48, 96, 72, 84, 12, 32, 44, 76, 60, 68, 64, 66, 26, 46, 24, 70, 94, 82, 22, 52, 74, 42, 58, 20, 78, 98, 88, 62, 15, 77, 92, 13, 21, 34, 55, 89, 16, 35, 51, 43, 47, 18, 65, 83, 37, 30, 67, 97, 41, 69, 11, 80, 91, 19, 10, 29, 39, 17, 28, 45, 73, 59, 33, 23, 56, 79, 27, 53, 40, 31, 71
96, 48, 36, 84, 12, 32, 44, 76, 60, 68, 64, 66, 26, 46, 24, 70, 94, 82, 22, 52, 74, 42, 58, 20, 78, 98, 88, 62, 15, 77, 92, 13, 21, 34, 55, 89, 16, 35, 51, 43, 47, 18, 65, 83, 37, 30, 67, 97, 41, 69, 11, 80, 91, 19, 10, 29, 39, 17, 28, 45, 73, 59, 33, 23, 56, 79, 27, 53, 40, 31, 71

24, 60, 84, 12, 96, 36, 22, 58, 40, 98, 46, 18, 32, 50, 82, 44, 42, 86, 64, 30, 94, 62, 78, 70, 74, 72, 73, 29, 34, 21, 55, 38, 31, 23, 27, 25, 52, 11, 63, 37, 20, 57, 77, 67, 16, 83, 99, 91, 95, 93, 47, 14, 61, 15, 76, 13, 89, 17, 53, 35, 88, 41, 43, 28, 71, 33, 26, 59, 85, 48, 19
60, 24, 84, 12, 96, 36, 22, 58, 40, 98, 46, 18, 32, 50, 82, 44, 42, 86, 64, 30, 94, 62, 78, 70, 74, 72, 73, 29, 34, 21, 55, 38, 31, 23, 27, 25, 52, 11, 63, 37, 20, 57, 77, 67, 16, 83, 99, 91, 95, 93, 47, 14, 61, 15, 76, 13, 89, 17, 53, 35, 88, 41, 43, 28, 71, 33, 26, 59, 85, 48, 19

24, 72, 96, 84, 36, 60, 48, 18, 22, 20, 42, 62, 52, 38, 30, 34, 32, 66, 98, 82, 90, 86, 44, 26, 14, 40, 54, 94, 74, 56, 13, 69, 41, 10, 51, 61, 16, 77, 31, 27, 29, 28, 57, 85, 71, 12, 83, 95, 89, 46, 45, 91, 68, 53, 11, 64, 15, 79, 47, 63, 55, 59, 19, 78, 97, 35, 33, 17, 25, 21, 23
24, 72, 96, 84, 36, 60, 48, 18, 22, 20, 42, 62, 52, 38, 30, 34, 32, 66, 98, 82, 90, 86, 44, 26, 14, 40, 54, 94, 74, 56, 13, 69, 41, 10, 51, 61, 16, 77, 31, 27, 29, 28, 57, 85, 71, 12, 83, 95, 89, 46, 45, 91, 68, 53, 11, 64, 15, 79, 47, 63, 55, 59, 19, 78, 97, 35, 33, 17, 50, 67, 39

48, 96, 36, 44, 40, 28, 68, 32, 20, 52, 12, 64, 76, 14, 90, 26, 58, 42, 50, 46, 24, 70, 94, 82, 88, 10, 98, 27, 25, 13, 38, 51, 89, 35, 62, 97, 53, 15, 34, 49, 83, 33, 29, 31, 30, 61, 91, 19, 55, 37, 92, 43, 45, 11, 56, 67, 41, 18, 59, 77, 17, 47, 16, 63, 79, 71, 75, 73, 74, 21, 95
72, 96, 84, 60, 48, 36, 28, 32, 20, 52, 12, 64, 76, 14, 90, 26, 58, 42, 50, 46, 24, 70, 94, 82, 88, 10, 98, 27, 25, 13, 38, 51, 89, 35, 62, 97, 53, 15, 34, 49, 83, 33, 29, 31, 30, 61, 91, 19, 55, 37, 92, 43, 45, 11, 56, 67, 41, 18, 59, 77, 17, 47, 16, 63, 79, 71, 75, 73, 74, 21, 95
84, 96, 36, 44, 40, 28, 68, 32, 20, 52, 12, 64, 76, 14, 90, 26, 58, 42, 50, 46, 24, 70, 94, 82, 88, 10, 98, 27, 25, 13, 38, 51, 89, 35, 62, 97, 53, 15, 34, 49, 83, 33, 29, 31, 30, 61, 91, 19, 55, 37, 92, 43, 45, 11, 56, 67, 41, 18, 59, 77, 17, 47, 16, 63, 79, 71, 75, 73, 74, 21, 95

72, 96, 84, 60, 36, 24, 30, 54, 12, 66, 78, 48, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 18
96, 84, 60, 36, 12, 48, 30, 78, 54, 66, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 72, 23, 19, 21, 40
96, 84, 60, 36, 12, 48, 30, 78, 54, 66, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 72

48, 60, 12, 72, 84, 78, 54, 66, 30, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 36, 79
72, 96, 84, 12, 48, 30, 78, 54, 66, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 36, 79
96, 60, 12, 72, 84, 78, 54, 66, 30, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 36, 79
96, 72, 84, 12, 48, 30, 78, 54, 66, 24, 18, 42, 10, 52, 62, 38, 50, 44, 94, 46, 70, 58, 16, 74, 90, 82, 86, 28, 57, 85, 71, 39, 55, 47, 17, 64, 27, 91, 59, 25, 21, 23, 22, 15, 37, 26, 63, 89, 76, 11, 87, 49, 34, 83, 13, 32, 45, 77, 61, 69, 65, 67, 33, 20, 53, 73, 14, 29, 43, 36, 79

[wrest]

Dmitriy40 в сообщении #1734352 писал(а):

Подтверждаю, максимальная длина 71

Какие ваши доказательства? (с)

[Dmitriy40]

wrest в сообщении #1734358 писал(а):

Какие ваши доказательства? (с)

Полный перебор другой (от ТС) программой (на любимом асме) за минут 40.

-- добавлено через 5 минут --

Что интересно, для однозначных чисел 1..9 максимальная длина равна 9, таких вариантов аж 16шт (и все с чётного числа слева).

[wrest]

Dmitriy40 в сообщении #1734359 писал(а):

(на любимом асме) за минут 40.

фантастика круто, чо уж.

[gipokrat]

Dmitriy40 в сообщении #1734359 писал(а):

-- добавлено через 5 минут --

Что интересно, для однозначных чисел 1..9 максимальная длина равна 9, таких вариантов аж 16шт (и все с чётного числа слева).

А как с трёхзначными дела обстоят?

[Dmitriy40]

gipokrat в сообщении #1734361 писал(а):

А как с трёхзначными дела обстоят?

Пока нашёл лишь максимальной длиной 335. Но левые примерно 120 ещё не начали перебираться (перебор слева направо), так что это явно совсем не предел.
Забавно что 4 таких цепочки отличаются где-то в середине, начало и конец идентичные.
Интересно что для трёхзначных похоже выгоднее перебор слева направо: слева направо на PARI нашлись цепочки длиной 335, а справа налево на асме лишь длиной 151 ... Писать перебор слева направо на асме/С что-то пока лень. По моему там основное время тратится не на проверку варианта, а на копирование маски использованных чисел, надо бы подумать как это дело оптимизировать.