Matematické Fórum

Dobrý den všem.
Mám 25 žetonů od pěti barev (čísla 12345) a pěti tvarů (písmena ABCDE). Čili ta množina žetonů je označena například A1, A2, A3, A4, A5, B1, ... E3, E4, E5.

Nyní z nich potřebuji vytvořit pětice tak, aby v každé pětici byl žeton od každé barvy a každého tvaru PRÁVĚ JEDNOU. Čili [A1, B2, C3, D4, E5] a nebo [E3, A2, C1, B5, D4] jsou validní permutace (jsou to permutace, že?), zatímco např. [A1, B2, A3, C4, E5] není validní (je tam dvakrát tvar A, i když je pokaždé jiné barvy) a nebo [B5, C3, A1, D1, E4] také není validní, protože je tam dvakrát barva číslo 1.

Celkem je to tedy 14400 permutací, ve kterých se nacházejí prvky vždy rozdílné barvy a tvaru.

Pro jednoduchost tam zatím nechávám i palindromické pětice, protože pro mě a moje účely je [A1, B2, C3, D4, E5] a [E5, D4, C3, B2, A1] identická, ty žetony totiž budou namalovány na kartách a ta karta se dá otočit o 180° a bude mít přitom pro mě shodný význam. Jinak po vykrácení palindromických pětic by se množina samozřejmě zkrátila na 7200 pětic.

No a teď ta otázka.
Poradí někdo způsob, jak vybrat podmnožinu karet, ve které budou platit následující podmínky???

1) Každý žeton, tzn. konkrétní tvar a barva, se MUSÍ na každé pozici v pěticích ve vybrané podmnožině vyskytovat PŘESNĚ STEJNĚKRÁT, jako ostatní žetony! Tzn. že pokud bych nastavil, že PŘESNĚ STEJNĚKRÁT bude 4, měla by mi vzniknout podmnožina s počtem pětic 100, protože mám 25 žetonů a chci, aby se každý objevil na dané pozici přesně 4x. Pokud se rozhodnu pro počet umístění na pozici s hodnotou 5, tak by to podle mě mělo být 125 pětic. A tak dále. Ale nevím, možná dělám chybu v uvažování. Každopádně jiná čísla než 3, 4, 5 nebo 6 mě pro ten počet opakování na dané pozici nezajímají.
2) Žádná pětice v podmnožině nesmí mít v té podmnožině k sobě pětici palindromickou, jak jsem psal výše!

Čili, když danou pětici zařazuji do podmnožiny, zaprvé kontroluji, zda je sestavena tak, aby se v ní neopakovala žádná barva i tvar vícekrát (to je zaručeno tím, že vybírám už z těch předem připravených 14400 vyhovujících pětic (tedy pokud ty pětice jsou opravdu vyhovující a nedělám někde chybu, ale konrtolní součty v Excelu na pozicích mi říkají, že mám tuhle množinu vhodných spravně)! A dále pak kontroluji danou pětici před přidáním, jestli už vznikající podmnožina neobsahuje palindromickou pětici. Pokud už palindromická pětice v podmnožině existuje, přidávanou pětici zahazuji a beru další v pořadí a snažím se jí přidat. Pokud taková pětice neexistuje, tak ji mohu přidat a zaroveň se mohu rozhodnout, jestli jí přidám tak, jak je, nebo jí transponuji (udělám z ní palindrom), abych si tím nějak aspoň trochu řídil množství jednotlivých žetonů na konkrétní pozici.

Jak se rozhoduji, jestli tam přidám původní ( [A1, B2, C3, D4, E5] ) a nebo revezní ( [E5, D4, C3, B2, A1]) ??? No, pokud by přidáním té původní se zvýšil počet výskytů A1 na PRVNÍ pozici z 1 na 2, zatímco při přidání palindromické pětice by se zvýšil počet výskytů na POSLEDNÍ PÁTÉ pozici z 0 na 1, tak samozřejmě je pro mě vhodnější vložit tu palindromickou, protože se mi tím tak nějak rovnoměrně naplňuje podmnožina, že má aspoň trochu vybalancovaný ten počet konkrétních žetonů na konkrétních pozicích.

To je víceméně jediný způsob, jak nějak balancovat ty pětice do nové podmnožiny. Druhým způsobem je to, že napřed zamíchám těch 14400 pětic, aby se mi dostávaly pod ruku už promíchané. Protože kdybych to vzal přísně popořadě po vygenerování:

[A1, B2, C3, D4, E5]
[A1, B2, C3, D5, E4]
[A1, B2, C3, E4, D5]
[A1, B2, C3, E5, D4]

tak už mám vlastně na pozici 1 vyčerpanou kapacitu výskytu pro prvek A1, na pozici 2 vyčerpanou kapacitu výskytu pro prvek B2 a na pozici 3 vyčerpanou kapacitu výskytu pro prvek C3, pokud jsem si zvolil, že na pozici MUSÍ BÝT žeton právě 4x.

Navíc mi tím vznikají vizuálně dost podobné pětice a protože to bude vyobrazeno na kartách jako ty žetony různých tvarů a barev, tak by si to bylo i vizuálně dost podobné a to já právě nepotřebuju, potřebuju i vizuální rozmanitost. Proto tu celou množinu 14400 prvků před začátkem probírání míchám a proto se rozhoduji, zda už tam náhodou nemám i palindromickou pětici...

Už jsem naprogramoval 3 skripty, které z té velké množiny vybírají tu podmnožinu a bohužel se mi nedaří se dostat do kýženého stavu! Při opakování na pozici nastaveném na 4 se dostávám na počet karet NEJVÝŠE 97, ale očekával jsem, že jich bude 100 (viz. výše). Při nastavení na počet opakování na pozici na 5 zase po kompletní iteraci se dostanu maximálně na počet 121, ale očekával bych 125...

Tenhle postup je podle mě dost náchylný na to, jak si naplním tak do půlky tu výstupní podmnožinu, protože se pak už velmi snadno může stát, že už ve zbytku NENAJDU vhodné pětice, které by mi doplnily tu podmnožinu do uspokojivého stavu. Takže pak musí přijít poměrně náročná ruční práce, kde musím i odmazávat některé pětice, abych získal prostor pro jiné, které tam chci dát.

Takže jsem tu chtěl poprosit zkušené, zda je nenapadá nějaký postup, jak to celé udělat lépe (brutální síla počítače a programování v Pythonu nebo Excelu není problém). Zdá se mi totiž neuvěřitelné, ale nejsem to schopen matematicky dokázat, že by v celkové množině 14400 pětic neexistovala podmnožina 100 pětic vyhovující podmínce přesného výskytu 4x na jedné pozici nebo 125 pětic vyhovující podmínce přesného výskytu 5x na konkrétní pozici.

Děkuji všem, kteří tohle přečetli a pokud někdo i poradí, JAKÝM ZPŮSOBEM to vybrat, budu moc rád.

Petr Vavřinec