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

Проект МЦНМО
при участии
школы 57
Задача 64517
Темы:    [ Четность и нечетность ]
[ Классическая комбинаторика (прочее) ]
[ Инварианты ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В ряд выписаны несколько нулей и единиц. Рассмотрим пары цифр в этом ряду (не только соседних), где левая цифра равна 1, а правая 0. Пусть среди этих пар ровно M таких, что между единицей и нулем этой пары стоит чётное число цифр, и ровно N таких, что между единицей и нулем этой пары стоит нечётное число цифр. Докажите, что  M ≥ N.


Решение

Если в ряду есть две единицы подряд, вычеркнем их. При этом разность  M – N  не изменится: число "чётных" пар с одной единицей равно числу "нечётных" пар с другой; а на чётности пар, куда эти единицы не входят, это не повлияет. Также можно стереть и два нуля, стоящих подряд. Продолжая эти стирания, мы придём к ряду (возможно, пустому), где нули и единицы чередуются. Но у такого ряда  N = 0.

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
задача
Номер 4

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

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