ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 31374
Темы:    [ Индукция (прочее) ]
[ Комбинаторная геометрия (прочее) ]
Сложность: 4
Классы: 6,7,8,9
В корзину
Прислать комментарий

Условие

В поселке 100 домов. Какое наибольшее число замкнутых не пересекающихся заборов можно построить, чтобы каждый забор огораживал хотя бы один дом и никакие два забора не огораживали бы одну и ту же совокупность домов?


Решение 1

В максимальном наборе заборов есть забор, ограничивающий ровно два дома. Объединив эти два дома в один, мы уменьшим количество домов на 1, а количество заборов на 2. При этом оба условия задачи сохраняются. Продолжим этот процесс. После 99 шагов останется один дом и один забор. А убрали мы 198 заборов. Значит, всего их было 199.


Решение 2

Если один забор находится внутри другого, то первый назовём потомком второго. Если они не отделены третьим забором, то первый – сын второго. Можно считать, что есть патриарх – забор, окружающий весь поселок (иначе, построив его, мы увеличим число заборов). По той же причине можно считать, что для каждого дома есть забор, окружающий только этот дом – это бездетные потомки (их ровно 100). Условия задачи на этом языке означают, что нет однодетных потомков. Если число заборов, имеющих сыновей, обозначить через x, то всего заборов не меньше чем  1 + 2x  (патриарх + чьи-то дети). Отсюда  100 + x ≥ 1 + 2xx ≤ 99,  100 + x ≤ 199.


Ответ

199 заборов.

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

книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 14
Название Разные задачи
Тема Неопределено
задача
Номер 30

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .