Avatar uživatele
Alesh

Mám správně tuto kombinatorickou úlohu?

Řeším rozlosování turnaje v mariáši. Konkrétně mě zajímá varianta, kdy se turnaje zúčastní 14 hráčů a hraje se na 5 kol. 14 hráčů posadím ke 4 stolům po 4, 4, 3 a 3 hráčích. A samozřejmě smyslem rozlosovaní je, aby se stejní hráči v dalších kolech spolu nepotkávali a zároveň, aby maximálně rovnoměrně hrál každý na trojkovém a čtyřkovém stole. Počet kombinací, jak vylosovat jedno kolo je podle mě tento:
c(4, 14) * c(4, 10) * c(3, 6) * c(3, 3) = 4204200
A teď, pokud bych chtěl prověřit všechny kombinace možných rozlosování všech 5 kol, tak by to bylo takto?

  1. kolo – nemusím losovat posadím je třeba 1,2,3,4 + 5,6,7,8 + 9,10,11 + 12,13,14
  2. kolo – 4204200 kombinací
  3. kole – 42042002 kombinací
  4. kole – 42042003 kombinací
  5. kole – 42042004 kombinací = 312. 416. 146. 662. 589. 000. 000. 000. 000 kombinací. Čili bez šance tyto všechny kombinace prověřit? Uvažuji správně?

No, to je moc zajímavá myšlenka s těmi virtuálními hráči, budu nad ní hloubat. Zatím jsem to moc nepromyslel, ale jak by to podle této metody bylo, pokud by se hráčů sešlo 15? Tam už to řešení možné je, virtuální hráč je jen jeden, stačí ho odebrat z těch 16 a hotovo, ne? Tím je i zaručeno, že každý hráč půjde přesně jednou na trojkový stůl. Čili pro 15 a výš hráčů na 5 kol lze vždy najít řešení, spravedlivého obsazení trojkových a čtyřkových stolů a zároveň eliminovat potkání dvou hráčů opakovaně. Abych se pochlubil, tak se mi podařilo vygenerovat skript ve VBA, který toto potvrzuje, ale právě při těch 14 hráčích se už nedokážu dostat na lepší variantu než, že 2 hráči, co jdou 3× na trojkový stůl, tak se s nikým nepotkají 2×, ostatní hráči, co jsou na trojkový stůl pouze 2× se s jedním hráčem potkají 2× a s jedním, se stejně jako ti, dva další nepotkají vůbec. Líp to asi rozlosovat nepůjde, co? Já právě spekuluji o tom, zda by i mezi těmi, co jdou jen 2× na trojkový stůl nejde alespoň u některých eliminovat to potkání se s tím jedním hráčem znovu. Ale zatím jsem takovou variantu neobjevil, tudíž se domnívám, že neexistuje a není ani reálné prověřit všechny kombinace, jestli přeci jen nějaká o fous lepší kombinace neexistuje. I když zas toto je pro všechny víceméně stejně spravedlivé.

Upravil/a: Alesh

Zajímavá 0 před 2605 dny Sledovat Nahlásit



Odpovědi
Avatar uživatele
Quimby

Pokud úlohu rozšíříme na 16 hráčů a 4 stoly po 4. Pak každý člověk za těch 5 kol potká 15 lidí, čili pokud by nikoho nepotkal dvakrát, tak potká všechny.

Což je ale i skoro nejlepší řešení pro tvoji úlohu, neboť víš, že každý bude sedět u trojkového stolu právě dvakrát neboť potká právě 2 virtuální lidi. Kromě dvou lidí, kteří budou jednou sedět pouze ve dvou (protože se právě ty 2 virtuální lidé potkali), ale dále pak vždy po čtyřech.

Najít toto řešení je překvapivě velmi těžká úloha a co vím, tak neexistuje řešení pro obecný případ. A asi už vůbec ne pro různě velké stoly, proto ta aproximace. Jak si zjistil, tak projít všechna řešení by domácí počítač v rozumném čase nezvládl.

Každopádně pro 16lidí existuje konkrétní řešení, zde si o tom problému můžeš přečíst více: http://bit.ly/2fdwitb
A řešení: (s použitím písmenek)

  1. kolo: ABCD EFGH IJKL MNOP
  2. kolo: AEIM BFJN CGKO DHLP
  3. kolo: AFKP BELO CHIN DGJM
  4. kolo: AGLN BHKM CEJP DFIO
  5. kolo: AHJO BGIP CFLM DEKN

Ale nevysvětlím ti jak na něj přijít, neboť je to nad moje znalosti, ale mělo by to být z těch odkazů na vědecké články. Nyní si stačí vybrat ty 2 virtuální lidi a vyhodit je. Popřípadě můžeš trochu promíchat to kolo, kde se ty 2 lidi potkaj aby si dostal dva stoly po třech místo jednoho po dvou.


Ano, při 15 hráčích je tohle nejlepší řešení. Pro těch 14 lidí nevím jestli opravdu existuje nejlepší řešení a v tom odkazu a článcích jsem nenašel nic pro různě velké stoly a jak řikám, tak téhle matematice ještě moc nerozumím. Každopádně není to řešení s 2 virt. hráči dostatečně spravedlivé? Opravdu se za jednu hru naučím číst toho druhého hráče natolik aby z toho byla v druhé hře nějaká výhoda?

Upravil/a: Quimby

0 Nominace Nahlásit


Diskuze k otázce

U otázky nebylo diskutováno.

Nový příspěvek