Из натуральных чисел от 1 до 1967 Дима хочет выбрать несколько и выписать в ряд так,...

Question

Из натуральных чисел от 1 до 1967 Дима хочет выбрать несколько и выписать в ряд так, чтобы сумма любых четырех идущих подряд чисел не делилась на три, а сумма любых пяти последовательных в этом ряду чисел делилась на три. Какое наибольшее количество чисел может выбрать Дима?

Answer 1

Вместо заданных чисел 1,2,...,1907 можно рассматривать их остатки от деления на три: 1,2,0,1,2,0,...,0,1,2. Нуль нельзя выбирать, иначе в пятерке, где нуль крайний, найдётся четвёрка с суммой, кратной трём. Выбранная последовательность единиц и двоек периодична с периодом, равным пяти. Короткий перебор показывает, что в периоде должно быть ровно четыре одинаковых числа. Поскольку в исходном наборе единиц и двоек поровну, то искомым набором может быть такой2,1,1,1,1,2,1,1,1,1,...,2,1,1,1,1,2.В нём 636 единиц и 145 двоек.
итого 636+145=771 числа.