ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64623
Темы:    [ Теория игр (прочее) ]
[ Признаки делимости на 11 ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Имеются 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 рублей.

Замечания

Если бы у мальчиков было по n карточек с цифрами 1 и 2, ответ в аналогичной задаче зависел бы от остатка от деления n на 11 – даже при больших n. Так, если  n = 2000,  то Пете нужно добиться того, чтобы k имело остаток 10 при делении на 11; значит, если  k = 2000  или  k = 0,  то Пете может понадобиться 10 ходов.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
1
Вариант 4
класс
Класс 9
задача
Номер 9.6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .