ФЕНИКС   На связи с единомышленниками           

 Поддержка проекта 

Авторизуйтесь с помощью соцсетей и служб

Заборы.

Автор
Опубликовано: 15 дней назад ( 5 октября 2019)
+6
: 6
Заборы.


В городе N домов. Какое наибольшее число заборов можно построить в этом городе, если:
1) заборы не пересекаются;
2) каждый забор огораживает хотя бы один дом;
3) никакие два забора не огораживают одну и ту же совокупность домов?
Спойлер
196 просмотров
Комментарии (38)
Ellinka # 5 октября 2019 в 07:40 +6
Думаю, решение задачи во многом зависит от расположения домов scratch
По-моему, их будет очень много!
Александр Борисенко # 6 октября 2019 в 01:27 +6
Если число заборов излишне увеличивать, то начнётся повторение числа огораживаемых домов, что противоречит п.3! Значит число заборов не так уж намного превышает N! laugh
Ellinka # 6 октября 2019 в 08:09 +6
"Число домов" и "совокупность домов" это разные понятия на мой взгляд.
Я согласна с Nif'ом по поводу общей формулы.
Рисовала разные комбинации и приходила всегда к тому же результату.
Пока не могу выложить рисунки (с мобильника).
Как доберусь до компа, выложу парочку вариантов!
Александр Борисенко # 7 октября 2019 в 01:06 +6
Да, пожалуй, Вы правы, Ellinka! smile_20
В авторском условии вопиющая неопределённость, которую я упустил! getImage 3
"Число домов" не зависит от места, на котором они находятся, а что касается "совокупности домов", то стоит изменить место - и "совокупность" уже другая! smile_11
Ellinka # 7 октября 2019 в 08:20 +5
Почему "неопределённость"?..
По-моему, хорошее условие. Получилась интересная задача! v
Александр Борисенко # 8 октября 2019 в 00:20 +5
Вы правы, Ellinka! Неопределённости скорее и не было, но такой и была задумка автора. Иначе решение было бы слишком просто: число заборов равно числу домов! smile
Ellinka # 5 октября 2019 в 07:46 +6
Пока для 4-х домов у меня получается 7 заборов.
К сожалению, сейчас нет времени на решение sad
Александр Борисенко # 7 октября 2019 в 01:17 +5
Принимается, Ellinka, для "совокупности"! smile_16 smile
Nif # 5 октября 2019 в 09:41 +6
В общем случае количество заборов = 2N-1, где N - количество домов в городе. v
Александр Борисенко # 7 октября 2019 в 01:18 +5
Вы правы, Nif! Для "совокупности" формула правильная! smile_16 smile smile_20
Александр Борисенко # 6 октября 2019 в 01:32 +6
Во избежание голословности утверждения,
Не мешало бы изобразить своё решение! joke
Ну, хотя бы на небольшом числе домов! А там - посмотрим... smile
Nif # 6 октября 2019 в 18:19 +6
Пример для 24 домов, вокруг которых 47 заборов. laugh
Александр Борисенко # 7 октября 2019 в 00:52 +6
Не годится, Nif! Начнём сверху: на второй линии у Вас два дома огорожены общим забором, но это же было на первой линии. Противоречие п.3! laugh
Александр Борисенко # 7 октября 2019 в 01:19 +6
Принимается решение, Nif! smile_16 smile
ШИКО # 6 октября 2019 в 19:24 +6
Так а что здесь, Александр, непонятно? Методом математической индукции при N = K домов число заборов 2K- 1.
Добавляем 1 дом: N = K + 1. Число заборов увеличивается на 2: 1 - вокруг этого дома и 1 - вокруг новой совокупности домов.
При N = K + 1 число заборов 2K + 1.
Другими словами, было N = K домов, 2K - 1, или 2N - 1 забор.
Стало N = K + 1 дом, 2(K + 1) - 1 = 2K + 1, или 2N - 1 забор. joke
Маргаритка # 7 октября 2019 в 00:51 +6
Можно проще сказать. С каждым новым домом добавляется два новых забора. А самому первому дому соответствовал только один забор. Значит, если всего домов N, то заборов всего 2N - 1. Минус один означает, что у первого дома был только один забор. hoho smile
Александр Борисенко # 7 октября 2019 в 00:57 +6
То же самое, Маргаритка, не выполняется п.3! laugh
ШИКО # 7 октября 2019 в 01:00 +6
Сказать, Маргаритка, что угодно можно. На сколько я понял, требуются доказательства. smile_13
Маргаритка # 7 октября 2019 в 01:10 +6
Я просто считала, что формула верная. Если бы формула была верная, то у меня ее объяснение. Но что-то в условии не так.
ШИКО # 7 октября 2019 в 01:15 +6
Я вообще тогда не понял, что такое "совокупность домов"
Александр Борисенко # 7 октября 2019 в 00:56 +6
Никак нет, ШИКО! Добавляя новый дом, можем увеличить число заборов только на 1! laugh
Александр Борисенко # 7 октября 2019 в 01:19 +6
Согласен, ШИКО! smile_16 smile smile_19
Александр Борисенко # 7 октября 2019 в 01:36 +6
Некоторые сомнения в формуле, впрочем, ещё имеются: слишком уж неопределённа конфигурация совокупности! scratch
Ellinka # 6 октября 2019 в 21:15 +6
У меня картинка попроще. Для 10 домов zst



