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

Классная задача. Мне понравилось её решать.

Я решил начать с маленьких чисел. Для N=1 дома, очевидно, ответ равен 1, ведь можно построить единственный забор, окружающий сам этот дом, и больше никакие.

Договоримся, что далее я буду всё время окружать дома заборами вот как. Во-первых, каждый дом отдельным забором. Во-вторых, все дома единым забором. Эти N+1 заборов никак не мешают друг другу и возможным другим заборам, поэтому их не буду проговаривать каждый раз. Ну а если можно построить ещё что-то кроме них, то буду это обсуждать.

Для N=2 домов ответом является 3, так как можно построить забор вокруг первого дом, забор вокруг второго дома и забор вокруг обоих домов (это именно те заборы, о которых сказано в договорённости).
Для N=3, кроме N+1=4 договорных заборов, можно построить ещё один: вокруг каких-нибудь двух домов.
А вот для N=4 уже начинаются варианты. Можно обнести забором три дома и внутри них ещё одним забором два дома, а можно два одним забором и два другим. Видно, что в обоих случаях заборов получилось 7.
Далее будет ещё больше вариативности, поэтому тут остановлю "маленькие числа".

Обозначим ответ к задаче за f(N). Выше мы установили, что f(1)=1, f(2)=3, f(3)=5, f(4)=7.

Сейчас я постараюсь объяснить ключевую вещь в решении:

f(N) = max [f(X) + f(N - X)] + 1,
где перебор проводится по всем X = 1, 2, ..., N - 1.

Пусть есть какое-то построение заборов для N домов, в котором Z заборов. Назовём величиной забора количество домов, которые он охватывает.
Если в указанном построении есть забор величины N, то мысленно выкинем его. Посмотрим на следующий по величине забор после него; пусть его величина равна X. Он отделяет одну группу домов (внутри себя) от другой (вне себя). Тогда в группе из X домов всего построено уж точно не более f(X) заборов (ведь в случайном построении заборов никак не может быть больше, чем в самом лучшем), а в оставшихся домах — уж никак не более f(N - X) (по аналогичным причинам). Следовательно,

Z ≤ f(X) + f(N - X) + 1

(плюс единичка взялась из-за того, что мы должны посчитать самый большой забор, который величины N в том случае, если он есть). Ну а поскольку

f(N) = max [Z],

где перебор проводится по всем построениям заборов

то получаем формулу выше.

Наконец, последняя часть доказательства. Уже на маленьких числах было заметно, что f(N)=2*N-1. А теперь докажем это методом математической индукции.

База есть, проверена выше.

Шаг. Пусть тот факт, что f(N)=2*N-1, верен для всех N = 1, 2, ..., K. Докажем это для N=K+1. Заметим, что

f(1) + f(K) = f(2) + f(K - 1) = f(3) + f(K - 2) = ... = 2 * (K + 1) - 2 = 2K,

то есть как ни разбивай дома, сумма максимумов получается одна и та же. Ну а

f(K + 1) = max [f(X) + f(N - X)] + 1 = 2K + 1 = 2 * (K + 1) - 1.

Вывод. Шаг индукции верен, значит поставленное утверждение справедливо.

Ответ: 2N - 1 забор.