Отправлено: 04.10.04 17:31. Заголовок: Число способов раскраски граненого стакана.
Есть граненый стакан с количеством граней N. Сколькими способами можно раскрасить его боковую поверхность, имея 2 краски и крася каждую грань только в один цвет. Примечание: грани стакана незанумерованы, иначе говоря, принципиально неразличимы. Неокрашеных граней оставаться не должно
Помещаю эту задачку в серьёзный раздел, поскольку её видимая простота обманчива. К тому же у меня нет полного решения этой задачи для произвольного числа граней. Ну и то, что сам раздел до сих пор был девственный - не есть хорошо.
Отправлено: 04.10.04 20:35. Заголовок: Re: Число способов раскраски граненого стакана.
Kostya пишет:
цитата2^N ?
Этот ответ справедлив для стакана, у которого все грани различимы, т.е. занумерованы. Интересно как раз решить задачу для стакана с неразличимыми гранями. В этом случае, например, следующие раскраски 4-хгранного стакана считаются одинаковыми: (1,0,0,0) ; (0,1,0,0) ; (0,0,1,0) , (0,0,0,1)
Или такие: (1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1) - тоже одинаковые
Отправлено: 05.10.04 11:22. Заголовок: Re: Число способов раскраски граненого стакана.
Может Костя и прав. (2^N)/2. Можно сделать развертку стакана, но так как все грани не различимы, то резать можно начиная с одной из красок, то есть все варианты, можно не нарушая общности, начинать с одной из красок.
Отправлено: 05.10.04 15:52. Заголовок: Re: Число способов раскраски граненого стакана.
Витек пишет:
цитатаМожет Костя и прав. (2^N)/2. Можно сделать развертку стакана, но так как все грани не различимы, то резать можно начиная с одной из красок, то есть все варианты, можно не нарушая общности, начинать с одной из красок.
Не получается. Лучше всего - на примерах. Наглядней будет, если мы выделим однотонную раскраску (когда все грани стакана покрашены в один цвет) в отдельные 2 способа (второе слагаемое в формулах, написанных ниже).
Для 2-гранного стакана 1 + 2 способа - (1,0) + (1,1), (0,0) Для 3-гранного стакана: 2 + 2 способа - (1,0,0) и (1,1,0) + (0,0,0) и (1,1,1) Для 4-х гранного: 4 + 2 способа - (1,0,0,0), (1,0,1,0), (1,1,0,0), (1,1,1,0) + (0,0,0,0) и (1,1,1,1) Для 5-ти гранного: 6 + 2 способа - (1,0,0,0,0), (1,0,1,0,0), (1,1,0,0,0), (1,1,1,0,0) , (1,1,1,1,0), (1,0,1,1,0)+ (0,0,0,0,0) и (1,1,1,1,1) ...
Все остальные раскраски при повороте стакана вокруг оси симметрии переходят в уже перечисленные (т.е. не считаются новыми раскрасками)
Требуется уточнение условия. Считаются ли различными раскраски, переходящие друг в друга при движениях торцов карандаша друг в друга, зеркальные в плоской развертке, другими словами. (101100) и (001101), к примеру?
Не совсем понял эту формулировку. Но приведенный пример (101100) и (001101) - зеркальные в плоской развертке - это две разные раскраски. Одинаковыми считаются лишь раскраски, которые совмещаются при повороте. Или иными словами, если смотреть в плоской развертке, то циклические перестановки какой-либо раскраски считаются одной раскраской.
ЗЫ. Речь, кстати, в задаче не про карандаш, а про священный гранёный стакан.
Когда у человека слово "грани" вызывает ассоциации со словом "карандаш", а не "стакан", это наводит на тягостные подозрения... Отдыхать мне нужно, пожалуй
там в теремке www.deniq.net/teremok висит обещанное решение. сорри что так долго - со свободным временем совсем беда. __________ а пузырь - хорош, спасибо. ето ж надо такое удивительное терпение иметь, чтоб так упорно объяснять Неверующему очевидные весчи. я б так не смог ;)))
Все даты в формате GMT
3 час. Хитов сегодня: 1
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет
- участник сейчас на форуме
- участник вне форума
