|
|
 |
Условие
25 дачников получили садовые участки. Каждый участок представляет собой квадрат 1×1, и все участки вместе составляют квадрат 5×5. Каждый дачник враждует не более, чем с тремя другими дачниками. Докажите, что можно распределить участки таким образом, чтобы участки враждующих дачников не были бы соседними (по стороне).
Подсказка
Распределите участки вначале произвольным образом, а затем пусть дачники меняются участками так, чтобы число пар враждующих соседей уменьшилось.
Решение
Число способов распределить участки между дачниками конечно, поэтому можно рассмотреть способ, при котором число пар враждующих соседей минимально.
Предположим, что пары враждующих соседей имеются; пусть A и B – два враждующих соседа. Рассмотрим 23 дачников, отличных от A и B. Покажем, что среди них найдётся такой дачник C, что а) C не враждует с соседями B; б) C не является соседом враждующих с B дачников. Действительно, условие а) исключает не более 4·3 − 1 = 11 дачников (один из соседей B – дачник A, одним из врагов которого является B). Условие б) исключает еще 3·4 − 1 = 11 дачников. Итак, оба условия исключают не более 22 дачников. Значит, хотя бы один дачник удовлетворяет этим условиям.
Если дачники B и C поменяются участками, то пара враждующих соседей (A, B) исчезнет, а новых пар не возникнет. Это противоречит выбору исходного распределения.
Источники и прецеденты использования
| web-сайт | |
| задача |
