Question

Даня складывает из 2024 карточек, на которых написана цифра 1, и 2024 карточек, на которых написана цифра 2, 4048-значное число. За один ход Федя может поменять местами некоторые две карточки и заплатить Дане 1 фоксик. Процесс заканчивается, когда у Феди получается число, кратное 11. Найдите наибольшее число фоксиков, которые может получить Даня, если Федя стремится заплатить как можно меньше?

Answer 1

Уфф... Давно не решал олимпиадных задач по математике, что ж, попробуем)

Пусть А - число из 4048 знаков.

Из них в нечётных разрядах Х единиц и У = 2024 - Х двоек.

Тогда в чётных разрядах будет Х двоек и У единиц.

Заметим, что тут Х принимает любые значения в интервале от 0 до 2024.

Разность сумм цифр в нечётных и чётных разрядах равна:

(Х + 2У) - (2Х + У) = У - Х = 2024 - 2Х. Поскольку 2024 делится на 11, то число 2024 - 2Х делится на 11 тогда и только тогда, когда Х делится на 11.

За один ход Х изменяется не более чем на 1. Потому, если Даня изначально сложит число А, для которого, например, Х = 5, то Феде потребуется не менее 5 ходов для того, чтобы полученное число делилось на 11.

Пусть Х - отличное от нуля число. Тогда:

- меняя единицу, стоящую в нечётном разряде, с двойкой, которая стоит в чётном, Федя уменьшает Х на единицу;

- меняя двойку, стоящую в нечётном разряде, с единицей, стоящей в чётном, он увеличивает за один ход Х на 1, если Х - число, отличное от 2024.

Пусть начальное число даёт при делении на 11 остаток R. Тогда:

- если R = 0, то число делится на 11, и Феде ничего делать не нужно.

- если R лежит в интервале от 1 до 5 включительно, то за R своих ходов Федя может уменьшить Х на величину R до ближайшего числа, кратного 11;

- если R лежит в интервале от 6 до 10 включительно, то за 11 - R своих ходов Федя увеличивает Х на величину 11 - R до ближайшего числа, кратного 11. Это возможно, так как наибольшее значение Х, равное 2024, кратно 11.

Поэтому минимальное число ходов для Феди равно 5. И при этом он стремится, если верить условию, заплатить как можно меньше. А значит, Даня может получить не более, чем 5 фоксиков.

Ответ: 5 фоксиков.