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

Пусть у нас N домов.

1. На первом этапе ставим N заборов- окружаем каждый дом.

2.Второй этап. Окружим забором только два объекта- получим N-1 объект.

3. На каждом последующем этапе будем окружать одним забором только два объекта и переходить к следующему этапу.

4. После N-1 этапов останется 2 объекта, которые мы и окружаем одним забором:

таким образом всего было N этапов- на первом мы возвели N заборов и на каждом последующем по одному- итого возведен N+N-1=2N-1 забор.

5.Объекты на каждом этапе равнозначны - были ли они группой домов или отдельно стоящим ограждённым домом- количество «правильных» заборов от этого не зависит, поэтому можно считать, что на каждом этапе мы добавляем один отдельно стоящий дом к группе ранее огороженных.

6. тогда более чем 2N-1 «правильных» заборов возникнуть не может, поскольку для одного забора на каждом этапе потребовался ровно один огороженный дом. И на большее количество заборов просто не хватит домов.