Красные - это домики с забором вокруг каждого.
Ну а остальное, думаю, понятно! laugh
Александр Борисенко # 7 октября 2019 в 01:01 +6
Цитирую п.3: "3) никакие два забора не огораживают одну и ту же совокупность домов?".
А у Вас, Ellinka, (считая слева) первый забор и второй забор огораживают по два дома! laugh
Маргаритка # 7 октября 2019 в 01:13 +6
Совокупность домов- это что, количество домов имеется в виду?
Александр Борисенко # 7 октября 2019 в 01:25 +6
Насчитал 9 или 10 заборов, Ellinka, а по формуле может быть максимально 2*10-1=19! Видимо, следует изменить расположение! laugh
Ellinka # 7 октября 2019 в 08:16 +6
Надо было не только считать, но и читать! laugh
Я же написала, что красные квадраты - это домики вместе с заборами, т.е.уже изначально 10 шт. ну и плюс те, что вам удалось насчитать. zst
Александр Борисенко # 8 октября 2019 в 00:21 +5
Да, Ellinka, не дочитал! zst Тогда принимается! smile_16 smile
Александр Борисенко # 7 октября 2019 в 01:12 +6
Как правильно отметила Ellinka, другая "совокупность домов" не означает, что у этой другой совокупности другое "число домов"! Значит приведённые решения, исходящие из "совокупности" - правильны! getImage 5
Александр Борисенко # 7 октября 2019 в 01:14 +6
Новая редакция п.3: "3) никакие два забора не огораживают одно и то же число домов" smile
Nif # 7 октября 2019 в 07:55 +6
Может так?

Тогда сколько домов - столько и заборов. laugh
Ellinka # 7 октября 2019 в 08:24 +6

Тогда сколько домов - столько и заборов.

Как в обычном коттеджном посёлке! laugh
Александр Борисенко # 8 октября 2019 в 00:24 +5
Конечно так, Ellinka! smile_16 smile
Маргаритка # 7 октября 2019 в 23:41 +5
В новой редакции получается так. scratch laugh
Все-таки, считаю, что условие было верное, понято участниками правильно, и решено правильно. Заборов будет 2N-1.
"Совокупность домов" это какая-то конкретная группа домов. И пункт третий означает просто, что заборы не дублируются. То есть вокруг каждой конкретной группы домов нельзя провести больше одного забора. Иначе число заборов может быть бесконечным... getImage 1
Александр Борисенко # 8 октября 2019 в 00:26 +5
Согласен, Маргаритка! smile_16 smile
В авторском варианте задача интереснее! smile
Ellinka # 8 октября 2019 в 14:17 +5
Полностью согласна! v
Александр Борисенко # 8 октября 2019 в 00:23 +5
Именно так, Nif! smile_16 smile

Новости клубов

28 минут назад
2 часа назад
2 часа назад
4 часа назад
Демид добавляет запись на стене клуба Христианское искусство:
СВЯТЫЕ МУЧЕНИКИ СЕРГИЙ И ВАКХ.
4 часа назад
9 часов назад
9 часов назад