Теперь Кью работает в режиме чтения

Мы сохранили весь контент, но добавить что-то новое уже нельзя

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

(заборы нужно строить замкнутые и непересекающиеся)

Задача из С.В. Иванов. Математический кружок

МатематикаДомашние задания+4
Давид Кац
  ·   · 890
Люблю математику, люблю решать задачи и учиться.  · 1 апр 2021

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

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

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

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

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

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

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

  1. тогда более чем 2N-1 «правильных» заборов возникнуть не может, поскольку для одного забора на каждом этапе потребовался ровно один огороженный дом. И на большее количество заборов просто не хватит домов.
Студент ВМК Московского Государственного Университ...  · 30 мар 2021
Классная задача. Мне понравилось её решать. Я решил начать с маленьких чисел. Для N=1 дома, очевидно, ответ равен 1, ведь можно построить единственный забор, окружающий сам этот дом, и больше никакие. > Договоримся, что далее я... Читать далее
кандидат физико-математических наук, математик, ис...  · 16 февр 2021  · novikovlabs.ru

Очень российская задача.

Россия - страна заборов и заборчиков.

Забор здесь - это замкнутая кривая или, например, отрезок? Можно окружить один дом одним забором? Или для для этого нужно минимум три забора?