Top.Mail.Ru
? ?
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка про куб и додекаэдр [июн. 30, 2020|10:26 pm]
Anatoly Vorobey
[Tags|]

«1. Выбраны 6 различных цветов; требуется раскрасить 6 граней куба, каждую в особый цвет из числа избранных. Сколькими геометрически различными способами можно это сделать? Геометрически различными называются две такие расцветки, которые нельзя совместить одну с другой при помощи вращений куба вокруг его центра.

2. Решить ту же задачу для случая раскраски граней правильного двенадцатигранника в 12 различных цветов.»




Я узнал об этой задаче из поста Григория Мерзона, который рассказал, что она предлагалась на первой московской математической олимпиаде - в 1935 году! - и самое удивительное, что из 120 участников ее никто не решил. Сейчас на математических олимпиадах таких относительно простых задач не дают, так что это что-то говорит о стандартах разных эпох, видимо.

Ну, мне она понравилась, и хотя не сразу (у меня вообще очень плохо с геометрической интуицией), я ее решил. Может, и вам понравится.

(скрывать комментарии не буду, и там скоро появятся правильные решения, думаю. Если условие или решения непонятны, можно задавать вопросы, поможем)
СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: sevabashirov
2020-06-30 07:28 pm
Полный набор 6-цветных кубиков у Гарднера в "Математических досугах" был, 30 вариантов.
(Ответить) (Thread)
[User Picture]From: avva
2020-06-30 07:29 pm
Доказать интереснее, чем полный набор построить. Уже не помню, что он об этом писал. Последний раз "М.досуги" открывал еще в школе, наверное...
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: special_linear
2020-06-30 07:47 pm
А учат ли нынче в олимпиадных кружках лемму Бернсайда?
(Ответить) (Thread)
[User Picture]From: avva
2020-06-30 08:16 pm
Думаю, в достаточно продвинутых да. Но эту задачу можно решить интуитивно, вообще ничего не зная о группах и их действиях. Я так и решил, собственно, потом уже прочитал про лемму Бернсайда и теорему Поля. Если когда-то и знал об этом в юношестве, то забыл.
(Ответить) (Parent) (Thread)
[User Picture]From: eisenberg
2020-06-30 07:53 pm
Факториал делить на порядок группы симметрии, нет?
(Ответить) (Thread)
From: (Anonymous)
2020-06-30 08:10 pm
-Уважаемый, подскажите, где мы?
-На воздушном шаре!
(Ответить) (Parent) (Thread)
From: (Anonymous)
2020-06-30 08:09 pm
Занумеруем цвета. Какая-то грань должна быть окрашена первым цветом, условимся считать эту грань "передней". Тогда для "задней" есть 5 вариантов окраски в случае куба (11 для 12-гранника).

Далее, в случае куба какая-то грань должна быть окрашена вторым цветом (либо, если второй уже использован для задней стенки - третьим), условимся считать эту грань "верхней", тем самым мы фиксируем ориентацию куба, и вариантов закрасить оставшиеся грани оставшимися цветами 3*2*1=6, т.е. всего 5*6=30 вариантов.

В случае 12-гранника вторым[третьим] цветом может оказаться окрашена либо грань в "заднем", либо в "переднем" ряду. Условимся в первом случае считать эту грань "задней верхней", во втором "передней верхней справа". В обоих случаях это фиксирует ориентацию, и остается 9! вариантов закраски. Итого 11*2*9! (гугл говорит это 7983360) вариантов.

Вроде тривиально, мне кажется даже может сгодиться и для олимпиады по физике и (студенческой) по химии, понимание симметрий.
(Ответить) (Thread)
[User Picture]From: avva
2020-06-30 08:15 pm
Все верно, да. У меня то же решение получилось, как 11*C(10,5)*4!*5!

Сначала выбираем цвет задней грани, потом выбираем, какие 5 из оставшихся 10 цветов участвуют в "переднем" ряду, потом один из цветов "переднего" ряда фиксируем в определенном месте, у остальных остается 4! варианта, а в "заднем" ряду мы уже не может ничего зафиксировать и ему доступны все 5! вариантов.
(Ответить) (Parent) (Thread)
[User Picture]From: urod
2020-06-30 08:12 pm
1. Повернём куб так, что у нижней грани цвет 1. Тогда есть 5 вариантов цветов верхней грани. Для каждого из них есть 4!=24 варианта раскраски 4 граней, но поскольку куб можно повернуть 4 способами, разных вариантов всего 6. Поэтому всего 30 вариантов.

2. Аналогично 11!/5.
(Ответить) (Thread)
[User Picture]From: utnapishti
2020-06-30 08:16 pm
Для куба:
Решение 1: Смотрим на грань, покрашенную в определённый цвет. Для противоположной грани 5 вариантов. Для оставшихся четырёх граней - циклическая перестановка оставшихся цветов, 3!. Всего 5*3! = 30.
Решение 2: В лемме Бернсайда только одно слагаемое, 6!/24 :)

Аналогично для додекаэдра 11*10!/5 или 12!/60.
(Ответить) (Thread)
[User Picture]From: avva
2020-06-30 08:29 pm
Мне кажется, есть два класса "наивных" решений (без леммы Бернсайда):

1. Фиксируем - выбираем, фиксируем - выбираем. Это как у тебя в первом решении для куба (вместо "циклическая перестановка" можно тоже: зафиксировали один из цветов в конкретном положении, для оставшихся 3! вариантов). Формула 5*3!

