|
|
 |
Условие
Имеются 2013 карточек, на которых написана цифра 1, и 2013 карточек, на которых написана цифра 2. Вася складывает из этих карточек 4026-значное число. За один ход Петя может поменять местами некоторые две карточки и заплатить Васе 1 рубль. Процесс заканчивается, когда у Пети получается число, кратное 11. Какую наибольшую сумму может заработать Вася, если Петя стремится заплатить как можно меньше?
Решение
Рассмотрим 4026-значное число A, состоящее из 2013 единиц и 2013 двоек. Пусть в этом числе в нечётных разрядах стоит k единиц и l = 2013 – k двоек, тогда в чётных разрядах будет k двоек и l единиц (здесь k может принимать любое целое значение от 0 до 2013). Разность сумм цифр в нечётных разрядах и чётных разрядах равна (k + 2l) – (2k + l) = l – k = 2013 – 2k. Поскольку 2013 кратно 11, то A кратно 11 тогда и только тогда, когда k кратно 11.
За один ход k изменяется не более чем на 1. Поэтому, если Вася изначально сложит число A, для которого, скажем k = 5 (очевидно, это возможно), то Пете потребуется не менее 5 ходов, чтобы получить число, для которого k кратно 11.
Покажем, что пяти ходов Пете всегда хватит. Меняя некоторую единицу, стоящую в нечётном разряде, с двойкой, стоящей в чётном разряде, он может уменьшить k на 1 за один ход, если только k ≠ 0. Аналогично, меняя некоторую двойку, стоящую в нечётном разряде, с единицей, стоящей в чётном разряде, он может увеличить k на 1 за один ход, если только k ≠ 2013. Пусть начальное Васино число давало остаток r при делении на 11. Если r = 0, то исходное число уже делится на 11, и ничего делать не нужно. Если 1 ≤ r ≤ 5, то за r операций Петя может уменьшить k на r до ближайшего числа, кратного 11. Если же 6 ≤ r ≤ 10, то за 11 – r ≤ 5 операций Петя может увеличить k на 11 – r до ближайшего числа кратного 11 (это возможно, так как наибольшее возможное значение k = 2013 кратно 11).
Ответ
5 рублей.
Замечания
Если бы у мальчиков было по n карточек с цифрами 1 и 2, ответ в аналогичной задаче зависел бы от остатка от деления n на 11 – даже при больших n. Так, если n = 2000, то Пете нужно добиться того, чтобы k имело остаток 10 при делении на 11; значит, если k = 2000 или k = 0, то Пете может понадобиться 10 ходов.
