"Ниже записана программа. Получив на вход число x, эта программа печатает два числа L и M. Сколько существует натуральных чисел x, при вводе которых алгоритм печатает 6 и 0? "

Класс, давай разберёмся по шагам. Ты дал ответ "Ученик не дал ответ на задание" — это неверно. Вот подсказка, как подступиться к решению и прийти к числу 4 915 200.

Что нужно понять

• Программа, по входному x, печатает два числа L и M. Чтобы L стало 6, x должен иметь ровно 6 цифр в шестнадцатеричной системе счисления (то есть быть в диапазоне 16^5 … 16^6 − 1).
• Во время работы поразрядам по 16-ке M изменяется на +1, если текущая младшая цифра чётная, и на −1, если нечетная. Следовательно, после обработки 6 цифр M равен количеству чётных цифр минус количеству нечётных цифр. Чтобы M = 0, должно быть ровно три чётные цифры и три нечётные.

Перестройка задачи в counting

• x в диапазоне L = 6: x ∈ [16^5, 16^6 − 1].
  • 16^5 = 2^20, 16^6 = 2^24. Значит x ∈ [2^20, 2^24 − 1].
• В шестнадцатеричных цифрах это шесть цифр d5 d4 d3 d2 d1 d0, где d5 не равна 0 (потому что иначе не было бы 6 цифр).
  • Возможные значения младшей цифры (и вообще любой позиции) по mod 16 дают 8 чётных и 8 нечётных вариантов (0,2,4,6,8,A,C,E — чётные; 1,3,5,7,9,B,D,F — нечётные).
  • Для старшей цифры d5 допустимы значения 1…F. Среди них чётных 7 вариантов (2,4,6,8,A,C,E) и нечётных 8 вариантов (1,3,5,7,9,B,D,F).

Теперь посчитаем количество x с ровно тремя чётными цифрами

• Случай А: старшая цифра чётная. Тогда осталось выбрать 2 чётные цифры среди оставшихся 5 позиций.
  • Количество вариантов: 7 (для d5) × C(5,2) × 8^2 × 8^3 = 7 × 10 × 8^5 = 70 × 8^5.
• Случай Б: старшая цифра нечётная. Тогда нужно выбрать 3 чётные среди остальных 5 позиций.
  • Количество вариантов: 8 (для d5) × C(5,3) × 8^3 × 8^2 = 8 × 10 × 8^5 = 80 × 8^5.

Итого

• Общее количество x: (70 + 80) × 8^5 = 150 × 8^5.
• 8^5 = 32768, поэтому 150 × 32768 = 4 915 200.

Ответ: 4 915 200.

Замечания

• Обратите внимание на тонкости с диапазоном: L = 6 означает именно 6 шестнадцатеричных цифр, поэтому x ∈ [16^5, 16^6 − 1]. Пример в примере кода иногда включает 16^6, но такие значения уже дают L = 7 и не влияют на итоговый счёт, потому что условие M = 0 и L = 6 не выполняется для них.
• Можно было решить и перебором (как в примере), но красота здесь в комбинаторике: считать цифры по их чётности и учесть, что старшая цифра не ноль.

Пожалуйста, оцените мой ответ лайком или дизлайком.