|
|
 |
Условие
В парламенте 200 депутатов. В процессе заседания произошло 200 потасовок, в каждой из которой участвовали некоторые два депутата.
Докажите, что можно объединить в комиссию 67 депутатов, из которых никакие два не выясняли между собой отношения в потасовке.
Подсказка
Вначале включим в комиссию всех депутатов, а затем исключаем из комиссии тех депутатов, которые участвовали по крайней мере в двух потасовках с членами комиссии.
Решение
Сначала включим в комиссию всех депутатов. Назовём депутата вредным для комиссии, если он участвовал по крайней мере в двух потасовках с членами этой комиссии. Если в комиссии нашелся вредный депутат, удалим его из комиссии (при этом некоторые депутаты могут перестать быть вредными). Будем удалять из комиссии вредных депутатов, пока это возможно. Пусть после завершения этого процесса депутатов в комиссии осталось k депутатов, между которыми произошли m потасовок. С одной стороны, k ≥ 2m (иначе есть вредный депутат); с другой стороны 200 – m ≥ 2(200 – k) (так как каждый раз при удалении из комиссии вредного депутата количество потасовок между членами комиссии уменьшалось по крайней мере на 2). Отсюда
k + (200 – m) ≥ 2m + 2(200 – k), следовательно, k – m ≥ 67. Наконец, удалим из комиссии по одному участнику каждой из m потасовок, после чего получим комиссию, между членами которой уже не было потасовок, состоящую из k – m членов.
Источники и прецеденты использования
| web-сайт | |
| задача |
