Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 06. 12. 2017 21:59

akalier
Zelenáč
Příspěvky: 1
Škola: VŠB FEI
Pozice: student
Reputace:   
 

Hledání největšího řádu permutace

Dobrý den,

mám problém s příkladem, jehož zadání zní takto:

Petr a Michael vymysleli zajímavou hru. Každý z nich dostane jedenáct kamenů očíslovaných postupně čísly 1 až 11. Nyní mají oba za úkol vymyslet nějaký rafinovaný systém přeskládání kamenů (kterého se musí držet celou hru) tak, aby vytvořili více vzájemně různých řad než jejich oponent. Petrův systém je velmi chytrý, vezme kámen a posune ho v řadě o dvě pozice doprava. To znamená, že pokud měl Petr v první řadě kameny sestaveny postupně 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, tak druhá řada bude vypadat následovně: 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9 pak třetí řada: 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7 a tak dále.

2)    Jaký systém musí Michael vymyslet, aby nejen vyhrál nad Petrem, ale aby zároveň získal maximální možný počet vzájemně různých řad?

Tento příklad bych měla řešit tak, že hledám nejvyšší řád permutace, pokud tomu správně rozumím. Musím tedy rozdělit permutaci do cyklů tak, aby jejich velikosti daly co největší společný násobek. Nebo se pletu?

Napadlo mě řešení, kdy udělám cykly o velikosti 5 a 6:
$\pi  = (1,3,5,7,9,11)(2,4,6,8,10)$

NSN bude tedy 30.

Můj vyučující mi však řekl, že je třeba zdůvodnit, proč je řád 30 největší možný.
"Zkuste uvést nějaký důkaz (nejlépe napište všechny jednotlivé možnosti délek cyklů dané
permutace). Pokud je řešení permutace se dvěma cykly délky 5 a 6 správné, jedná se o jediné řešení?"

Nejsem si jistá, jak tomu mám rozumět. Mám tedy vypsat všechny další možnosti? Např. velikosti  cyklů 1 a 10, 2 a 9 a tak podobně a u všech určit řád? Ale jak to bude v případě určování řádu permutace, když budu mít 3, 4 a více cyklů, to přece nemohu všechno rozepisovat...?

Asi tomu moc dobře nerozumím, mohl by mi někdo poradit? Asi existuje nějaké elegantnější zdůvodnění.

Mnohokrát děkuji

Offline

 

#2 08. 12. 2017 20:03

petrkovar
Moderátor
Místo: Ostrava/Paskov
Příspěvky: 992
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Hledání největšího řádu permutace

↑ akalier:Ano, zadání rozumíte dobře. Co se rozebrání různých možností týká, není jich až zas tolik, že by se nevešly na jednu stranu A4. S výhodou lze využít systematický přístup:
Známe permutaci řádu 30=6*5. Jak dlouhý může být NEJDELŠÍ cyklus v případné permutaci 11 prvků, která je řádu většího než 30. Může taková permutace obsahovat cyklus délky 11? 10? 9? ... Jak to bude vypadat se zbývajícími cykly?

Offline

 

#3 08. 12. 2017 23:45

Welite
Zelenáč
Příspěvky: 2
Reputace:   
 

Re: Hledání největšího řádu permutace

Řeším stejný příklad, zajímalo by mě, vymyslel jsem způsob, se kterým lze dosáhnout až 80 výsledků, ale nevím zda splnuje podmínky zadání: "rafinovaný systém přeskládání kamenů (kterého se musí držet celou hru)"


Můj systém přeskládání:
Vezme se první prvek a přehodí se o jednu pozici doprava, v dalším kroku se vezmou první 2 prvky a posunou o 1 pozice doprava, v dalším kroku se vezme první prvek a posune se o 2 doprava. A pak už se to střídá, pořád dokola, v každém lichém kroku se přesouvá jeden prvek o takový počet pozic, který odpovídá celkovém počtu provedených posunutí a v sudém kroku se vždy posouvají první 2 prvky o jednu pozici doprava.

Na tento způsob jsem si napsal jednoduchý kod v Javě, který mi tyto kombinace generuje, výstup:
1,2,3,4,5,6,7,8,9,10,11,
10,11,1,2,3,4,5,6,7,8,9,
9,11,10,1,2,3,4,5,6,7,8,
7,8,9,11,10,1,2,3,4,5,6,
6,8,9,11,7,10,1,2,3,4,5,
4,5,6,8,9,11,7,10,1,2,3,
3,5,6,8,9,11,4,7,10,1,2,
.....


Teoreticky, kdybych do tohoto systému zakomponoval další podmínky (například, že v každém třetím kroku ještě vyměním nějaké prvky) získám mnohem více kombinací, tudíž maximální možný počet přeskládání je teoreticky: 11! (11 faktorial)

Offline

 

#4 10. 12. 2017 00:53

petrkovar
Moderátor
Místo: Ostrava/Paskov
Příspěvky: 992
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Hledání největšího řádu permutace

↑ Welite:Střídáte dva různé postupy. Podle zadání se ale má stále opakovat stejný postup.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson