Studentsk´y matematicko-fyzik´aln´ı ˇcasopis Roˇ cn´ık XX
ˇ ıslo C´ 4
ˇ sen´ı u Zad´ an´ı u ´ loh ˇ ctvrt´ e s´ erie – str. 2 • Reˇ ´ loh druh´ e s´ erie – str. 3 T´ ema 3: FlatFox – str. 8 • Mgr.MM Dominik Krasula: Hr´ atky se ˇ ctverci – str. 8 T´ ema 4: Do hlubin – str. 10 • Bc.MM Aneta K. Lesn´ a: Projekt Lindenbaum – str. 10 Dominika Tanglov´ a: Pl´ an mise – str. 12 • T´ ema 5: Sd´ılen´ı tajemstv´ı – str. 13 Doc.MM Mark´ eta Cal´ abkov´ a: O kl´ıˇ c´ıch teoreticky – str. 14 Mgr.MM Dominik Krasula: O vyuˇ zit´ı prvoˇ c´ısel pro sd´ılen´ı tajemstv´ı – str. 16 Dr.MM Matej Lieskovsk´ y: Sd´ılen´ı tajemstv´ı na ˇ c´ınsk´ y zp˚ usob – str. 17
ˇ Casopis M&M a stejnojmenn´y korespondenˇcn´ı semin´ aˇr je urˇcen pro studenty stˇredn´ıch ˇskol, kteˇr´ı se zaj´ımaj´ı o matematiku, fyziku ˇci informatiku. Bˇehem ˇskoln´ıho roku dost´ avaj´ı ˇreˇsitel´e zdarma ˇc´ısla se zad´ an´ım u ´loh a t´emat k pˇrem´yˇslen´ı. Sv´ a ˇreˇsen´ı odes´ılaj´ı k n´ am do redakce. My jejich pˇr´ıspˇevky oprav´ıme, obodujeme a poˇsleme zpˇet. Nejzaj´ımavˇejˇs´ı ˇreˇsen´ı otiskujeme.
2 Mil´ y ˇreˇsiteli, bl´ıˇz´ı se pololet´ı a spoleˇcnˇe s n´ım se i n´ aˇs korespondenˇcn´ı semin´aˇr dost´av´a do druh´e poloviny. Opˇet ti pˇrin´ aˇs´ıme nov´e u ´lohy i nˇekolik pˇr´ıspˇevk˚ u k t´emat˚ um. St´ ale m˚ uˇzeˇs ale pˇrisp´ıvat i k t´emat˚ um uveˇrejnˇen´ ym v nˇekter´em z pˇredchoz´ıch ˇc´ısel. R´ adi bychom pˇripomnˇeli, ˇze autor nejpovedenˇejˇs´ıho pˇr´ıspˇevku k t´ematu od n´ as dostane na konci ˇskoln´ıho roku dort. Pˇribliˇznˇe 20 nej´ uspˇeˇsnˇejˇs´ıch ˇreˇsitel˚ u pozveme jako obvykle na jaˇre na soustˇredˇen´ı (konkr´etnˇe se bude konat 29. 3.–6. 4.). Pˇri pohledu do v´ ysledkov´e listiny zjist´ıˇs, ˇze na 20. pozici v semin´ aˇri zat´ım nen´ı potˇreba aˇz tak moc bod˚ u, na soustˇredˇen´ı se tedy m˚ uˇze dostat skuteˇcnˇe kaˇzd´ y. Nenech se o tuto moˇznost pˇripravit! Jeˇstˇe pˇred soustˇredˇen´ım bychom tˇe ale r´ adi pozvali i na dalˇs´ı akce, kter´e Matfyz v Praze poˇr´ ad´ a. Ve ˇctvrtek 6. u ´nora se kon´ a Jeden den s fyzikou (den pln´ y pˇredn´ aˇsek a exkurz´ı pro veˇrejnost), 14. u ´nora je pak tradiˇcn´ı fyzik´aln´ı t´ ymov´a soutˇeˇz Fykos´ı Fyzikl´ an´ı. V´ıce informac´ı najdeˇs v pˇriloˇzen´ ych let´aˇcc´ıch. Pokud bys chtˇel str´ avit z´ abavou s matematikou a fyzikou i ˇc´ast letn´ıch pr´azdnin, m˚ uˇzeme ti doporuˇcit Letn´ı ˇskolu matematiky a fyziky, kter´a prob´ıh´a podobnˇe jako naˇse soustˇredˇen´ı a o jej´ımˇz term´ınu tˇe budeme jeˇstˇe informovat. Jestli upˇrednostˇ nujeˇs v´ıce odborn´eho programu, jsou tu pro tebe odborn´e t´abory, jejichˇz nab´ıdku pˇrikl´ ad´ ame uˇz nyn´ı. Pˇrejeme ti hodnˇe u ´spˇech˚ u nejen pˇri pot´ yk´ an´ı se s probl´emy naˇseho semin´aˇre. organiz´ atoˇri M&M
Zad´ an´ı u ´loh Term´ın odesl´ an´ı tˇ ret´ı s´ erie: 3. 3. 2014
Zde u ´hlopˇr´ıˇcky rovn´e a nespoutan´e obs´ ahnou nebe.
´ Uloha 4.1 – Mnoho´ uheln´ık
(3b)
Sestrojte pravideln´ y mnoho´ uheln´ık, kdyˇz zn´ ate d´elku nejdelˇs´ı a druh´e nejdelˇs´ı u ´hlopˇr´ıˇcky. Aby to nebylo moc jednoduch´e, tak ale nezn´ate poˇcet stran mnohou ´heln´ıku. Jarn´ı n´ alada zahal´ı pˇretlakovou kom˚ urku ticha.
XX/4
3
´ Uloha 4.2 – Poissonova
(3b)
Uvaˇzujme uzavˇrenou n´ adobu se vzduchem. N´ adobu pˇretlakujeme na tlak p1 pˇri pokojov´e teplotˇe. Pot´e na kr´ atk´ y ˇcas otoˇc´ıme ventilem, neˇz se vyrovn´a tlak v n´adobˇe s okol´ım. Jak´ y tlak bude v n´ adobˇe po vyrovn´ an´ı teplot plynu s okol´ım? Uvaˇzujte tlaky bl´ızk´e atmosferick´emu tlaku. Mohla by se hodit aproximace (1 + x)n ≈ 1 + xn pro x 1. Vlah´ a je rosa cestou pak po zelen´e k´ ac´ıme stromy.
´ Uloha 4.3 – Barven´ı grafu
(4b)
M´ ame acyklick´ y orientovan´ y graf1 s nejdelˇs´ı orientovanou cestou d´elky2 maxim´alnˇe k. Ukaˇzte, ˇze lze vrcholy grafu obarvit nejv´ yˇse k barvami tak, aby ˇz´adn´a hrana nespojovala dva vrcholy se stejnou barvou. Mlhav´y opar kulatou sklenkou nap˚ ul rozl´ev´ an r´ anem.
´ Uloha 4.4 – Kruhy
(2b)
Ukaˇzte, ˇze kruh s pr˚ umˇerem 2 lze pokr´ yt sedmi kruhy s pr˚ umˇerem 1.
ˇ sen´ı u Reˇ ´loh ´ Uloha 2.1 – Kˇr´ıˇ z
(3b)
Zad´ an´ı: Pap´ır ve tvaru ˇctverce tuˇzkou rozdˇel´ıme na 9 menˇs´ıch stejnˇe velk´ych ˇctverc˚ u. Po odstˇrihnut´ı 4 rohov´ych ˇctverc˚ u dostaneme kˇr´ıˇz. Jak ho lze rozdˇelit dvˇema ˇrezy tak, aby ze vznikl´ych ˇc´ ast´ı bylo moˇzn´e opˇet poskl´ adat ˇctverec? ˇ sen´ı: Reˇ Protoˇze m´ ame ˇctverec rozdˇelit na 9 stejn´ ych ˇctverc˚ u, jedin´e ˇreˇsen´ı je rozdˇelit 1 Graf si m˚ uˇ zete pˇredstavit jako nˇ ejak´ e body, napˇr´ıklad mˇ esta, (tˇ em se ˇr´ık´ a vrcholy) pospojovan´ e cestami (tˇ em se ˇr´ık´ a hrany), pokud se cesty kˇr´ıˇ z´ı tak vˇ zdy mimo´ urovˇ novˇ e (tj. pˇrejet na jinou cestu se d´ a jen ve mˇ estˇ e). Orientovan´ y znamen´ a, ˇ ze vˇsechny cesty jsou jednosmˇ erky. Acyklick´ y znamen´ a, ˇ ze kdyˇ z vyraz´ıte z libovoln´ eho mˇ esta, tak uˇ z do nˇ ej nikdy nem˚ uˇ zete dojet zpˇ et. 2 Cesta d´ elky k je cesta, bˇ ehem kter´ e navˇst´ıv´ım k mˇ est, vˇ cetnˇ e poˇ c´ ateˇ cn´ıho a koncov´ eho.
4 kaˇzdou stranu na tˇretiny. Zvolme, ˇze d´elka strany p˚ uvodn´ıho ˇctverce je 3. Potom m´ a vznikl´ y kˇr´ıˇz d´elky stran 1 a obsah 5. Pokud ho chceme jakkoli √ rozdˇelit a vytvoˇrit ˇctverec, mus´ı m´ıt ˇctverec tak´e obsah 5 a tedy d´elku strany 5. √ √ Mus´ıme tedy v kˇr´ıˇzi naj´ıt dva ˇrezy d´elky 5, protoˇze 5 nelze vyj´adˇrit jako souˇcet pˇrirozen´ ych ˇc´ısel (d´eka strany kˇr´ıˇze) a nˇejak´ ych jin´ ych druh´ ych odmocnin (jin´e ˇrezy). Zp˚ usob˚ u, jak tento ˇrez um´ıstit je nˇekolik, pˇr´ıklady vid´ıte na obr´azc´ıch. Druh´ y ˇrez mus´ı b´ yt na prvn´ı kolm´ y, protoˇze ˇrezy budou tvoˇrit obvod ˇctverce a strany ˇctverce jsou na sebe kolm´e. Opˇet m´ ame nˇekolik zp˚ usob˚ u, jak tento ˇrez um´ıstit. Pot´e uˇz staˇc´ı uk´ azat, ˇze do sebe d´ıly zapadnou, coˇz je vˇetˇsinou vidˇet pˇres jednoduch´e shodnosti.
ˇ Jedno z moˇzn´ eji: Kˇr´ıˇz ABCDEF GHIJKL, ˇrezy r1 , r2 . Rezy √ych ˇreˇsen´ı detailnˇ √ 2 2 |KF | = |SU | = 2 + 1 = 5. U je stˇred CD, protoˇze r2 p˚ ul´ı obd´eln´ık BP EF . Pokud tento obd´eln´ık posuneme po r2 tak, ˇze P 0 = F , tak z´ısk´ame, ˇze S je stˇredem GH. Proto pokud posuneme KF SHIJ tak, ˇze K 0 F 0 = QP , tak na sebe budou ˇc´ asti navazovat.
SGF je shodn´e s RAQ, protoˇze |AQ| = |GF |, oba jsou pravo´ uhl´e a KQ je
XX/4
5
rovnobˇeˇzn´ a s P S, tedy maj´ı shodn´e vˇsechny u ´hly a stranu. Obdobnˇe U DEF je shodn´ y s RALK, protoˇze m´ a2u ´hly prav´e, |U D| = |SG| = |RA| a 1 = |F E| = |ED| = |KL| = |LA|. T´ımto jsme dok´ azali, ˇze d´ıly na sebe navazuj´ı a tvoˇr´ı ˇctverec. Jethro
´ Uloha 2.2 – Knihovna
(2b)
Zad´ an´ı: Reg´ al obsahuje N knih seˇrazen´ych podle sv´eho n´ azvu, pˇriˇcemˇz ˇz´ adn´e dvˇe knihy se nejmenuj´ı stejnˇe. Chtˇeli bychom je pˇreuspoˇr´ adat tak, aby kaˇzd´ a byla na pozici pr´ avˇe o K vˇetˇs´ı nebo menˇs´ı. Pro jak´ a K v z´ avislosti na N to m˚ uˇzeme prov´est? ˇ sen´ı: Reˇ Knihy si po ˇradˇe oˇc´ıslujeme 1, 2, . . . , N . Vˇsimnˇeme si nejdˇr´ıv, ˇze K < N . V opaˇcn´em pˇr´ıpadˇe bychom nemohli ˇz´ adnou knihu pˇresunout. Pokud by byla kniha na pozici 1 ≤ p ≤ N , pak ji mus´ıme pˇresunout bud’ na pozici p + K ≥ p + N ≥ N + 1, nebo na pozici p − K ≤ p − N ≤ 0, ale takov´e pozice v knihovnˇe nejsou. Ted’ si vˇsimnˇeme, ˇze knihy na pozic´ıch 1, . . . , K mus´ıme pˇresunout doprava, nalevo bychom narazili na okraj knihovny. Knihy tedy pˇresuneme na pozice K + 1, . . . , 2K. Naopak na pozice 1, . . . , K m˚ uˇzeme pˇresunout pouze knihy z pozic K+1, . . . , 2K. A vida, N mus´ı b´ yt alespoˇ n 2K, jinak prvn´ıch K knih nepˇresuneme. T´ım jsme vyˇreˇsili prvn´ıch 2K knih a uˇz s nimi nem˚ uˇzeme h´ ybat. Pokud N = 2K, tak jsme vyhr´ ali a knihy jsou spr´ avnˇe pˇreskl´ adan´e. V opaˇcn´em pˇr´ıpadˇe jsme se ale dostali do situace, kdy m´ ame pˇresunout knihy v knihovnˇe o N −2K knih´ach. Pro prvn´ıch 2K knih (tj. knihy na pozic´ıch 2K +1 aˇz 4K) m´ame opˇet jednoznaˇcnˇe urˇceno, jak je pˇresunout. Postupnˇe tedy mus´ıme pˇreskl´ad´avat bloky o 2K knih´ach, dokud nepˇreskl´ ad´ ame celou knihovnu, nebo neskonˇc´ıme s blokem menˇs´ım neˇz 2K, kter´ y pˇreskl´ adat nelze. Doˇsli jsme tedy k tomu, ˇze knihy lze pˇreskl´ adat pouze tehdy, kdyˇz m˚ uˇzeme knihovnu rozdˇelit na bloky o velikost 2K, tedy N = 2Ka pro nˇejak´e pˇrirozen´e ˇ ıslo K tud´ıˇz mus´ı b´ ˇc´ıslo a. C´ yt nˇejak´ y dˇelitel N/2 (coˇz m´a samozˇrejmˇe smysl jen, je-li N/2 cel´e). Nav´ıc jsme pˇredt´ım uk´ azali, ˇze pokud toto plat´ı, tak knihovnu pˇreskl´ adat m˚ uˇzeme, tedy opravdu vyhovuj´ı vˇsechna takov´a K. Leˇc, zapomnˇeli jsme (stejnˇe jako spousta z v´ as) na jeden trivi´ aln´ı pˇr´ıpad – K = 0. Tehdy knihy m˚ uˇzeme pˇreskl´ adat vˇzdy – prostˇe je nech´ ame na p˚ uvodn´ıch m´ıstech. Asi nejˇcastˇejˇs´ı chybou bylo, ˇze jste usoudili, ˇze knihovna je cyklick´a. Bohuˇzel n´ as nenapadlo, ˇze by si nˇekdo mohl zad´ an´ı takto vykl´adat, pˇrece jen, poliˇcky v knihovnˇe prostˇe do kruhu nejsou. Nav´ıc, takov´e pˇresunut´ı knih vˇetˇsinou zadanou podm´ınku nespln´ı. Vezmˇeme si tˇreba N = 5, K = 3 a knihu na pozici p = 4. Podle zad´ an´ı m´ ame tuto knihu pˇresunout na pozici p+K = 7 nebo p−K = 1. T´ım, ˇze ji cyklicky pˇresuneme dozadu, ji ale pˇresuneme na pozici 2, coˇz zad´an´ı nevyhovuje. O(N)dra
6
´ Uloha 2.3 – Suˇs´ arna
(4b)
Zad´ an´ı: Venku je 0 ◦ C a prˇs´ı. V mal´e nevˇetran´e suˇs´ arnˇe vytopen´e na 25 ◦ C se snaˇz´ıme usuˇsit velk´e mnoˇzstv´ı mokr´eho pr´ adla. Po nˇekolika dnech je pr´ adlo st´ ale mokr´e. Pom˚ uˇze suˇsen´ı rychl´e vyvˇetr´ an´ı? Kolik vody zkondenzuje v m´ıstnosti nebo kolik vody se odpaˇr´ı z pr´ adla po jednom rychl´em vyvˇetr´ an´ı? ˇ Reˇ sen´ı: Shrˇ nme si napˇred, co vlastnˇe v´ıme – to je vˇzdycky dobr´ y zaˇc´atek. . . M´ame malou m´ıstnost se spoustou mokr´eho pr´ adla, kter´e n´ am nechce schnout. Z toho lze vyvodit, ˇze vzduch v m´ıstnosti je uˇz vodou zcela nasycen. V m´ıstnosti je stoprocentn´ı vlhkost. Venku prˇs´ı. D´eˇst’ nast´ av´ a, kdyˇz uˇz vzduch nen´ı schopen udrˇzet vodu, a zaˇcne ji uvolˇ novat. M˚ uˇzeme tedy ˇr´ıci, ˇze venku je tak´e stoprocentn´ı vlhkost. (Vlastnˇe v sobˇe vzduch tu vlhkost uˇz nemohl udrˇzet d´ele, proto se vytvoˇrila ta soustava mikrokapiˇcek, kter´e ˇr´ık´ ame mrak.) Vyvˇetr´ an´ım vymˇen´ıme vzduch z m´ıstnosti za vzduch z venku. Mluv´ıme ale o relativn´ı vlhkosti. Ta je definov´ ana jako pomˇer mnoˇzstv´ı vody re´ alnˇe pˇr´ıtomn´e v dan´em objemu vzduchu, % [g/m3 ], v˚ uˇci mnoˇzstv´ı vody, kter´e dan´ y objem vzduchu maxim´ alnˇe pojme pˇri dan´e teplotˇe t, %t [g/m3 ]. Pokud chceme zjistit absolutn´ı vlhkost vzduchu venku a vevnitˇr, mus´ıme v tabulk´ach dohledat tyto maxim´ aln´ı hodnoty pro dan´e teploty. Moje tabulky maxim´aln´ı mnoˇzstv´ı vody ve vzduchu dan´e teploty uv´ adˇej´ı jako dva r˚ uzn´e parametry: hustotu a tlak nasycen´e vodn´ı p´ ary. Hustota nasycen´e p´ ary je naˇse %t . Pokud jste naˇsli tyto u ´daje, byl v´ ypoˇcet trivi´ aln´ı: Pˇri teplotˇe 0 ◦ C je hustota nasycen´ ych par 4.85 g/m3 , pˇri teplotˇe 25 ◦ C je 3 to 23.04 g/m . Pokud napln´ıme m´ıstnost studen´ ym vzduchem zvenku a zavˇreme okno, vzduch se ohˇreje opˇet na teplotu 25 ◦ C. Pˇri teplotˇe 25 ◦ C se n´am do kub´ıku vzduchu vejde 23.04 g vody, ale m´ ame v nˇem jenom 4.85 g, takˇze se jeˇstˇe dalˇs´ıch 18.19 g vody na kaˇzd´ y kub´ık vzduchu v m´ıstnosti m˚ uˇze vypaˇrit z pr´adla. Pokud jste naˇsli jen tlak nasycen´ ych par, bylo potˇreba trochu poˇc´ıtat. Budeme pˇredpokl´ adat, ˇze vodn´ı p´ ara je ide´ aln´ı plyn. Pˇri takto n´ızk´ ych tlac´ıch to, jak uvid´ıte, sed´ı. Stavov´ a rovnice ide´ aln´ıho plynu je pV = nRT , kde p je tlak vodn´ıch par, V objem, my budeme uvaˇzovat jednotkov´ y objem (1 m3 ), n mol´ arn´ı mnoˇzstv´ı plynu, R = 8.31 J/( K · mol) univerz´aln´ı plynov´a konstanta a T absolutn´ı teplota. Mol´ arn´ı mnoˇzstv´ı plynu si m˚ uˇzeme vyj´adˇrit jako m , M kde m je jeho hmotnost a M mol´ arn´ı hmotnost vody. Mol´arn´ı hmotnost vody je 18 g/mol. Dosad´ıme do stavov´e rovnice a dostaneme n=
XX/4
7
m RT % = . VM M T´ım jsme z´ıskali pˇrepoˇcet tlaku vodn´ıch par na jejich hustotu a pˇrevedli tak situaci na pˇredchoz´ı pˇr´ıpad. Tabulky tvrd´ı, ˇze tlak nasycen´ ych vodn´ıch par pˇri teplotˇe 0 ◦ C je 611 Pa a pˇri teplotˇe 25 ◦ C 3168 Pa. Pokud tyto hodnoty dosad´ıme do odvozen´eho vzorce, dostaneme skuteˇcnˇe dˇr´ıve zm´ınˇen´e hustoty nasycen´ ych vodn´ıch par, a je tak vidˇet, ˇze aproximace ide´ aln´ım plynem je v poˇr´adku. p = RT
Zuzka
´ ˇ rstˇ Uloha 2.4 – Ctyˇ en
(2b)
Zad´ an´ı: Souˇcet u ´hl˚ u kolem kaˇzd´eho vrcholu ˇctyˇrstˇenu je roven 180 ◦ . Ukaˇzte, ˇze vˇsechny stˇeny ˇctyˇrstˇenu si jsou podobn´e.
ˇ sen´ı: Reˇ Rozloˇzme si ˇctyˇrstˇen na jeho troj´ uheln´ıkovou s´ıt’ tak, jak je vidˇet na obr´azku – vrcholy prostˇredn´ıho troj´ uheln´ıka oznaˇcme A, B, C, zb´ yvaj´ıc´ı vrcholy krajn´ıch troj´ uheln´ık˚ u oznaˇcme postupnˇe D, E, F . Z podm´ınky ze zad´an´ı plyne, ˇze u ´hly EAF , F BD a DCE maj´ı hodnotu 180 ◦ – jsou pˇr´ım´e. Troj´ uheln´ıky tvoˇr´ıc´ı s´ıt’ tedy tvoˇr´ı jeden velk´ y troj´ uheln´ık s vrcholy D, E, F . Body A, B, C jsou stˇredy stran velk´eho troj´ uheln´ıka DEF (´ useˇcky AE a AF maj´ı stejnou d´elku, protoˇze obˇe odpov´ıdaj´ı stejn´e hranˇe p˚ uvodn´ıho ˇctyˇrstˇenu, obdobnˇe postupujeme pro dalˇs´ı strany). To znamen´ a, ˇze AB, BC a CA jsou stˇredn´ı pˇr´ıˇcky troj´ uheln´ıka DEF . Stˇredn´ı pˇr´ıˇcka je rovnobˇeˇzn´ a se svou odpov´ıdaj´ıc´ı stranou, takˇze AB k ED, BC k F E, CA k DF . S vyuˇzit´ım souhlasn´ ych a stˇr´ıdav´ ych u ´hl˚ u jiˇz snadno ovˇeˇr´ıme, ˇze jsou vˇsechny ˇctyˇri troj´ uheln´ıky podobn´e. Plat´ı ∠F AB = ∠F EC = ∠AEC = ∠BCD, ∠F BA = ∠F DC = ∠BDC = ∠ACE, takˇze troj´ uheln´ıky ABF , BCD a CAE si jsou navz´ ajem podobn´e podle vˇety uu. Nav´ıc ∠CAB = ∠ABF a ∠CBA = ∠BAF (stˇr´ıdav´e u ´hly), takˇze i prostˇredn´ı troj´ uheln´ık ABC je podobn´ y ostatn´ım. Ve skuteˇcnosti jsou strany ˇctyˇrstˇenu dokonce shodn´e, nebot’ maj´ı stejn´e d´elky. Pepa
8
ˇ sen´ı t´ Reˇ emat T´ ema 3 – FlatFox Od Mgr.MM Dominika Krasuly jsme dostali nˇekolik kr´atk´ ych pˇr´ıspˇevk˚ u ˇreˇs´ıc´ıch nˇekter´e bˇeˇznˇejˇs´ı matematick´e probl´emy a u ´kony s d˚ urazem na efektivitu. Mezi nimi odmocˇ nov´ an´ı, rozkl´ ad´ an´ı na ˇctverce, nˇekter´e kombinatorick´e funkce (binomick´ y koeficient a Catalanova ˇc´ısla), nejvˇetˇs´ı spoleˇcn´ y dˇelitel a pak nˇekolik operac´ı, kter´e berou ˇc´ıslo v registru jako ˇretˇezec cifer3 , konkr´etnˇe cifern´ y souˇcet v dan´e soustavˇe a pak pˇrevod mezi soustavami (opˇet vn´ım´ame-li ˇc´ıslo jako ˇretˇezec). Vˇsechny programy jsou pro p˚ uvodn´ı FlatFox. St´ ale je velmi otevˇren´e t´ema novinek v FF++, at’ uˇz s´ıla a rychlost ve srovn´an´ı s FF, teoretick´e koncepty vol´ an´ı podporgram˚ u a jejich struktura, nebo konkr´etn´ı programy ˇreˇs´ıc´ı zaj´ımav´e u ´lohy. Tom´ aˇs
Hr´atky se ˇctverci
(8b)
Mgr.MM Dominik Krasula Pozn. red.: Uv´ ad´ıme jen jeden ze s´erie ˇcl´ ank˚ u Mgr.MM Krasuly. Programy a nˇekolik dalˇs´ıch text˚ u najdete na str´ ance t´ematu.
Jak vytvoˇ rit ˇ ctverec4 M˚ uˇzeme ˇc´ıslo prostˇe umocnit na druhou. Jedn´ a se o z´akladn´ı funkci FlatFoxu (hodnotu zkop´ırujeme a pot´e kopii a p˚ uvodn´ı ˇc´ıslo vyn´asob´ıme). Nen´ı to vˇsak jedin´ a moˇznost: Pn−1 Tvrzen´ı. Pro kaˇzd´e n ∈ N plat´ı n2 = k=0 2k + 1 D˚ ukaz. Dok´ aˇzeme to indukc´ı, pro n = 1 to plat´ı trivi´alnˇe. Pˇredpokl´ad´ame tedy, ˇze pro n vzorec plat´ı. Uk´ aˇzeme, ˇze mus´ı platit i pro n+1: (n+1)2 = n2 +2n+1 → 2 2 (n + 1) − n = 2n + 1.
Odmocnˇ en´ı S vyuˇzit´ım vztahu v´ yˇse m˚ uˇzeme pˇresnˇe odmocnit ˇctverec. V pˇr´ıpadˇe odmocˇ nov´ an´ı neˇctverce z´ısk´ ame horn´ı celou ˇc´ ast odmocniny. 1. 2. 3. 4.
M´ ame nˇejak´ y odeˇcetn´ı registr, v nˇem je na zaˇc´atku jedniˇcka. Tento registr vˇzdy odeˇcteme od hodnoty odmocˇ novan´eho ˇc´ısla Pˇriˇcteme jedna k registru pro v´ ysledek. Zkontrolujeme, zda-li je v odmocˇ novan´em registru jeˇstˇe kladn´a hodnota, pokud ano, pˇriˇcteme k odeˇcetn´ımu registru 2 a vrac´ıme se ke kroku 2. 5. Pokud se odmocˇ novan´ y registr jiˇz vynuloval, program konˇc´ı. 3 I kdyˇ z jsou ˇ c´ısla zobrazena des´ıtkovˇ e, interpretr je vid´ı jen jako hodnoty bez konkr´ etn´ı soustavy. 4 Ctverec ˇ je oznaˇ cen´ı pro druhou mocninu pˇrirozen´ eho ˇ c´ısla.
XX/4
9
Prvoˇ c´ısla a ˇ ctverce Tvrzen´ı. Pro k ∈ N: 1. Kaˇzd´e prvoˇc´ıslo, kter´e lze zapsat ve tvaru 4k +1, lze zapsat jsko souˇcet dvou ˇctverc˚ u. 2. Kaˇzd´e lich´e prvoˇc´ıslo, kter´e nelze zapsat ve tvaru 4k + 1, nelze zapsat jako souˇcet dvou ˇctverc˚ u. Dok´ aˇzeme si pouze ˇc´ ast 2, d˚ ukaz ˇc´ asti 1 je velmi dlouh´ y a je v nˇem pouˇzit´a sloˇzit´ a matematika. Lemma. Kaˇzd´ y ˇctverec lze zapsat ve tvaru 4k, jedn´a-li se o sud´ y ˇctverec. Pokud je lich´ y, lze ho zapsat pouze ve tvaru 4k + 1. D˚ ukaz lemmatu. Jak´ekoliv ˇc´ıslo m˚ uˇzeme zapsat jako 4k + l, kde l je jedno z ˇc´ısel 0, 1, 2, 3. Kdyˇz takov´e ˇc´ıslo mocn´ıme, z´ısk´ ame: (4k + 0)2 ≡ 0 (mod 4), 2 2 (4k + 1) ≡ 1 (mod 4), (4k + 2) ≡ 4 (mod 4) ≡ 0 (mod 4) nebo (4k + 3)2 ≡ 9 (mod 4) ≡ 1 (mod 4). D˚ ukaz tvrzen´ı. Prvoˇc´ıslo lze zapsat bud’ ve tvaru 4k + 1 nebo 4k + 3, jinak by se jednalo o sud´e ˇc´ıslo. Hodnotu 4k + 3 souˇctem dvou ˇctverc˚ u z´ıskat dle lemmatu nem˚ uˇzeme, jedn´ a se o lich´e ˇc´ıslo, mus´ı tedy b´ yt souˇctem lich´eho a sud´eho ˇc´ısla, tedy 4k + (4l + 1) = 4(k + l) + 1. Z lemmatu d´ ale vypl´ yv´a, ˇze prvoˇc´ıslo ve tvaru 4k + 1 bude souˇctem lich´eho a sud´eho ˇctverce.
Program N´ asleduj´ıc´ı program zjist´ı, zda-li je ˇc´ıslo ve tvaru 4k + 1 a pokud ano, rozdˇel´ı jej na dva ˇctverce. Jestli se jedn´ a o prvoˇc´ıslo m˚ uˇzeme ovˇeˇrit tak, ˇze pˇrid´ame na zaˇc´ atek program Prime, nicm´enˇe prim´ arn´ı u ´ˇcel programu je rozdˇelit prvoˇc´ıslo na ˇctverce, takˇze bude pˇredpokl´ adat, ˇze mu jako vstup budeme d´avat prvoˇc´ısla. Princip programu je jednoduch´ y, bude od p˚ uvodn´ıho ˇc´ısla odeˇc´ıtat lich´e ˇctverce a v´ ysledek vˇzdy zkus´ı odmocnit, pokud odmocnˇen´ı nevyjde, tak pouˇzit´ y lich´ y ˇctverec nebyl spr´ avn´ y. Kdybychom ˇc´ıslo neust´ ale obnovovali, byla by ˇcasov´a sloˇzitost programu vysok´ a. Proto by bylo dobr´e odeˇc´ıtat rozd´ıl mezi lich´ ym ˇctvercem, kter´ y jsme jiˇz odeˇcetli, a n´ asleduj´ıc´ım lich´ ym ˇctvercem, nemuseli bychom pak ˇc´ıslo obnovovat. Rozd´ıl mezi lich´ ymi ˇctverci je (2n + 3)2 –(2n + 1)2 = (4n2 − 4n2 ) + (12n − 4n) + (9 − 1) = 8n + 8, Pn m˚ uˇzeme tedy vyvodit vztah (2n + 1)2 = 1 + k=0 8k. Z toho lze napsat program pro odmocnˇen´ı lich´eho ˇc´ısla. Odmocˇ novan´e ˇc´ıslo je v registru R, pouˇz´ıv´ ame pomocn´ y registr B, do registru G ukl´ad´ame v´ ysledek. 1. Odeˇcteme 1 od R. 2. B := B + 8; R := R − B; G := G + 8
10 3. Zkouˇska, zda-li je R ˇctvercem. Pokud ano, program konˇc´ı, naˇsli jsme v´ ysledek. Pokud ne, vrat’ se k 2. Zjednoduˇsit m˚ uˇzeme i odmocˇ nov´ an´ı sud´ ych ˇctverc˚ u: (2n + 2)2 − (2n)2 = (4n2 − 4n2 ) + (8n) + (4) = 8n + 4, vztah pak bude (2n)2 =
Pn
k=0 (8k
+ 4) a program obdobn´ y jako v´ yˇse.
Celkov´ y program tedy bude vypadat n´ asledovnˇe: Odeˇcte 1 od vstupu (nejniˇzˇs´ı lich´ y ˇctverec), zkus´ı odmocnit. Odeˇcte 8 od vstupu (uˇz odeˇcetl 9, druh´ y nejniˇzˇs´ı lich´ y ˇctverec), zkus´ı odmocnit. Odeˇcte 16 od vstupu (uˇz odeˇcetl 25, tˇret´ı nejniˇzˇs´ı lich´ y ˇctverec), zkus´ı odmocnit. ...
T´ ema 4 – Do hlubin K t´ematu pˇriˇsly pouze dva pˇr´ıspˇevky, kter´e pˇrin´ aˇsej´ı mnohem v´ıce ot´azek neˇz odpovˇed´ı. Objevuje se nˇekolik zaj´ımav´ ych myˇslenek, bohuˇzel vˇsechny konˇc´ı jejich pouh´ ym konstatov´ an´ım. Douf´ ame, ˇze se nˇekdo dalˇs´ı chop´ı pˇr´ıleˇzitosti a nˇekter´ y ˇ anky otiskujeme jen s dotazy a pozn´amkami z aspekt˚ u mise vyˇreˇs´ı podrobnˇeji. Cl´ redakce.
Projekt Lindenbaum
(2b)
Bc.MM Aneta K. Lesn´a Pˇredstavuji v´ am projekt Lindenbaum“, projekt ˇcesk´e ponorky navrˇzen´e pri” m´ arnˇe pro u ´ˇcel pr˚ uzkumu Mariansk´eho pˇr´ıkopu. Ponorka Linde“ vypad´ a i z d´ alky na prvn´ı pohled jako ponorka. To znamen´a, ” ˇze m´ a tvar, kter´ y si lid´e obvykle asociuj´ı s ponorkami. Vztlak zajiˇst’uje benz´ın. (Jako vztlakov´ a kapalina je pouˇzit benz´ın zejm´ena pro svou n´ızkou hustotu a t´emˇeˇr nulovou stlaˇcitelnost.) (M´ısto benz´ınu by mohla b´ yt pouˇzita pˇena typu Isofloat, ta byla ale po konsultaci s odborn´ıkem zavrhnuta.) D´elka je pˇribliˇznˇe dvacet metr˚ u. Pos´ adku tvoˇr´ı tˇri lid´e. V souvislosti s t´ım je tˇreba zajistit z´akladn´ı potˇreby, ponorka tedy m´ a jednoduch´ y z´ achod a prostory pro skladov´an´ı menˇs´ıho mnoˇzstv´ı j´ıdla a vody. Tlakov´ a sfera, ve kter´e bude um´ıstˇena pos´adka, poskytuje plnˇe funkˇcn´ı system podpory ˇzivota. Pˇr´ıtomen je CCR (closed-circuit rebreather) system podobn´ y tomu v modern´ıch vesm´ırn´ ych lod´ıch a skafandrech. Stˇeny sfery jsou v´ıce neˇz patn´ act centimetr˚ u siln´e, tlak by proto mˇely vydrˇzet. Pos´adka m´a moˇznost pozorovat sv´e okol´ı d´ıky mal´emu ok´enku z akrylick´eho skla. (Akrylick´e sklo je jedin´ a dostupn´ a pr˚ uhledn´ a l´ atka schopn´ a pˇrest´at extremn´ı tlak.) Vnˇejˇs´ı osvˇetlen´ı zajiˇst’uj´ı kˇremenn´e obloukov´e lampy, kter´e prokazatelnˇe vydrˇz´ı tlak v´ıce neˇz tis´ıc atmosf´er.
XX/4
11
V pˇr´ıpadˇe nedostatku jin´ ych moˇznost´ı m˚ uˇze b´ yt komunikace realizov´ana pomoc´ı zaˇr´ızen´ı na bazi sonaru ˇci hydrofonu. Sbˇer vzork˚ u bude realizov´an pomoc´ı robotick´ ych paˇz´ı s napojen´ım nezbytn´ ych zaˇr´ızen´ı. D´ıky d˚ umysln´e konstrukci jim pr´ ace pod velik´ ym tlakem nedˇel´ a probl´em. Ponorka m´a dostatek u ´loˇzn´eho prostoru. Energii dod´ avaj´ı baterie. Velk´e elektromagnety udrˇzuj´ı na m´ıstˇe z´atˇeˇz v podobˇe deseti tun magnetick´ ych ˇzelezn´ ych ˇc´ ast´ı. V pˇr´ıpadˇe selh´an´ı bateri´ı se tedy ponorka automaticky vynoˇr´ı na povrch. Pˇredpokl´ adan´ a d´elka jedn´e mise je asi deset hodin. Pr˚ ubˇeh mise ˇr´ıd´ı kapit´an, kter´ y se ˇr´ıd´ı instrukcemi, kter´e mu zadala povˇeˇren´ a osoba. Pos´adka bude vybr´ana na z´ akladˇe pˇredem stanoven´ ych kriteri´ı ze skupiny uchazeˇc˚ u soustˇredˇen´e v Praze. Pˇresn´ y term´ın prvn´ıho sestupu ponorky zat´ım nebyl specifikov´an. Pozn´ amky redakce: 1. Zaj´ımalo by n´ as, jak´y pˇresnˇe tvar si lid´e asociuj´ı s ponorkami a proˇc? Je tento tvar skuteˇcnˇe pro ponorku nejvhodnˇejˇs´ı? Jak´e parametry mus´ı splˇ novat? 2. Jak by fungovalo uˇzit´ı vztlakov´e kapaliny? V jak´e ˇca ´sti ponorky by byla um´ıstˇena? A kolik by j´ı bylo potˇreba? Pokud by tedy bylo pouˇzito toto ˇreˇsen´ı odlehˇcen´ı ponorky. . . 3. Je 20 m skuteˇcnˇe vhodn´y rozmˇer pro naˇsi ponorku? Proved’te odhad, co vˇsechno se do n´ı mus´ı vej´ıt, kolik prostoru zabere samotn´ a konstrukce, . . . 4. Pokud bychom pˇrijali tˇr´ıˇclennou pos´ adku, co bude m´ıt kdo na starosti? Budou opravdu vˇsichni pˇrimˇeˇrenˇe vyt´ıˇzeni? 5. Jak vypad´ a z´ achod v ponorce? 6. Kolik j´ıdla a pit´ı bude pos´ adka na misi potˇrebovat? 7. Co vˇsechno zahrnuje podpora ˇzivota a jak je to zajiˇstˇeno? 8. Je 15 cm s´ıla stˇen opravdu adekv´ atn´ı? Jak´y je na dnˇe Mari´ ansk´eho pˇr´ıkopu tlak? Nepl´ytv´ ame materi´ alem? 9. Jak byste provedli zapojen´ı kˇremenn´ych obloukov´ych lamp do pl´ aˇstˇe ponorky? Jak budou chr´ anˇeny pˇred vlhkem? Jak bude vyˇreˇsen pˇr´ıvod energie? 10. Jak´y komunikaˇcn´ı protokol je vhodn´y pˇri pouˇzit´ı sonaru ˇci hydrofonu? Je to v˚ ubec na takovou vzd´ alenost (dno–hladina) moˇzn´e? 11. Jak m´ a vypadat robotick´ a paˇze, aby byla schopn´ a sb´ırat vzorky? Jak´ a to d˚ umysln´ a konstrukce jim umoˇzn´ı pracovat v obrovsk´ych tlac´ıch? 12. Kolik u ´loˇzn´eho prostoru ponorka potˇrebuje (a na co)? 13. Jak´e baterie jsou nejvhodnˇejˇs´ı pro takovou misi a proˇc? Kolik jich bude potˇreba? 14. Jak´e parametry mus´ı m´ıt elektromagnety, aby udrˇzely poˇzadovan´y objem kovu? Proˇc zrovna deset tun (autorka neuv´ ad´ı hmotnost ponorky)? Kolik energie z bateri´ı by tyto elektromagnety spotˇrebov´ avaly na udrˇzen´ı onoho z´ avaˇz´ı? 15. Co vˇse se mus´ı bˇehem mise stihnout a jak dlouho to bude trvat? Staˇc´ı
12 opravdu 10 hodin? Jak dlouho v˚ ubec trv´ a kles´ an´ı a stoup´ an´ı rozumnou rychlost´ı? 16. Jak´ a rychlost je rozumn´ a? 17. Podle jak´ych krit´eri´ı je vhodn´e vyb´ırat pos´ adku?
Pl´an mise
(3b)
Dominika Tanglov´a Pro misi na dno Mari´ ansk´eho pˇr´ıkopu je potˇreba ponorka, kter´a bude ˇcelit obrovsk´emu tlaku. Nejvhodnˇejˇs´ı materi´ al pro ponorku by byla slitina skla a polymeru – nˇeco jako nepr˚ ustˇreln´e sklo. Sklo by bylo uspoˇr´adan´e do dvou vrstev, pˇriˇcemˇz vnitˇrn´ı vrstva by byla vyztuˇzena nejm´enˇe 7 vzpˇerami uspoˇr´adan´ ymi do hvˇezdy. Veˇsker´e zaˇr´ızen´ı by bylo ukryto ve vnitˇrn´ı ˇc´asti ponorky, prostor mezi pl´ aˇsti by byl pouˇzit k naˇcerp´ an´ı vody a t´ım zat´ıˇzen´ı ponorky a vyrovn´an´ı vnitˇrn´ıho tlaku. Ve vnitˇrn´ı ˇc´ asti by bylo zaˇr´ızen´ı pro pˇretlak, kdy postupnˇe bude zvyˇsovat tlak uvnitˇr ponorky aby nedoˇslo k implozi. Pro pohon by byly pouˇzity elektromotory um´ıstˇen´e opˇet ve vnitˇrn´ı ˇc´ asti. Turb´ıny by byly um´ıstˇeny na vrchn´ı ˇc´asti pl´ aˇstˇe. Vˇsechny komponenty um´ıstˇen´e vnˇe ponorky by byly vyrobeny z odoln´e kalen´e oceli. Turb´ıny by se pouˇz´ıvaly pouze aˇz po sestupu a n´aslednˇe by dopomohly k vyzvednut´ı ponorky. Pro sestup by byla pouˇzita koule z betonu, kter´a by se na dnˇe oddˇelila a ponechala by se na dnˇe. Pro vzestup by byl pouˇzit zabudovan´ y pˇretlakov´ y ventil s nepropustnou vrstvou. Kdyˇz by byl vnitˇrn´ı tlak vyˇsˇs´ı neˇz vnˇejˇs´ı, drˇzel by ventil pevnˇe na sv´em m´ıstˇe, v pˇr´ıpadˇe, ˇze by venku byl tlak vˇetˇs´ı, ventil by se uvolnil a tlaky by se vyrovnaly.5 Ponorka by byla plnˇe robotick´a, ovl´ adan´ a na d´ alkov´e ovl´ ad´ an´ı. Pro zes´ılen´ı sign´ alu by byly v rozestupech um´ıstˇen´e zesilovaˇce, kter´e by pˇrepos´ılaly sign´ aly. Pro sledov´an´ı okol´ı by byly pouˇzity kamery um´ıstˇen´e v trupu ponorky, jejich obraz by nebyl kv˚ uli vodˇe pˇr´ıliˇs ostr´ y, avˇsak pro pozorov´ an´ı dˇej˚ u a orientaci by to staˇcilo. Sbˇer vzork˚ u by zajiˇst’ovaly robotick´e paˇze, vzorky se budou ukl´ adat do vak˚ u pˇridˇelan´ ych na povrchu ponorky. Doba trv´ an´ı mise z´ aleˇz´ı na v´ ykonnosti akumul´ator˚ u. Pˇri dobr´e v´ ykonnosti by doba pobytu ponorky na dnˇe mohla b´ yt i okolo 2 dn˚ u. Cesta zp´atky by mˇela trvat nejm´enˇe den, aby se postupnˇe vyrovn´ avaly tlaky a nedoˇslo k poˇskozen´ı ponorky, to stejn´e plat´ı i pro cestu dol˚ u. Ponorka bude vybavena GPS pro pozdˇejˇs´ı nalezen´ı a vytaˇzen´ı z vody. Velikost vnitˇrn´ıho pl´ aˇstˇe by se mohla pohybovat okolo 2–3 metr˚ u v pr˚ umˇeru a vnˇejˇs´ı pr˚ umˇer kolem 2,5–3,5 metru. Pr˚ ubˇeh mise: 1. 2. 3. 4. 5 To
Spuˇstˇen´ı zesilovaˇc˚ u a vys´ılaˇc˚ u. Spuˇstˇen´ı z´ avaˇz´ı a ponorky do vody. Pomal´e tlakov´ an´ı ponorky. Sestup na dno. Odpojen´ı z´ avaˇz´ı. bylo pˇredpokl´ ad´ ame myˇsleno opaˇ cnˇ e.
XX/4 5. 6. 7. 8. 9. 10. 11.
13
Zkoum´ an´ı dna, odeb´ır´ an´ı vzork˚ u. Odlehˇcen´ı ponorky, pomal´ y vzestup. Vyrovn´ av´ an´ı tlaku pomoc´ı ventilu. Naveden´ı ponorky na souˇradnice vyzvednut´ı. Vyzvednut´ı ponorky. Zajiˇstˇen´ı vzork˚ u. Konec mise.
Pozn´ amky redakce: 1. Jak´y konkr´etnˇe kompozit skla a polymeru je vhodn´y pro stavbu ponorky, nebo aspoˇ n ok´ynek? (Slitina se tomu neˇr´ık´ a.) 2. Je skuteˇcnˇe vhodn´ a topologie v´yztuh ˇctrn´ actic´ıp´ a hvˇezda? Vymysl´ıte lepˇs´ı? 3. Zjevnˇe m´ a m´ıt ponorka v´ıce pl´ aˇst’˚ u. . . Jak mus´ı b´yt jednotliv´e pl´ aˇstˇe siln´e? Jak velk´ a m´ a b´yt mezera mezi nimi, aby mˇela dostateˇcnou z´ atˇeˇz, pokud je mezi nˇe naˇcerp´ ana voda? Jak siln´ a ˇcerpadla potˇrebujeme? 4. Jak funguje pˇretlakov´e zaˇr´ızen´ı? 5. Proˇc je vhodn´e pouˇz´ıt na vnˇejˇs´ı komponenty kalenou ocel? Proˇc ne tˇreba dural, karbon, litinu. . . 6. Jak´y v´ykon turb´ın motor˚ u potˇrebujeme k vyzdviˇzen´ı ponorky ze dna? 7. Jak velkou betonovou kouli je tˇreba uˇz´ıt jako z´ atˇeˇz, aby kles´ an´ı prob´ıhalo rozumnou rychlost´ı? Kdy pˇresnˇe je vhodn´e ji oddˇelit? 8. Zd´ a se, ˇze v ˇcl´ anku byla myˇslena r´ adiov´ a komunikace. Jak daleko od sebe mus´ı b´yt zesilovaˇce, aby byl sign´ al dostateˇcn´y? Jak´ a bude prodleva zp˚ usoben´ a takov´ymto pˇrenosem sign´ alu? 9. Proˇc je (anebo nen´ı?) obraz kamer ve vodˇe neostr´y? 10. Z jak´eho materi´ alu by mˇely b´yt vaky na vzorky? Jak by mˇely b´yt pˇrichyceny k ponorce? Budeme vˇsechno sb´ırat do nˇekolika vak˚ u, nebo budeme vzorky separovat? 11. Jak dlouho vydrˇz´ı ponorka v provozu a kolik jak´ych zdroj˚ u je na to potˇreba? Je odhad 2 dny re´ aln´y? 12. Pouˇzit´ı GPS je dobr´y n´ apad, jako pojistka. . . Je ale pravdˇepodobn´e, ˇze ji budeme potˇrebovat? Zuzka
T´ ema 5 – Sd´ılen´ı tajemstv´ı K t´ematu pˇriˇsly hned ˇctyˇri zaj´ımav´e pˇr´ıspˇevky. Kaˇzd´ y z autor˚ u ke sd´ılen´ı tajemstv´ı pˇristoupil trochu jinak. Doc.MM Mark´eta Cal´abkov´a pracuje s virtu´aln´ımi z´ amky a neˇreˇs´ı jejich pˇresnou implementaci. Naopak Dr.MM Matej Lieskovsk´ y a Mgr.MM Dominik Krasula navrhuj´ı detailnˇe popsan´a sch´emata. Prvn´ı se rozˇ ınskou zbytkovou vˇetu, druh´ hodl vyuˇz´ıt C´ y rozklady na prvoˇc´ısla. Aˇc by se tyto
14 pˇr´ıstupy mohly zd´ at podobn´e, mnoho spoleˇcn´eho v jejich pˇr´ıpadˇe nemaj´ı. Posledn´ı pˇrisp´ıvaj´ıc´ı Bc.MM Aneta Lesn´ a navrhuje vyuˇz´ıt velk´a prvoˇc´ısla, sv˚ uj n´avrh ale poˇr´ adnˇe nespecifikuje. Doc.MM Mark´eta Cal´ abkov´ a a Bc.MM Aneta Lesn´ a se zab´ yvaj´ı tak´e dalˇs´ımi aplikacemi pro sd´ılen´ı tajemstv´ı. Aplikace navrhovan´e Mark´etou si m˚ uˇzete pˇreˇc´ıst v jej´ım ˇcl´ anku, kter´ y n´ıˇze otiskujeme. Aneta navrhuje: Dalˇs´ı moˇznost´ı vyuˇzit´ı ” takov´eho tajemstv´ı by mohlo b´ yt spoleˇcenstv´ı, kde ke spuˇstˇen´ı jist´eho zaˇr´ızen´ı staˇc´ı urˇcit´ y poˇcet hlas˚ u. Pokud sv´e ˇc´ıslo poskytne dostateˇcn´ y poˇcet lid´ı, mˇely by staˇcit ke spuˇstˇen´ı zaˇr´ızen´ı. Pokud rozvinu pˇr´ıklad s bankou, dok´aˇzu si dobˇre pˇredstavit trezor, kter´ y vlastn´ı skupina lid´ı a kter´ y se otevˇre, pouze pokud dostatek z nich (pˇr´ıpadnˇe vˇsichni) ˇc´ıslo poskytne.“ Vzhledem k rozd´ıln´ ym pˇr´ıstup˚ um pˇrispˇevatel˚ u otiskuje n´ıˇze hned tˇri ˇcl´anky. Nˇekter´e z nich pro u ´sporu m´ısta jen ve zkr´ acen´e podobˇe. Jejich plnou verzi najdete na naˇsem webu.
A co d´ale? Jeˇstˇe neˇz dojde na pˇr´ıspˇevky, m´ am nˇekolik tip˚ u, ˇc´ım se v r´amci t´ematu nad´ale zab´ yvat. Urˇcitˇe lze vym´ yˇslet dalˇs´ı a dokonalejˇs´ı sch´emata, neˇz ta navrhovan´a. Nav´ıc i samotn´e pˇr´ıspˇevky jeˇstˇe nech´ avaj´ı trochu voln´eho prostoru na vylepˇsen´ı, pod´ıvejte se na pozn´ amky redakce pod kaˇzd´ ym z nich. Zkusme si ale pˇredstavit u ´plnˇe novou situaci pro sd´ılen´ı tajemstv´ı. Chtˇeli bychom si zahr´ at po telefonu hru k´ amen, n˚ uˇzky, pap´ır. Jak to udˇelat? Potˇrebovali bychom kamar´ adovi na druh´e stranˇe nejdˇr´ıv sdˇelit nˇejak´ y n´aˇs z´avazek, ze kter´eho by on nepoznal, jak´ y symbol chceme d´ at. Pak ho nechat, at’ on n´am svou volbu prozrad´ı a n´ aslednˇe mu poslat nˇejak´ y kl´ıˇc“, pomoc´ı kter´eho rozˇsifruje n´aˇs z´avazek. ” Pˇritom mus´ı b´ yt zajiˇstˇeno, abychom nemohli podv´ adˇet. Tedy k z´avazku nesm´ıme umˇet naj´ıt kl´ıˇc“ vedouc´ı k r˚ uzn´ ym symbol˚ um. ” Na prvn´ı pohled to moˇzn´ a vypad´ a neˇreˇsitelnˇe, ale ˇreˇsen´ı existuje a kupodivu nen´ı aˇz tak sloˇzit´e. Mimochodem, pro sch´emata zaloˇzen´a na podobn´em principu existuj´ı i vˇselijak´ a re´ aln´ a uplatnˇen´ı. Napadnou v´ as nˇejak´a?
O kl´ıˇc´ıch teoreticky
(9b)
Doc.MM Mark´eta Cal´abkov´a Nejdˇr´ıve vyˇreˇs´ım u ´lohu pro n osob, z nichˇz m´ a tajemstv´ı zn´at libovoln´ ych n − 1, ale uˇz ne n − 2. Radˇsi si to budu pˇredstavovat, ˇze ty osoby maj´ı urˇcit´ y poˇcet r˚ uzn´ ych typ˚ u kl´ıˇc˚ u a jedn´ a se o dveˇre s urˇcit´ ym poˇctem z´amk˚ u. Tedy vezmeme si nˇejakou skupinu o n − 2 ˇclenech. Ta urˇcitˇe tajemstv´ı nezn´a, tedy nem´a vˇsechny druhy kl´ıˇc˚ u. Potom z p˚ uvodn´ıch n lid´ı po odebr´ an´ı tˇechto n − 2 osob zbudou 2 osoby, z nichˇz kdyˇz kteroukoliv pˇrid´ ame do naˇs´ı skupiny o n−2 ˇclenech, vytvoˇr´ıme autorizovanou skupinu. Tedy tyto dvˇe osoby mus´ı m´ıt aspoˇ n jeden spoleˇcn´ y kl´ıˇc, kter´ y nikdo z vybran´ ych n − 2 osob nem´ a a kter´ y je potˇreba k otevˇren´ı dveˇr´ı. Ke stejn´emu z´ avˇeru se dostaneme, kdyˇz si vybereme jakoukoliv jinou (n − 2)-tici lid´ı,
XX/4
15
pˇriˇcemˇ zbylou dvojici bude dan´ y kl´ıˇc unik´atn´ı. Takˇze m´ame nejm´enˇe kaˇzdou z pro n(n−1) n n = = z´ a mk˚ u , tedy celkem nejm´enˇe n(n − 1) kl´ıˇc˚ u, tedy kaˇzd´a 2 n−2 2 osoba m´ a n − 1 kl´ıˇc˚ u u sebe, aby tento syst´em fungoval. Takˇze pro zadan´ ych 7 osob by Korunn´ı komora mˇela m´ıt 21 r˚ uzn´ ych z´ amk˚ u a kaˇzd´a z povˇeˇren´ ych osob by mˇela m´ıt 6 kl´ıˇc˚ u. Funguje to, protoˇze kdyˇz si ted’ vyberu n − 1 lid´ı, maj´ı vˇsechny kl´ıˇce (protoˇze zbyl jeden a ten m´ a kaˇzd´ y sv˚ uj kl´ıˇc spoleˇcn´ y s nˇejakou jinou osobou), ale pro n − 2 lid´ı mi zbude skupina o dvou lidech, kter´a m´a podle sch´ematu sv˚ uj unik´ atn´ı kl´ıˇc. Kdyˇz uˇz v´ım, jak se to poˇc´ıt´ a, m˚ uˇzu naj´ıt sch´ema pro obecn´e k. Vyberu si skupinu o k − 1 lidech, kter´ a podle zad´ an´ı neum´ı dveˇre otevˇr´ıt, takˇze mi z p˚ uvodn´ıch n zbude n − k + 1 lid´ı. Stejnou u ´vahou jako pˇredt´ım zjist´ım, ˇze tyto osoby maj´ ı n n sv˚ uj spoleˇcn´ y unik´ atn´ı kl´ıˇc, tedy typ˚ u kl´ıˇc˚ u (ˇcili z´ amk˚ u) bude k−1 = n−k+1 , n tedy celkem kl´ıˇc˚ u bude n−k+1 · (n − k + 1), takˇze kaˇzd´a osoba bude vlastnit n (n−k+1 )·(n−k+1) n−1 = n−k kl´ıˇc˚ u. Zase si m˚ uˇzeme zkusit, ˇze to bude fungovat. n Prozat´ım jsem ˇreˇsila situaci pro zcela rovnocenn´e osoby, coˇz neplat´ı pro uveden´eho kr´ ale se tˇremi vojev˚ udci. Tak. . . vyberu si jedin´eho kr´ale, kter´ y neum´ı dveˇre s´ am otevˇr´ıt, a zbudou tˇri vojev˚ udci, z nichˇz kdyˇz jak´ehokoliv pˇrid´ame ke kr´ ali, otevˇrou to. Tedy vˇsichni tˇri vojev˚ udci mus´ı m´ıt stejn´ y unik´atn´ı typ kl´ıˇce. D´ ale si vyberu dva vojev˚ udce. K nim kdyˇz pˇrid´ am zb´ yvaj´ıc´ıho vojev˚ udce, otevˇrou dveˇre, ale bez nˇej ne. Tedy kaˇzd´ y vojev˚ udce mus´ı m´ıt aspoˇ n jeden kl´ıˇc, kter´ y ostatn´ı vojev˚ udci nemaj´ı, ale kr´ al m´ıt m˚ uˇze. Aby ale dveˇre mohli otevˇr´ıt kr´al s jedn´ım vojev˚ udcem, mus´ı m´ıt kr´ al vˇsechny kl´ıˇce, kter´e vojev˚ udci chybˇej´ı, tedy kl´ıˇce vˇsech ostatn´ıch vojev˚ udc˚ u bez toho, kter´ y maj´ı jenom vojev˚ udci. Takˇze kr´al m´ a kl´ıˇce vˇsech vojev˚ udc˚ u kromˇe toho, kter´ y je vˇsem tˇrem vojev˚ udc˚ um spoleˇcn´ y. Bude lepˇs´ı si to nˇejak oznaˇcit. Takˇze si vojev˚ udce oznaˇc´ım V1 , V2 a V3 , kr´ale K. Kl´ıˇc, kter´ y m´ a V1 a ostatn´ı vojev˚ udci ne, bude v1 . Obdobnˇe zadefinuji v2 a v3 . Kl´ıˇc, kter´ y je vˇsem vojev˚ udc˚ um spoleˇcn´ y, ale kr´ al ho nem´a, oznaˇc´ım v. Takˇze V1 bude m´ıt kl´ıˇce v1 a v, V2 kl´ıˇce v2 a v, V3 kl´ıˇce v3 a v a koneˇcnˇe K bude m´ıt kl´ıˇce v1 , v2 a v3 . M´ ame ˇctyˇri z´ amky: v1 , v2 , v3 a v. Tohle sch´ema funguje. Praktick´e aplikace uˇz byly pops´ any v zad´ an´ı, tak tˇreba jeˇstˇe: kdyby mˇelo nˇekolik lid´ı sd´ılen´ y poˇc´ıtaˇc, aby heslo nemohl zmˇenit jen jeden, ale v´ıc – zaheslo” van´e heslo“ – dost ˇs´ılen´ y n´ apad. Ale to je zase situace peer-to-peer, ta nen´ı tak zaj´ımav´ a a ta je tu nav´ıc popsan´ a. A nebo kdyˇz m´ame firmu, kter´a je z r˚ uzn´ ych ˇc´ ast´ı vlastnˇena akcion´ aˇri, abychom v tom nemˇeli nepoˇr´adek (kdyˇz m´a firma akcie na burze), tak jim firmu pomˇerovˇe pˇrerozdˇel´ıme aˇz od urˇcit´eho poˇctu vlastnˇen´ ych akci´ı (tˇreba jako volby do poslaneck´e snˇemovny, tam taky nepostoup´ı strany, co maj´ı m´enˇe jak 5 % hlas˚ u a zbyl´e si kˇresla pˇrerozdˇel´ı podle pomˇeru z´ıskan´ ych hlas˚ u). Tak by tˇreba mohlo j´ıt zaheslovat u ´ˇcet t´e firmy tak, aby s n´ım mohli manipulovat pouze akcion´ aˇri, co vlastn´ı v souˇctu v´ıc jak 50 % firmy. Pˇredpokl´ad´am, ˇze kaˇzd´ y investor vlastn´ı celoˇc´ıseln´ y poˇcet akci´ı. Tohle sch´ema jsem uˇz popsala u kr´ ale a tˇr´ı vojev˚ udc˚ u, kde si to taky m˚ uˇzu pˇredstavit tak, ˇze kr´al m´a tˇri akcie a vojev˚ udci dvˇe. Mohl tam b´ yt tˇreba jeˇstˇe princ, kter´ y jakoby vlastnil jen jednu
16 ˇ ım akcii, ale nic tam nemˇenil, takˇze se s n´ım nemuselo poˇc´ıtat. Takˇze podobnˇe. C´ v´ıc akci´ı vlastn´ık m´ a, t´ım v´ıc kl´ıˇc˚ u dostane. Kaˇzd´ a skupina, kter´a m´a v souˇctu v´ıce neˇz polovinu poˇctu akci´ı povˇeˇren´ ych akcion´ aˇr˚ u, ale nem´a ˇz´adnou takovou podskupinu, m´ a sv˚ uj unik´ atn´ı kl´ıˇc. Pˇriˇcemˇz akcion´ aˇri, kteˇr´ı nic nemohou ovlivnit (respektive nepˇrehoupnou ˇz´ adnou skupinu z podpoloviˇcn´ı do nadpoloviˇcn´ı) budou z rozdˇelov´ an´ı kl´ıˇc˚ u vylouˇceni. Takhle by to mˇelo b´ yt funkˇcn´ı. ˇ anek se zab´yv´ Pozn´ amka redakce: Cl´ a teoretick´ym rozborem probl´emu, coˇz nen´ı v˚ ubec na ˇskodu. Jak by se ale takov´y z´ amek dal realizovat prakticky napˇr´ıklad v poˇc´ıtaˇci?
O vyuˇzit´ı prvoˇc´ısel pro sd´ılen´ı tajemstv´ı
(9b)
Mgr.MM Dominik Krasula Zvolit jako kl´ıˇc konkr´etn´ı ˇc´ıslo nen´ı dobr´ y n´ apad. Lepˇs´ı by bylo nastavit z´amek tak, aby se otevˇrel, pokud mu zadan´e ˇc´ıslo splˇ nuje nˇejakou vlastnost/soubor vlastnost´ı nebo pr´ avˇe naopak se jej dan´ a vlastnost net´ yk´a. Kdyˇz se to vymysl´ı chytˇre, nemusej´ı ani vlastn´ıci kl´ıˇc˚ u zn´ at vlastnosti, jenˇz z´ amek zkoum´a. Pro zaˇc´ atek je tedy dobr´e zvolit, jak´e vlastnosti u ˇc´ısla budeme zkoumat. Jak´e podm´ınky mus´ı splˇ novat. Tento ˇcl´ anek se bude zab´ yvat myˇslenkou v´ ybˇeru ˇc´ısla podle toho, zda-li m´ a dan´e prvoˇcinitele, hodnoty z´ıskan´e z kl´ıˇc˚ u se n´asob´ı. Moˇznost´ı je urˇcitˇe v´ıce. M´ ame-li n osob, tak kaˇzd´ a bude m´ıt ve sv´em ˇc´ısle n − 1 r˚ uzn´ ych prvoˇc´ısel kr´at nˇejak´e matouc´ı bezpeˇcnostn´ı hodnoty (ty nebudu pro jednoduchost v´ ykladu br´at v potaz, prostˇe osoba, co m´ a kl´ıˇc 5 · 3, nebude m´ıt ˇc´ıslo 15, ale tˇreba 345). Kaˇzd´a osoba bude tedy m´ıt vˇsechna ˇc´ısla z n-ˇc´ıseln´eho bloku, vyjma jednoho, u kaˇzd´eho to bude jin´e. Pokud z´ amek nastav´ıme tak, ˇze kaˇzd´e prvoˇc´ıslo mus´ı b´ yt ve v´ ysledn´em ˇc´ısle (n − 1)-kr´ at, musej´ı se sej´ıt vˇsichni, kdyˇz (n − 2), staˇc´ı, kdyˇz se sejde libovoln´ ych n − 2 osob a tak d´ ale. Pˇr´ıklad: M´ ame tˇri osoby, prvn´ı m´ a kl´ıˇc 2 · 3, druh´a 3 · 5, tˇret´ı 2 · 5, kl´ıˇc se otevˇre, jen kdyˇz dostane n´ asobek 2 · 3 · 5 – musej´ı se sej´ıt alespoˇ n dva, je jedno jac´ı. Tento princip umoˇzn ˇuje z´ amek nastavit tak, aby otevˇrel libovoln´emu, pˇredem dan´emu poˇctu zasvˇecen´ ych lid´ı. Jsou ale situace, kdy si nejsou vˇsichni rovni. Nˇekdo m´ a vˇetˇs´ı pravomoc, takˇze by mu mˇelo staˇcit m´enˇe dalˇs´ıch pomocn´ık˚ u k otevˇren´ı z´ amku. ˇ sme tˇreba pˇr´ıpad ze zad´an´ı. M´ame tˇri Nadkl´ıˇc“ by tedy mˇel lepˇs´ı ˇc´ıslo. Reˇ ” osoby a kr´ ale. Na tuto situaci se m˚ uˇze nahl´ıˇzet jako na situaci, kdy m´ame pˇet osob a otevˇr´ıt z´ amek mohou libovoln´e tˇri, pˇriˇcemˇz kr´al jsou pr´avˇe dvˇe bˇeˇzn´e osoby (m´ a dvˇe ˇc´ısla – tˇreba 3 · 2 a 5 · 2, kdeˇzto gener´al m´a pouze 3 · 2). Jdou t´ım ˇreˇsit i pˇrekvapivˇe sloˇzit´e pomˇery, se sloˇzit´ ym syst´emem, kdy postavy maj´ı nejr˚ uznˇejˇs´ı hodnosti:
XX/4
17
Postaˇcuj´ıc´ı kl´ıˇc maj´ı bud’ ˇctyˇri voj´ıni, tˇri plukovn´ıci, dva gener´alov´e nebo posloupnost voj´ın, plukovn´ık, gener´ al. Zprvu to vypad´a neˇreˇsitelnˇe, ale co kdybychom za nad-osobu prohl´ asili i voj´ına? Kdyby mˇel voj´ın dvˇe ˇc´ısla, mohli bychom plukovn´ıkovi d´ at tˇri, gener´ alovi ˇctyˇri, a poˇzadovat osm ˇc´ısel k otevˇren´ı. Potom syst´em opˇet funguje. A je celkem odoln´ y. D´ a se zocelovat – prostˇe jen bude nejniˇzˇs´ı osoba m´ıt v´ıce ˇc´ısel a pak si m˚ uˇzeme pˇeknˇe hr´ at s pomˇery. Co kdyˇz se ale kr´ al ob´ av´ a sv´ ych gener´ al˚ u. M˚ uˇze potom ˇr´ıci, ˇze nechce, aby spoj´ı-li se jeho gener´ alov´e, otevˇreli z´ amek. Gener´ alovi s deseti plukovn´ıky uˇz m˚ uˇze vˇeˇrit – bud’ je skuteˇcnˇe s n´ım anebo uˇz m´ a tolik lid´ı na sv´e stranˇe, ˇze je to stejnˇe jedno. Nab´ız´ı se pouˇz´ıt prostˇe syst´em, kdy dva gener´alov´e nemaj´ı dostateˇcnou hodnotu, aby z´ amek otevˇreli. Ovˇsem tento syst´em nemus´ı b´ yt funkˇcn´ı, dvˇema gener´ al˚ um prostˇe staˇc´ı pˇrekecat dva/tˇri plukovn´ıky a m˚ uˇzou z´amek v pohodˇe otevˇr´ıt. Jak tedy ˇreˇsit situaci, kdy nˇejak´ a podmnoˇzina konkr´etn´ıch lid´ı z´amek prostˇe nem˚ uˇze otevˇr´ıt? M˚ uˇzeme si tu tˇreba hr´ at s dˇelitelnost´ı. Tˇreba d´at gener´al˚ um do souˇcinu ˇc´ısla n · m, a nastavit z´ amek tak, ˇze dostane-li ˇc´ıslo dˇeliteln´e n2 · m2 tak se neotevˇre, ale dˇelitelnost ˇc´ıslem n · m mu nevad´ı. Tato metoda se d´a ˇsikovnˇe vyuˇz´ıt i pˇri ochranˇe pˇred ˇspiony. Vypustit nˇekolik ˇc´ısel se zak´ azanou hodnotou (tˇreba pr´avˇe hodnotou n2 · m2 ), takˇze je-li ve skupinˇe byt’ jen jedin´ y ˇspi´on, z´amek se neotevˇre. Pozn´ amka redakce: Zbytek ˇcl´ anku rozeb´ıraj´ıc´ı dalˇs´ı speci´ aln´ı pˇr´ıpady rozdˇelen´ı moci mezi r˚ uzn´e skupiny naleznete na naˇsem webu. Pozn´ amka redakce: Nev´yhodou zde nab´ızen´eho syst´emu je snadn´ a moˇznost podv´ adˇen´ı. Zakl´ adat bezpeˇcnost na nezn´ am´em principu ovˇeˇrov´ an´ı se za vhodn´e obvykle nepovaˇzuje. Staˇcilo by ale m´ısto mal´ych prvoˇc´ısel volit prvoˇc´ısla velk´ a a syst´em by mohl fungovat docela obstojnˇe. Faktorizovat velk´ a ˇc´ısla je totiˇz sloˇzit´y probl´em, na jehoˇz neˇreˇsitelnosti v re´ aln´em ˇcase je zaloˇzen napˇr´ıklad velmi popul´ arn´ı algoritmus RSA. Pˇresto i pˇri pouˇzit´ı velk´ych prvoˇc´ısel m´ a nab´ızen´y syst´em jednu potenci´ aln´ı slabinu. Napadne v´ as?
Sd´ılen´ı tajemstv´ı na ˇc´ınsk´y zp˚ usob
(10b)
Dr.MM Matej Lieskovsk´y Kl´ıˇc je pro potˇreby tohoto ˇcl´ anku definov´ an jako nˇejak´e pˇrirozen´e ˇc´ıslo (vˇcetnˇe nuly), kter´e je potˇreba zn´ at k z´ısk´ an´ı pˇr´ıstupu. C´ılem je nˇejak distribuovat kl´ıˇc nebo jeho ˇc´ asti mezi n lid´ı tak, aby libovoln´ ych k z nich umˇelo relativnˇe rychle kl´ıˇc urˇcit, ale aby libovoln´ ych k − 1 toho o kl´ıˇci vˇedˇelo co nejm´enˇe. Bude n´am staˇcit, aby urˇcen´ı kl´ıˇce pro k − 1 lid´ı bylo mnohem sloˇzitˇejˇs´ı neˇz pro k, absolutn´ı sloˇzitost um´ıme snadno nav´ yˇsit, zp˚ usob uvedu. Ve vˇsech pˇr´ıpadech je bezpeˇcnost proti u ´toku z vnˇejˇsku urˇcena poˇctem moˇzn´ ych kl´ıˇc˚ u. Bezpeˇcnost pro k − 1 budu urˇcovat jako poˇcet kl´ıˇc˚ u, ze kter´ ych budou muset tipovat.
18 Tady bych r´ ad upozornil na nˇeco, co vn´ım´ am jako chybu v zad´an´ı t´em´atka. Poˇzadavek na to, aby libovoln´ ych k − 1 lid´ı nevˇedˇelo o kl´ıˇci v˚ ubec nic, je podle mˇe ´ zbyteˇcn´ y. Uplnˇ e staˇc´ı, aby mˇelo k−1 lid´ı potˇrebu vyb´ırat z alespoˇ n dvou moˇznost´ı, naˇceˇz um´ıme bezpeˇcnost exponenci´ alnˇe zvyˇsovat pouˇzit´ım nˇekolika kl´ıˇc˚ u. Skupina k − 1 lid´ı na tom bude v´ yraznˇe l´epe neˇz vnˇejˇs´ı u ´toˇcn´ık, ale pokud na tom i tak budou zoufale ˇspatnˇe, tak n´ am to zrovna moc nevad´ı. Nejdˇr´ıve uv´ ad´ım nˇekolik specifick´ ych ˇreˇsen´ı pro dan´a k. Jsou implementaˇcnˇe jednoduˇsˇs´ı, neˇz obecn´e ˇreˇsen´ı, kter´e uv´ ad´ım na konci t´eto pr´ace. ˇ sen´ı pro k = 1, n, 2 a n − 1 z prostorov´ych d˚ Pozn´ amka redakce: Reˇ uvod˚ u vynech´ av´ ame. Najdete je na webu. N´ asleduje obecn´e ˇreˇsen´ı pro libovoln´e k a n. ˇ ınsk´ C´ a vˇeta o zbytc´ıch ˇr´ık´ a, ˇze zn´ ame-li zbytky po dˇelen´ı nˇejak´eho ˇc´ısla n nˇekolika vz´ ajemnˇe nesoudˇeln´ ymi ˇc´ısly p1 , p2 , p3 , . . . , pn , dok´aˇzeme ˇc´ıslo n jednoznaˇcnˇe urˇcit pr´ avˇe, kdyˇz je menˇs´ı neˇz souˇcin p1 · p2 · p3 · · · · · pn . Kaˇzd´ y z n lid´ı bude m´ıt pˇridˇeleno jedno z n vz´ajemnˇe nesoudˇeln´ ych ˇc´ısel a n´ aslednˇe se dozv´ı zbytek po vydˇelen´ı kl´ıˇce t´ımto ˇc´ıslem. Kl´ıˇc se d´a urˇcit jako nejmenˇs´ı ˇc´ıslo, kter´e bude splˇ novat libovoln´ ych k zbytk˚ u. Jelikoˇz chceme, aby kl´ıˇc bylo moˇzn´e urˇcit z libovoln´ ych k zbytk˚ u, mus´ı kl´ıˇc b´ yt menˇs´ı, neˇz souˇcin k nejmenˇs´ıch pˇridˇelen´ ych ˇc´ısel. Souˇcasnˇe ale nesm´ı b´ yt kl´ıˇc urˇciteln´ y z k − 1 zbytk˚ u, mus´ı tedy b´ yt vˇetˇs´ı neˇz souˇcin k − 1 nejvˇetˇs´ıch pˇridˇelen´ ych ˇc´ısel. Obˇe podm´ınky dohromady s poˇzadavkem na vz´ajemnou nesoudˇelnost pˇridˇelen´ ych ˇc´ısel n´ am v´ yraznˇe komplikuje v´ ybˇer pˇridˇelen´ ych ˇc´ısel. D´a se uk´ azat, ˇze nejtˇeˇzˇs´ı je toto pˇridˇelov´ an´ı zvl´ adnout pro k = dn/2e. M´enˇe pˇresn´a, ale jednoduˇsˇs´ı postaˇcuj´ıc´ı podm´ınka je, ˇze nejvˇetˇs´ı pˇridˇelen´e ˇc´ıslo mus´ı b´ yt menˇs´ı, neˇz to nejmenˇs´ı na k/(k − 1). Pokud budeme pˇridˇelovat prvoˇc´ısla, tak podle 2 Bertrandova postul´ atu n´ am budou staˇcit“ ˇc´ısla ˇra´dovˇe 2n . Je to sice opravdu ” hodnˇe, ale pro menˇs´ı mnoˇzstv´ı lid´ı to bude fungovat. Lepˇs´ı nal´ez´an´ı vz´ajemnˇe nesoudˇeln´ ych ˇc´ısel je rozhodnˇe otevˇren´ y probl´em k dalˇs´ımu v´ yzkumu. Touto metodou lze ˇreˇsit i u ´lohu s kr´ alem a vojev˚ udci. Snadno nahl´edneme, ˇze kr´ al se chov´ a jako dva vojev˚ udci. Tud´ıˇz vygenerujeme zbytky pro (n, k) = (5, 3), kaˇzd´ y vojev˚ udce dostane jeden zbytek a kr´ al dva. Obdobnˇe um´ıme vyˇreˇsit libovoln´ y pˇr´ıpad, kter´ y um´ıme pˇrev´est na probl´em s lidmi, jejichˇz v´aha“ pˇri ” otev´ır´ an´ı je racion´ aln´ım ˇc´ıslem. Domn´ıv´ am se, ˇze implementace sd´ılen´ı tajemstv´ı pomoc´ı ˇc´ınsk´e zbytkov´e vˇety je dostateˇcnˇe siln´ a na to, aby bylo moˇzn´e opˇet zobecnit zad´an´ı. M´ame n lid´ı a seznam vˇsech minim´ aln´ıch autorizovan´ ych skupin, kdy pˇr´ıstup m´a dostat (pouze) libovoln´ a skupina, kter´ a obsahuje alespoˇ n jednu celou minim´aln´ı autorizovanou skupinu. Zat´ım nev´ım, jak pˇresnˇe tento algoritmus implementovat, ale bude postaven na principu pouˇz´ıv´ an´ı ˇc´ısel, kter´ a jsou vz´ ajemnˇe dle potˇreby soudˇeln´a. Pozn´ amka redakce: Jestli fakt, ˇze neautorizovan´ a skupina drˇzitel˚ u kl´ıˇce o tomto kl´ıˇci m˚ uˇze z´ıskat nˇejakou alespoˇ n kusou informaci, je na z´ avadu, je sp´ıˇse filosofickou ot´ azkou. Pochopitelnˇe i pokud ˇca ´st informace z´ısk´ a, m˚ uˇze b´yt sch´ema jeˇstˇe poˇr´ ad dostateˇcnˇe bezpeˇcn´e. Takˇze t´ımto smˇerem m´ a smysl zad´ an´ı rozˇs´ıˇrit. Na druhou stranu takov´e sch´ema uˇz alespoˇ n podle mˇe nen´ı tak hezk´e.
XX/4
19
ˇ anek docela sloˇzitˇe rozeb´ır´ Cl´ a problematiku moˇzn´e velikosti hledan´eho kl´ıˇce. ˇ ım v´ıce moˇznost´ı pro kl´ıˇc buToto t´ema by urˇcitˇe st´ alo za to jeˇstˇe prozkoumat. C´ deme m´ıt, t´ım bude sch´ema bezpeˇcnˇejˇs´ı. Nehroz´ı, ˇze bude moˇznost´ı na kl´ıˇc tˇreba tak m´ alo, ˇze by bylo moˇzn´e je vyzkouˇset hrubou silou jednu po druh´e? Na zaslan´em pˇr´ıspˇevku oceˇ nuji, ˇze jako jedin´y z doˇsl´ych mˇel skuteˇcnˇe podobu ˇcl´ anku vˇcetnˇe nadpisu. I toto se prom´ıtlo do jeho bodov´eho hodnocen´ı. Kuba
V´ysledkov´a listina 2. ˇc´ısla Poˇ r.
Jm´ eno
1. 2. 3. 4. 5. 6. 7.–8.
MM
9. 10. 11.–12. 13. 14. 15.–18.
19.–20. 21. 22.–25.
26.–29.
Mgr. D. Krasula Doc.MM M. Cal´ abkov´ a Dr.MM M. Lieskovsk´ y Mgr.MM P. Souˇcek Mgr.MM L. Studen´ a ˇ ’astn´ Doc.MM A. St a Mgr.MM O. Hollmann Mgr.MM V. Rozhoˇ n Dr.MM P. N´ acovsk´ y Bc.MM A. K. Lesna Bc.MM V. Bartovic Dr.MM J. Kuˇsn´ır Bc.MM J. Havelka Bc.MM J. V´ aclavek V. Konˇcick´ y T. Paliesek D. Tanglov´ a MM Bc. A. Teichmann Dr.MM F. Homza J. Liˇska Mgr.MM L. Langerov´ a J. Noskov´ a ˇ A. Sedov´ a Bc.MM V. V´ aclav´ık MM Dr. P. Vincena R. Hlavinka E. Klimentov´ a
R. 1. 3. 4. 2. 4. 4. 4. 3. 3. 1. 2. 3. 1. 2. 3. 2. 1. 4. 4. 2. 3. 4. 2. 4. 3. 2. 4.
P
−1
44 119 93 36 24 111 21 21 57 17 12 53 11 10 9 9 9 18 95 8 42 5 5 13 63 4 4
´ Ulohy P r1 r2 r3 r4 t3 t4 t5 0 8 3
2
3 3 3 3
2 2 2 1
2 2 0 0 3 3 3 2 0
1 0 0 0 2 1 2 0 0
4 0 1 4
3 0
1
1
1 3
2
2 2
2
2
0
2 0
3
2 1
3 0 2
1 0
9 9 10
2
0
2 0 2
3
17 16 10 7 8 8 4 0 7 9 1 4 5 4 9 2 3 0 5 3 0 0 0 4 2 0 4
P
1
44 36 26 25 24 22 21 21 20 17 12 12 11 10 9 9 9 9 8 8 6 5 5 5 5 4 4
20 Poˇ r.
Jm´ eno MM
30.–33.
34.–38.
Mgr. M. Poljak J. Stanovsk´ y D. Dimitrov Dr.MM A. Hruˇskov´ a K. Kol´ aˇr ˇ ara J. Skv´ Bc.MM J. Dittrich Bc.MM Z. Garˇcic Doc.MM J. Kadlec Mgr.MM V. Skoup´ y ˇ Bc.MM M. Safek
R. 2. 2. 3. 4. 2. 3. 2. 3. 3. 4. 3. 3. 1. 2. 4. 4.
−1
´ Ulohy P r1 r2 r3 r4 t3 t4 t5 0
38 4 3 59 6 6 14 12 100 44 14 12 1 33 16 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0
P
2
Bc.MM K. Ilievov´ a F. Zaj´ıc 41.–43. Mgr.MM J. Cerman 0 MM Bc. D. Mach´ aˇcov´ a M. M¨ uller P P Sloupeˇcek −1 jePsouˇcet vˇsech bod˚ u z´ıskan´ ych v naˇsem semin´ aˇri, 0 je souˇcet bod˚ u v aktu´ aln´ı s´erii a 1 souˇcet vˇsech bod˚ u v tomto roˇcn´ıku. Tituly uveden´e v pˇredchoz´ım textu slouˇz´ı pouze pro u ´ˇcely M&M 39.–40.
S obsahem ˇcasopisu M&M je moˇzn´e nakl´ adat dle licence Creative Commons Attribution 3.0. D´ılo sm´ıte ˇs´ıˇrit a upravovat. M´ ate povinnost uv´est autora. Autory text˚ u jsou, pokud nen´ı uvedeno jinak, organiz´ atoˇri M&M.
Adresa redakce: M&M, OVVP, UK MFF Ke Karlovu 3 121 16 Praha 2 E-mail:
[email protected] WWW: http://mam.mff.cuni.cz ˇ Casopis M&M je zastˇreˇsen Oddˇelen´ım pro vnˇejˇs´ı vztahy a propagaci Univerzity Karlovy, Matematicko-fyzik´ aln´ı fakulty a vyd´ av´ an za podpory stˇredoˇcesk´e poboˇcky Jednoty ˇcesk´ ych matematik˚ u a fyzik˚ u.
P
1
4 4 3 3 3 3 2 2 2 2 2 1 1 0 0 0
