Назад
Задача

Имеются 2013 карточек, на которых написана цифра 1, и 2013 карточек, на которых написана цифра 2. Вася складывает из этих карточек 4026-значное число. За один ход Петя может поменять местами некоторые две карточки и заплатить Васе 1 рубль. Процесс заканчивается, когда у Пети получается число, кратное 11. Какую наибольшую сумму может заработать Вася, если Петя стремится заплатить как можно меньше?

Решение

  Рассмотрим 4026-значное число A, состоящее из 2013 единиц и 2013 двоек. Пусть в этом числе в нечётных разрядах стоит k единиц и  l = 2013 – k  двоек, тогда в чётных разрядах будет k двоек и l единиц (здесь k может принимать любое целое значение от 0 до 2013). Разность сумм цифр в нечётных разрядах и чётных разрядах равна  (k + 2l) – (2k + l) = lk = 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 рублей.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет