Отзывы пользователей

гдз

Олимпиадная задача по математике из коллекции задач Московской Математической Олимпиады на темы: Турниры и турнирные таблицы, Разбиения на пары и группы; биекции.

Условие

2n спортсменов дважды провели круговой турнир (в круговом турнире каждый встречается с каждым, за победу начисляется одно очко, за ничью — 1/2, за поражение — 0). Докажите, что если сумма очков каждого изменилась не менее, чем на n, то она изменилась ровно на n.

Решение

  Разделим участников турнира на две группы: тех, кто набрал во втором турнире больше очков, чем в первом, и тех, кто набрал в первом турнире больше очков, чем во втором. Хотя бы одна из этих двух групп включает не менее, чем n спортсменов. Пусть, например, такова первая группа, и в ней x спортсменов. Пусть их общая сумма очков во втором турнире на D больше, чем их сумма очков в первом турнире. Тогда из условия следует, что

Dx . n.

Это изменение произошло за счет встреч x спортсменов с остальными 2n - x спортсменами (так как встречи спортсменов друг с другом внутри группы оба раза дали в сумме одно и то же количество очков, а именно ). Каждая из встреч со спортсменами другой группы добавила не более одного очка. Поэтому

Dx . (2n - x).

Сравнивая неравенства, получаем 2n - xn. Если хотя бы одно из предыдущих неравенств было бы строгим, то мы имели бы 2n - x > n, что противоречило бы предположению xn. Значит, x = n и D = n×n, и каждый спортсмен первой группы увеличил свою сумму очков ровно на n.

Так как во второй группе тоже n спортсменов, к ней применимо аналогичное рассуждение.

Комментарии. 1o. Из решения видно, что условие задачи может выполняться лишь в следующем случае: спортсмены разбились на две группы по n человек, причем в первом турнире все игроки первой группы выиграли у всех игроков второй группы, а во втором турнире все игроки второй группы выиграли у всех игроков первой.

2o.

 
Поделиться: