Совпадения чисел и их квадратов

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Один остаток квадратов
  2. Проверка указанного числа

    Сначала: Один остаток квадратов

  3. Ответ: да

    Сначала: Проверка указанного числа

  4. Один остаток квадратов

    Сначала: Ответ: да

  5. Проверка указанного числа

    Сначала: Один остаток квадратов

  6. Ответ: нет

    Сначала: Проверка указанного числа

  7. Один остаток квадратов

    Сначала: Ответ: нет

  8. Цепочки возведения в квадрат

    Сначала: Один остаток квадратов

  9. Выбор цепочек

    Сначала: Цепочки возведения в квадрат

  10. Ответ

    Сначала: Выбор цепочек

Разобранный пример

Коля записал на доске 20 различных натуральных чисел, каждое из которых меньше 1000. Петя записал на доске квадраты всех чисел, которые записал Коля. Получилось так, что среднее арифметическое любых трёх чисел, которые записал Петя, — целое число. Одно из чисел, записанных на доске, равно 625.

а) Может ли на доске быть записано число 1081610816?

б) Может ли на доске быть записано число 9363693636?

в) Какое наибольшее количество пар одинаковых чисел может быть написано на доске?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
N=20N=20
H=1000H=1000
K=625K=625
Шаг 2. Число на доске могло быть исходным допустимым числом либо квадратом допустимого исходного числа. Проверяем оба случая, учитывая натуральность, верхнюю границу и неделимость на 3. При возможности оставшиеся места заполняются любыми другими допустимыми числами.
T=(104)\mathcal T=\left(104\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
N=20N=20
H=1000H=1000
K=625K=625
Шаг 2. Число на доске могло быть исходным допустимым числом либо квадратом допустимого исходного числа. Проверяем оба случая, учитывая натуральность, верхнюю границу и неделимость на 3. При возможности оставшиеся места заполняются любыми другими допустимыми числами.
T={}\mathcal T=\left\{\right\}
Шаг 3. Нет. Необходимое ограничение или полная конечная область исключает такой случай.
Шаг 1. Сравнивая две тройки с двумя общими числами, получаем, что все записанные квадраты имеют один остаток по модулю 3. Указанное в условии число является исходным числом или квадратом исходного. В данном домене оно не делится на 3, поэтому и все исходные числа не делятся на 3, а их квадраты дают остаток 1.
Шаг 2. Совпадение исходного числа с записанным квадратом означает, что в исходном наборе одновременно есть uu и u2u^{2}. Все допустимые исходные числа разбиваются на цепочки u, u2, u4, …u,\,u^{2},\,u^{4},\,\ldots до заданной границы; число 1 образует отдельную петлю. В цепочке из ll чисел выбор t>0t>0 членов даёт не больше t−1t-1 совпадений, а подряд идущие tt членов достигают этой границы. Для 1 выбор даёт одно совпадение.
Шаг 3. Распределяем NN мест между конечными цепочками. Для каждой цепочки пробуем 0≤t≤l0\leq t\leq l и сохраняем наибольшее число совпадений при каждом общем количестве мест. Это все варианты распределения; для фиксированного tt уже известны точная верхняя граница и конструкция. Цепочка, содержащая указанное число или его корень, обязательно выбирается. Таблица содержит выбранные исходные числа и совпадающие значения.
T=((1;2;4;16;256;5;25;625;22;484;23;529;26;676;28;784;29;841;31;961);(1;4;16;256;25;625;484;529;676;784;841;961))\mathcal T=\left(\left(1;2;4;16;256;5;25;625;22;484;23;529;26;676;28;784;29;841;31;961\right);\left(1;4;16;256;25;625;484;529;676;784;841;961\right)\right)
Шаг 4. Записываем полученное значение или набор.
1212

Открыть задачу целиком

Попробовать самостоятельно