Ваня складывает из 2013 карточек, на которых написана цифра 1, и 2013 карточек, на которых написана цифра 2, 4026-значное число. За один ход Федя может поменять местами некоторые две карточки и заплатить Ване 1 рубль. Процесс заканчивается, когда у Феди получается число, кратное 11. Найдите наибольшее число рублей, которые может получить Ваня, если Федя стремится заплатить как можно меньше?
Answers & Comments
Оценка:
Докажем, что пяти рублей Феде всегда хватит. Пусть число Вани даёт остаток k от деления на 11. Если k чётный, поменяем местами "1" на чётной позиции с "2" на нечётной позиции. Остаток после этого уменьшится на 2. Если k нечётный, поменяем местами "1" на нечётной позиции с "2" на чётной позиции. Остаток после этого увеличится на 2 (когда он станет равен 11, число будет делиться на 11). При этом такую операцию всегда можно будет сделать, так как если одну из данных операций больше провести невозможно, то получилось либо число "2121...21", либо число "1212...12", оба из которых делятся на 11 по признаку делимости.
Пример:
Число "1212121212,2121...21" ("," показывает момент изменения порядка следования "1" и "2") имеет остаток 1 от деления на 11, следовательно, с ним нужно провести не менее 5 действий.
Ответ: 5 рублей.