Posted By: Xofon (Xof) on 'CZriddles'
Title:     Z Jarni skoly - reseni I
Date:      Thu May  4 13:10:03 2006


     Pro zajemce uz zverejnim strucne vzorove reseni prikladu I.

Kodovani:

     Karty 1-52 si predstavime serazene cyklicky (vizualne na kruznici). 
Z nich jsme dostali 5, zbyva tedy 47 v balicku. A mezi temi peti kartami
je pet der. Podivame se na jejich velikosti. Vybereme nejvetsi diru (je-li 
nekolik stejne velkych, zvolime libovolnou z nich), stranou dame kartu, 
ktera tvori spodni hranici teto diry, a do poradi zbylych ctyr karet 
(kterych je 4!=24) zakoduju, na kolikate pozici ve vysledne dire je ta
zahozena.

Lemma: Vsechny diry krome jedne nejdelsi jsou velikosti <=23.
Dukaz: Kdyby nejaka byla velikosti v>=24, pak nejdelsi je velikosti
w>=v>=24, ale celkova velikost vsech der je 47 < 24+24 <= w+v. Spor.

Dekodovani:

     Vybereme nejvetsi diru a v ni podle poradi vybereme kartu.

Priklad:

     A dostane karty 10,20,30,40,50.

Velikosti der jsou:
10-20: 9,
20-30: 9,
30-40: 9,
40-50: 9,
50-10: 11 (pozice v dire jsou 51,52,1,2,3,4,5,6,7,8,9).
Nejvetsi dira: 50-10
Bokem dam _50_
Tim vznika nova nejvetsi dira: 40-10
Pozice zahozene karty v nove dire: 10
Desata permutace (ve slovnikovem poradi): 
    (abcd abcd acbd acdb adbc adcb bacd badc bcad) _bcda_
Poradi predavanych karet: 20 30 40 10.

     B dostane karty 20,30,40,10.

Nejvetsi dira: 40-10
Cislo permutace bcda: 10
Desata karta v mezere 40-10: 50
Odpoved: _50_

     Rozhodci overi, ze odpoved je spravna.

     Xof
:wq

Search the boards