Задача к ЕГЭ по информатике на тему «действия над цифрами числа» №2

Автомат получает на вход пятизначное число. По этому числу строится новое число по таким правилам:

Складываются квадраты цифр, стоящих на нечетных позициях;
Складываются квадраты цифр, стоящих на четных позициях;
Затем в порядке неубывания записываются эти суммы.

Укажите наименьшее число, при вводе которого автомат выдает число 72128.

Решение прогой

for i in range(10 ** 4, 10 ** 5):
    x = str(i)
    sumOddPos = int(x[0]) ** 2 + int(x[2]) ** 2 + int(x[4]) ** 2
    sumEvenPos = int(x[1]) ** 2 + int(x[3]) ** 2
    num = str(min(sumOddPos, sumEvenPos)) + str(max(sumOddPos, sumEvenPos))
    if num == "72128":
        print(i)
        break

Решение аналитически

Сумма квадратов $3$ чисел принадлежит промежутку [0,243], а сумма квадратов $2$ чисел промежутку [0,162]. В соответствие с этими правилами число 72128 разбивается на числа $72$ и $128$ . Всего на нечетных позициях в пятизначном числе стоит $3$ цифры, на четных — $2$ цифры.

Определим сначала, какие цифры могут стоять на четных позициях. Это можно сделать с помощью перебора всех комбинаций x и y, которые являются решениями уравнения $x2 + y2 = N.$ Потенциально самое большое значение наименьшего разряда (а соответственно и самое маленькое значение наибольшего разряда) может быть в решении уравнения с суммой квадратов неизвестных, равных наибольшему из найденных ранее чисел, т.е. $128$ . Тогда положим, что $N = 72,$ чтобы в уравнении для цифр на нечетных позициях можно было задать более высокую верхнюю границу и в перспективе поставить самую большую цифру в разряд единиц, а самую маленькую — в разряд десятков тысяч. В текущем же уравнении для цифр на четных позициях $2 2 x + y = 72$ оба числа x и y не могут превышать значения 8. Подходящей (и единственной) комбинацией является {6, 6}.

Теперь найдем комбинацию цифр, которые должны стоять на нечетных позициях. Для этого положим три различные переменные в новое уравнение:

$2 2 2 x + y + z = 128$

Рассмотрим случай $x = y = z$ . Целых решений для $x$ в уравнении $2 3x = 128$ нет, поскольку $3$ не является делителем $128$ .

Далее рассмотрим $x = y.$ Необходимо подобрать такое значение $z$ , чтобы полуразность $128$ и квадрата $z$ была квадратом какого-либо натурального числа. Перебором приходим к выводу, что если $z = 0,$ то $2 2 2x = 128, x = 64, x = 8.$

Мы нашли частное решение 86860, рассмотрим последний случай, когда $x,y$ и $z$ различны между собой.

Будем брать $z = 9, 8,7...$ и таким образом искать случай, при котором можно будет получить такую сумму квадратов $2 2 x + y ,$ что одна из переменных $x$ или $y$ была бы меньше $8$ , а далее и меньше найденных в процессе цифр.

Если $z = 9,$ тогда $x2 + y2 = 128 − 81 = 47$ . Подходящих решений нет.

Если $z = 8,$ тогда $x2 + y2 = 128 − 64 = 64$ . Этот вариант уже был рассмотрен ранее.

Если $z = 7,$ тогда $x2 + y2 = 128 − 49 = 79$ . Подходящих решений нет.

Далее вплоть до $z = 0$ мы так и не найдем подходящих решений.

В таком случае поменяем константы в уравнениях для цифр на четных и нечетных позициях. Пусть для четных $x2 + y2 = 128,$ а для нечетных $x2 + y2 + z2 = 72$ . Пройдемся заново по тому же алгоритму. Для четных получим комбинацию {8,8}, а для нечетных {8,2,2}.

Таким образом, мы нашли наименьшее число $28288$ .

Ответ: 28288