Задача с гривни

[Гост]

Здравейте, може ли помощ за решаването на тази задача. До тук стигам, че възможностите са 96, но как да определя, колко от тях са повтарящи се, тъй като гривната е кръгла и тя няма начало и край.
3в. * 2в. * 2в. * 2в. * 2в. * 2в. * 1в. = 96 в.

[Гост]

Гривни-page-001.jpg (337.21 KiB) Прегледано 190 пъти

Гривни-page-002.jpg (273.1 KiB) Прегледано 190 пъти

[peyo]

Задача: Колко са различните гривни с 7 мъниста, всяко от които е жълто, синьо или червено, ако съседните мъниста са различни?

Идея:
Фиксираме първото мънисто да е цвят 1 (например жълто). Гледаме всяка гривна като разходка по триъгълник от цветовете 1, 2, 3, където всяка стъпка минава по ребро (новият цвят винаги е различен от предишния).

Ще броим по позиции (1 до 7) колко начина има да стигнем до всеки цвят, ако започнем от цвят 1. Обозначаваме:

- ред "цвят 1" – броят начини да сме на цвят 1 след k хода;
- ред "цвят 2" – съответно за цвят 2;
- ред "цвят 3" – за цвят 3.

Преходът е:
$$\text{брой начини за даден цвят в позиция k+1} = \text{сбор от броя начини за другите два цвята в позиция k}$$

(защото не можем да останем на същия цвят – съседни мъниста трябва да са различни).

Допълнително в позиция 7 забраняваме цвят 1, понеже последното мънисто не може да е със същия цвят като първото.

Таблица:

Код: Избери целия код

позиция →     1   2   3   4   5   6   7
             --------------------------
цвят 1     |  1   0   2   2   6  10   0
цвят 2     |  0   1   1   3   5  11  21
цвят 3     |  0   1   1   3   5  11  21


Кратко разчитане:

- Колона 1: започваме на цвят 1 → (1, 0, 0).
- Колона 2: от 1 можем към 2 или 3 → (0, 1, 1).
- Всяка следваща колона: за всеки цвят взимаме сбора от другите два в предишната колона.
- В колона 7 за цвят 1 слагаме 0 (забранен), а за 2 и 3:
- цвят 2: 10 + 11 = 21
- цвят 3: 10 + 11 = 21

В последната колона общият брой валидни оцветявания с фиксиран първи цвят 1 е:
$0 + 21 + 21 = 42$

Интересен детайл: появява се числото 42 – познато и като „отговора на въпроса за Живота, Вселената и всичко останало“.

От редици към гривни:
Дотук броихме оцветявания, при които:

- знаем кое мънисто е "първо";
- знаем в каква посока обикаляме (по или обратно на часовника).

За една и съща истинска гривна:

- можем да изберем кое мънисто да наречем "първо" по 7 начина (7 завъртания);
- можем да обикаляме по часовник или обратно – по 2 начина.

Така всяка гривна съответства на точно 14 различни „разходки“ (оцветявания с фиксирана позиция 1 и посока).

Следователно броят различни гривни, при които някакво мънисто е цвят 1, е:
$42 / 14 = 3$

Първоначално ние произволно избрахме кой цвят да наречем „1“. Реално първият цвят може да е жълт, син или червен – имаме 3 избора. Значи общият брой различни гривни е:

$3 × 3 = 9$

Краен отговор: 9 различни гривни.

[ammornil]

Още един поглед на задачата чрез графи. $$ P(C_{n},q)= (q-1)^{n} +(-1)^{n}\cdot{}(q-1) $$ $\\[12pt] P=\dfrac{P(C_{7},3)}{P(C_{4},3)}= \dfrac{2^{7} +(-1)^{7}\cdot{2}}{2^{4} +(-1)^{4}\cdot{2}}= \dfrac{126}{14}= 9\\[12pt]$ Цикъл със седем възела от три различни цвята има общо 126 пермутации. Понеже два съседни възела не могат да са от един и същи цвят, можем да разгледаме седемте възела като цикъл от три съпервъзела с по два различни цвята и един възел с един от три цвята което дава вариациите на всяка комбинация. Отношението на общия брой пермутации и вариациите (ротации и отражения) на една и съща пермутация дава уникалния брой подреждания.