Коля записал на доске 20 различных натуральных чисел, каждое из которых меньше 1000. Петя записал на доске квадраты всех чисел, которые записал Коля. Получилось так, что среднее арифметическое любых трёх чисел, которые записал Петя, — целое число. Одно из чисел, записанных на доске, равно 625.
а) Может ли на доске быть записано число 10816?
б) Может ли на доске быть записано число 93636?
в) Какое наибольшее количество пар одинаковых чисел может быть написано на доске?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
N=20
H=1000
K=625
Шаг 2. Число на доске могло быть исходным допустимым числом либо квадратом допустимого исходного числа. Проверяем оба случая, учитывая натуральность, верхнюю границу и неделимость на 3. При возможности оставшиеся места заполняются любыми другими допустимыми числами.
T=(104)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
N=20
H=1000
K=625
Шаг 2. Число на доске могло быть исходным допустимым числом либо квадратом допустимого исходного числа. Проверяем оба случая, учитывая натуральность, верхнюю границу и неделимость на 3. При возможности оставшиеся места заполняются любыми другими допустимыми числами.
T={}
Шаг 3. Нет. Необходимое ограничение или полная конечная область исключает такой случай.
Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
Шаг 2. Совпадение исходного числа с записанным квадратом означает, что в исходном наборе одновременно есть u и u2. Все допустимые исходные числа разбиваются на цепочки u,u2,u4,… до заданной границы; число 1 образует отдельную петлю. В цепочке из l чисел выбор t>0 членов даёт не больше t−1 совпадений, а подряд идущие t членов достигают этой границы. Для 1 выбор даёт одно совпадение.
Шаг 3. Распределяем N мест между конечными цепочками. Для каждой цепочки пробуем 0≤t≤l и сохраняем наибольшее число совпадений при каждом общем количестве мест. Это все варианты распределения; для фиксированного t уже известны точная верхняя граница и конструкция. Цепочка, содержащая указанное число или его корень, обязательно выбирается. Таблица содержит выбранные исходные числа и совпадающие значения.