2. Возьмем определенную последовательность граней в пространстве и рассмотрим все способы назначить им цвета по порядку, таковых 6! Каждая "реальная" раскраска будет встречаться в этом списке много раз, сколько? Можно повернуть раскрашенный куб, так, чтобы любая его грань стала первой в последовательности, и затем еще 4 раза повернуть дает разные элементы списка. Значит, реальных раскрасок 6!/(6*4).

Для додекаэдра формулы соответственно 11*C(10,5)*4!*5! (ну так у меня вышло, см. комментарий выше), и 12!/(12*5).

Мне очень естественно думать по первому варианту (и я так решил и для куба и для додекаэдра), и почему-то совсем неестественно по второму.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ny_quant
2020-06-30 08:44 pm
Сейчас на математических олимпиадах таких относительно простых задач не дают, так что это что-то говорит о стандартах разных эпох, видимо.

С другой стороны, когда я готовился к вступительным экзаменам, мне попались в руки варианты вступительных экзаменов на мехмат МГУ конца 30-х годов. Очень непростые там были задачки.
(Ответить) (Thread)
[User Picture]From: rsokolov
2020-06-30 08:44 pm
30
7983360
(Ответить) (Thread)
From: marknn
2020-06-30 08:55 pm
Упрощенный вариант - без потери общности передняя грань будет первым цветом - одиннадцать граней могут быть раскашены 11! цветов. Каждая раскраска встречается 5 раз при поворотах, соответственно ответ 11! / 5
(Ответить) (Parent) (Thread)
From: yegork
2020-06-30 08:49 pm
Если хотите, то вот задачка, которую мне задали в 1995 году в Израиле на компьютерной олимпиаде (могу похвастаться, что я её тогда один полностью решил):

В оригинале звучало так: "Ввести строку ноликов и единичек неизвестной длинны, ответить делится ли данное двоичное число на 3".

Сразу скажу: имплементировать BigNumber конечно можно, но не спортивно. Скажем так: размер числа такой, что ни памяти, ни диска не хватит.
(Ответить) (Thread)
[User Picture]From: livelight
2020-06-30 09:10 pm
Дык, 4 (=основание системы записи в квадрате) делится на 3 с остатком 1. Точно так же, как 10 (=основание системы записи в степени 1) делится на 3 и на 9 с остатком 1. А потому признак делимости точно такой же по сути: берём двоичные циферки по 2 штуки и складываем по модулю 3 эти числа от 0 до 3, пока не закончатся. Если в конце осталась одна цифрв - можно считать, что после неё есть ещё нолик (что меняет остаток, но не влияет на делимость).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sergey_cheban
2020-06-30 09:49 pm
1. Берём куб, красим нижнюю грань первым цветом. Потому что куб всегда можно положить на грань, закрашенную первым цветом.
2. Красим переднюю грань - 5 вариантов. Заднюю - 4 варианта. Левую - три варианта. Правую - 2 варианта. Верхнюю - 1 вариант. Итого - 5*4*3*2*1=120 вариантов.
3. Куб можно вращать вокруг вертикальной оси. 4 варианта.
5. 120/4=30.

С додекаэдром, полагаю, аналогично: 11!/5=7983360.
(Ответить) (Thread)
[User Picture]From: deep_econom
2020-06-30 10:32 pm
про куб
5*3!
(Ответить) (Thread)
[User Picture]From: Илья Цыгвинцев
2020-06-30 11:12 pm
С кубиком:

Фиксируем цвет произвольной грани. Фиксируем цвет противоположной — 5 вариантов. На круге 4 оставшихся цвета, сколько способов их расставить? Фиксируем цвет одной грани, убирая степень свободы, связанную с вращением. Оставшиеся 3 цвета дают 3! варианта. Итого 5*3! = 30 вариантов раскраски.

С додекаэдром:

Фиксируем цвет произвольной грани. 11 вариантов противоположной, 2 круга по 5. Фиксируем цвет одной из соседних к первой граней (держим в уме множитель 2 — данный цвет может быть на другом круге). Оставшиеся 9 цветов дают 9! вариантов. Итого 9!*2*11 = 7983360 вариантов раскраски.
(Ответить) (Thread)
From: (Anonymous)
2020-07-01 04:16 am
Для куба есть 6! раскрасок и 6*4 способов совместить его с собой вращениями (любую из 6 граней можно вращением сделать верхней, затем вращение вокруг вертикальной оси дает 4 варианта) ответ 6!/(6*4)=30. Для додекаэдра аналогично 12!/(12*5).
(Ответить) (Thread)
[User Picture]From: melkiythegreat
2020-07-01 07:09 am
Фиксируем одну грань одним цветом. Прилегающие вращать можно - противоположную нет. Это дает нам перебор 5 вариантов. Далее в каждом из вариантов фиксируем одну грань одним цветом и получаем перестановкой трех оставшихся получаем еще 6 вариантов итого 30.
(Ответить) (Thread)
From: karpion
2020-07-01 01:00 pm
Это про куб?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2020-07-01 07:09 am
A к прошлой задаче, про рыцарей, решениe будете постить как обещали ?

(Ответить) (Thread)
[User Picture]From: avva
2020-07-01 12:32 pm
В принципе там есть в комментариях, но да, напишу сегодня-завтра, спасибо что напомнили.
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>