25 januára 2012

Veže


  Agátka si z 21 drevených kociek postavila niekoľko veží. Z každej veže vzala vrchnú kocku a zo zozbieraných kociek postavila novú vežu. Potom opäť vzala z každej veže najvrchnejšiu kocku a z týchto kociek postavila novú vežu a tak ďalej. Keď po dlhom čase so svojou hrou skončila, koľko mala veží? 

Poznámka: Aj jednu kocku považujeme za vežu. Keď z takejto veže vezme Agátka vrchnú (čiže jedinú) kocku, táto veža zanikne a príslušná kocka sa stane súčasťou novej veže.

13 komentárov:

goober povedal(a)...

Namôjdušu, to je úplne perfektná úloha :-)

Tychi povedal(a)...

Přiznávám, že jsem nic nepočítala. Šla jsem na to čistě dětsky a došla jsem k číslu 6.
Úloha je to moc hezká, budu o ní ještě přemýšlet.

Lenka povedal(a)...

Mne to tiez vyslo 6 a navyse, vsetky pokusy skoncili v stave 1,2,3,4,5,6. Dokazat, ze z tohto sa "neda dostat", je lahke. Tazsie bude ukazat, ze kazde pociatocne rozlozenie vezi skonci v 1,2,3,4,5,6 (pripadne nejakej permutacii).
Dalej mam taku hypotezu, ze taketo nieco plati nielen pre 21 kociek, ale pre vsetky sucty 1+2+...+k :)

Rori povedal(a)...

vsetky cesty vedu k 6 5 4 3 2 1

teda aspon pocitac tak zistil :) (dokaz pocitacom :) )

Radoslav Harman povedal(a)...

:) Dôkaz počítačom je úplne akceptovateľný (nakoniec, pomocou preverenia veľkého množstva prípadov počítačom bol dokázaný aj slávny problém štyroch farieb), ale lepšie by bolo mať taký dôkaz, ktorý môže človek v rozumnom čase skontrolovať sám.

Pokúsme sa nájsť dôkaz Lenkinej všeobecnej hypotézy.

Rori povedal(a)...

Ja len z pozorovania vystupu z tych 21 - vzdy to skoncilo v tom 1 2 3 4 5 6 a nebol tam ziaden iny cyklus (teda ze by sa rozne kombinacie vezi v pocte 6 opakovali dookola)

Lenka povedal(a)...

mam taky nie velmi exaktny dokaz toho, ze cyklus dlzky 1 existuje len ak mame veze vysky 1,...k.
po presune vezi vysky n1,n2,...,nk dostaneme veze n1-1,...,nk-1,k.
chceme, aby sa tieto dve postupnosti rovnali.
nejake ni teda musi byt rovne 1, nech je to n1 (je jedno, ako to spermutovane). dalej musi pre nejake ni platit, ze ni=k, nech je to n2.
potom ale na pravej strane mame vyraz typu n2-1=k-1 a tomu musi zodpovedat nieco z lavej strany, napriklad n3.
podobne, na pravej strane potom je n3-1=k-2, co musime mat aj nalavo, tak polozme n4=k-2....no a tak sa da pokracovat dalej :)

Ruziklan povedal(a)...

Hm, ta Agatka si teda vie zvolit vhodny pocet kociek... :)

Anonymný povedal(a)...

Hmm.. pri nahodnom rozlozni kociek, aky je priemerny pocet opakovani, kym sa dostaneme k ustalenemu stavu 1 2 3 4 5 6?

goober povedal(a)...

Priemerný počet závisí od toho, ako je definované to "náhodné rozdelenie kociek".

Keď odignorujeme poradie veží, existuje 792 rôznych rozložení. Ak každé z nich vyberieme s rovnakou pravdepodobnosťou, očakávaný počet krokov je o kúsoček viac ako 20. Maximálny počet krokov vychádza 30 (a dá sa dosiahnuť zo 65 rôznych rozdelení).

Pri iných "trojuholníkových" počtoch to vychádza takto:
1 1 0 0 (1)
3 3 1 2 (1)
6 11 3 6 (1)
10 42 ~6 12 (3)
15 176 ~12 20 (16)
21 792 ~20 30 (65)
28 3718 ~30 42 (293)

(počet kociek, počet rozostavení, priemerný počet krokov po "pevný bod", maximálny počet krokov potiaľ a počet počiatočných rozostavení, ktoré toto maximum dosahujú).

Jedno také ad-hoc pozorovanie -- maximálny počet krokov je vždy dvojnásobok počtu kociek v predošlom riadku. Inak povedané, ak je kociek Q*(Q+1)/2, maximálny počet krokov je Q*(Q-1). Je to len náhoda?

Radoslav Harman povedal(a)...

goober, Ty sa s tým teda riadne pohral; zaujímavé by bolo vidieť to počiatočné rozdelenie 28 kociek, ktoré vedie k pevnému bodu až po 293 krokoch. Vidím, že sa mi šťastnou náhodou podarilo trafiť pomerne komplexný problém (ale aj dosť ťažký).

goober povedal(a)...

Ee, 293 nie je maximálny počet krokov (ten je iba 42), je to počet rôznych rozostavení, ktoré ten maximálny počet krokov dosahujú. T.j. existuje 293 rôznych počiatočných rozostavení veží (ignorujúc poradie), pre ktoré to trvá 42 krokov, kým dospejú do stabilnej trojuholníkovej konfigurácie.

Radoslav Harman povedal(a)...

Aha, pardon, veď sa mi to aj zdalo príliš veľa :)