Город представляет собой бесконечную клетчатую плоскость (линии – улицы, клеточки – кварталы). На одной улице через каждые 100 кварталов на перекрестках стоит по милиционеру. Где-то в городе есть бандит (местонахождение его неизвестно, но перемещается он только по улицам). Цель милиции – увидеть бандита. Есть ли у милиции способ (алгоритм) наверняка достигнуть своей цели? (Максимальные скорости милиции и бандита какие-то конечные, но не известные нам величины, милиция видит вдоль улиц во все стороны на бесконечное расстояние.)

   Решение

Темы:    [ Турниры и турнирные таблицы ] [ Доказательство от противного ] [ Принцип Дирихле (прочее) ]

Сложность: 4 Классы: 10,11

Прислать комментарий

Условие

В футбольном турнире в один круг участвовало 28 команд. По окончании турнира оказалось, что более ¾ всех игр закончилось вничью.
Докажите, что какие-то две команды набрали поровну очков.

Решение

Менее  ¼·½·28·27 = 94,5  игр были результативными. Вычтем из всех результатов по очку, то есть будем считать, что за выигрыш дается 1 очко, а за проигрыш –  –1. Если команда набрала n очков, то она выиграла (или проиграла, если  n < 0)  не менее |n| матчей. Пусть n_k – число очков, набранных k-й командой. Предположим, что все числа n_k различны. Тогда число результативных игр не меньше чем
½ ( |n₁| + … + |n₂₈| ) ≥ ½ (0 + 1 + ... + 13 + 1 + ... + 14) = 98.  Противоречие.

Замечания

1. Баллы: 7-8 кл. – 6, 9-10 кл. – 5.

2. Ср. с задачей М1047 из Задачника "Кванта".

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