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.
Namôjdušu, to je úplne perfektná úloha :-)
OdpovedaťOdstrániťPřiznávám, že jsem nic nepočítala. Šla jsem na to čistě dětsky a došla jsem k číslu 6.
OdpovedaťOdstrániťÚloha je to moc hezká, budu o ní ještě přemýšlet.
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).
OdpovedaťOdstrániťDalej mam taku hypotezu, ze taketo nieco plati nielen pre 21 kociek, ale pre vsetky sucty 1+2+...+k :)
vsetky cesty vedu k 6 5 4 3 2 1
OdpovedaťOdstrániťteda aspon pocitac tak zistil :) (dokaz pocitacom :) )
:) 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.
OdpovedaťOdstrániťPokúsme sa nájsť dôkaz Lenkinej všeobecnej hypotézy.
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)
OdpovedaťOdstrániťmam taky nie velmi exaktny dokaz toho, ze cyklus dlzky 1 existuje len ak mame veze vysky 1,...k.
OdpovedaťOdstrániť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 :)
Hm, ta Agatka si teda vie zvolit vhodny pocet kociek... :)
OdpovedaťOdstrániťHmm.. pri nahodnom rozlozni kociek, aky je priemerny pocet opakovani, kym sa dostaneme k ustalenemu stavu 1 2 3 4 5 6?
OdpovedaťOdstrániťPriemerný počet závisí od toho, ako je definované to "náhodné rozdelenie kociek".
OdpovedaťOdstrániť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?
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ý).
OdpovedaťOdstrániť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.
OdpovedaťOdstrániťAha, pardon, veď sa mi to aj zdalo príliš veľa :)
OdpovedaťOdstrániť