Cтраница 2
Ответ для п домов: можно построить In - 1 заборов. Ik - 1 уже проверена, то рассмотрим п домов, вокруг которых построено максимально возможное количество заборов. Какой-то один забор огораживает все дома. Если этот внешний забор снести, то самыми внешними станут некоторые два забора. Пусть внутри одного из них будет k домов, а внутри другого - остальные п - - k домов. В силу предположения индукции вокруг k домов может быть построено не больше 2k - 1 заборов, а вокруг остальных п - k домов - не больше, 2 ( п - k) - 1 заборов. Значит, всего заборов не более ( 2k - 1) ( 2 ( п - k) - 1) 1 2п - 1, что и требовалось доказать. [16]