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

Проект МЦНМО
при участии
школы 57
Задача 98288
Темы:    [ Подсчет двумя способами ]
[ Процессы и операции ]
Сложность: 4-
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Автор: Шень А.Х.

Кресла для зрителей вдоль лыжной трассы занумерованы по порядку: 1, 2, 3, ..., 1000. Кассирша продала n билетов на все первые 100 мест, но n больше 100, так как на некоторые места она продала больше одного билета (при этом  n < 1000).  Зрители входят на трассу по одному.Каждый, подойдя к своему месту, занимает его, если оно свободно, если же занято, говорит "Ох!", идёт в сторону роста номеров до первого свободного места и занимает его. Каждый раз, обнаружив очередное место занятым, он говорит "Ох!". Докажите, что число "охов" не зависит от того, в каком порядке зрители выходят на трассу.


Решение

  Для каждого i от 1 до n обозначим через ki количество билетов, проданных на места от 1-го до i-го. Ясно, что, после того как все рассядутся, первые n мест будут заняты. При этом для каждого i от 1 до n при переходе от i-го места к (i+1)-му раздастся ровно  ki – i  охов: ведь именно такого количества мест не хватит обладателям билетов с номерами от 1-го до i-го.
  Таким образом, от порядка, в котором зрители выходят на трассу, не зависит не только общее число произнесённых охов, но даже их количество, произнесённое при переходе от i-го места к (i+1)-му для каждого i.

Замечания

6 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 1995/1996
Номер 17
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 4

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

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