7
|
Задача 950. Новый Годпостоянный адрес задачи: http://www.diofant.ru/problem/2644/автор задачи: E.Schroder показать все задачи автора >> показать код для вставки на свой сайт >> |
Задачу решили:
22
всего попыток:
155
поделиться задачей:
|
|
|
Задача опубликована:
25.09.13 08:00
Прислал:
nauru
(Сергей Меньшов)
Источник:
Санкт-Петербургская олимпиада
Вес:
1
сложность:
2
класс:
8-10
баллы: 100
Темы:
комбинаторика
|
|
Лучшее решение:
TALMON
(Тальмон Сильвер)
|
У Санта-Клауса, как и обычно это бывает перед Новым Годом есть 8 различных подарков и несколько одинаковых мешков красного цвета (сам он синий). В каждом мешке лежит ровно два предмета(два мешка, два подарка или мешок и подарок). В частности, тот единственный мешок, который Санта-Клаус держит на плече, тоже содержит два предмета. Сколько существует способов разложить подарки по мешкам?
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Попробую сформулировать вопрос. Он в том, какие разложения считать разными.
Вижу, по меньшей мере, 3 варианта счета. Пока только первый вопрос.
Пусть 8 подарков А1,…,А8 разделены на 4 пары П1=А1+А2, П2=А3+А4, П3=А5+А6, П4=А7+А8.
Берем вариант, когда на плече у Санта-Клауса мешок М0, в котором 2 мешка (М1,М2), в каждом из которых по 2 мешка (в М1 - М3 и М4, в М2 - М5 и М6), в каждом из которых – одна пара. Надеюсь, что все варианты, в которых пары П1 и П2 оказались в одном и том же мешке М1 или М2, это одно и то же разложение, но считаются ли оно совпадающим с разложением, в котором в одном и том же мешке M1 или М2 оказались П1 и П3?
Нет.
Варианты
М0 \ М1 \ ... \ П1 + М0 \ М1 \ ... \ П2
и
М0 \ М1 \ ... \ П1 + М0 \ М1 \ ... \ П3
считаются различными.
В условии написано: Различные подарки, одинаковые мешки. Это означает, что важно и какие получаются различные двоичные деревья, и как расположены в них различные подарки.
Естественно, если в каком-то дереве "поменять местами (целиком!)" две ветки, исходящие из одного и того же узла, то это считается одним и тем же способом разложения.
Любые другие перестановки подарков в каком-то дереве приводят к другим способам разложения.
Спасибо Вам, первопроходец Sam777e, спасибо Вам, Talmon - ответ исчерпывающий!
Сколько существует различных способов разложить 3 подарки по мешкам указанном способом задачи?
3.
Единственное возможное разложение: Отдельный подарок + мешок с двумя подарками.
Получаются 3 варианта: который из трёх подарков взять отдельно!
Т.е.:
1) A + мешок(B + C)
2) B + мешок(A + C)
3) C + мешок(A + B)
Нет, в условии не написано, что в каждом разложении обязаны присутствовать все 3 вида мешка. Поэтому варианты, о которых Вы спросили, тоже допустимы.
НЕ Е НАПИСАНО,НО 3 ПОДАРЪКА МОЖЕ ДА БЪДАТ И 1+1+1 И
КАТО СА РАЗЛИЧНИ 3! ВАРИАНТА.
МОЖЕ БИ НЕ СЪМ РАЗБРАЛ УСЛОВИЕТО?
Что такое "1+1+1"?
В мешке должно быть ровно 2 предмета.
Так ведь тогда в последнем мешке ничего не будет, а должно быть 2 предмета в КАЖДОМ
Ну, извините, Ваша "бескрайность" - это из другого анекдота, а здесь все конечно.
КОНЕЧНО,РАЗЛОЖЕНИЕ ПОДАРКОВ КРАЙНО,НО НЕСКОЛЬКО МЕШО-
КОВ МОЖЕТ БЬIТЬ БЕЗКРАЙНО.НАПРИМЕР,ДЛЯ 3 ПОДАРКА:
М0(М1,П1)-М1(М2,П2)-М2(М3,П3)-М3(М4,М5)......