|
|
 |
Условие
В поселке 100 домов. Какое наибольшее число замкнутых не пересекающихся заборов можно построить, чтобы каждый забор огораживал хотя бы один дом и никакие два забора не огораживали бы одну и ту же совокупность домов?
Решение 1
В максимальном наборе заборов есть забор, ограничивающий ровно два дома. Объединив эти два дома в один, мы уменьшим количество домов на 1, а количество заборов на 2. При этом оба условия задачи сохраняются. Продолжим этот процесс. После 99 шагов останется один дом и один забор. А убрали мы 198 заборов. Значит, всего их было 199.
Решение 2
Если один забор находится внутри другого, то первый назовём потомком второго. Если они не отделены третьим забором, то первый – сын второго. Можно считать, что есть патриарх – забор, окружающий весь поселок (иначе, построив его, мы увеличим число заборов). По той же причине можно считать, что для каждого дома есть забор, окружающий только этот дом – это бездетные потомки (их ровно 100). Условия задачи на этом языке означают, что нет однодетных потомков. Если число заборов, имеющих сыновей, обозначить через x, то всего заборов не меньше чем 1 + 2x (патриарх + чьи-то дети). Отсюда 100 + x ≥ 1 + 2x, x ≤ 99, 100 + x ≤ 199.
Ответ
199 заборов.
Источники и прецеденты использования
| книга | |
| Автор | Иванов С.В. |
| Название | Математический кружок |
| глава | |
| Номер | 14 |
| Название | Разные задачи |
| Тема | Неопределено |
| задача | |
| Номер | 30 |
