4. série
Téma: Pøíbìhyzmenzy
Termínodeslání: 5.ledna2004
1.úloha (3body)
Vkopíhvokolímenzy¾ijespoustazvíøátek.Ka¾déznihmátøioblíbenáèísla.Li¹kymajísvé
prvníoblíbenéèíslodvojku,sovymajívprvníøadìrádytrojku,mazanékunymajínejoblíbenìj¹í
ètyøku,králíèipìtkuazajíèi¹estku,jelenivprvníøadìfandísedmièe,noriosmièeaméïové
devíte. Zvíøátkajsourùznobarevná. Hnìdázvíøátka majídruhéoblíbenéèíslodvanátku,bílá
jsouproètrnátku,èernábysivybralajakodruhéèíslo¹estnátkuaprozelenájedruhánejob-
líbenìj¹íosmnátka.Zvíøátkajsousamozøejmìirùznìvelká.Malázvíøátkamajítøetíoblíbené
èíslomaléèíslonula.Prùmìrnìvelkábyvolilaotrohuvìt¹ídesítku.Velkásivybírajíu¾elkem
velkoudvaítku.Aobrovskámajítøetínejoblíbenìj¹ísamozøejmìobrovskoupìtadvaítku.Jedno
zvíøátkoobèasnìkteré studentyvmenzetaktrohustra¹í. Jednou do nízabìhloapostra¹ilo
tím,¾esouèetjehooblíbenýhèíselje24.Jindyzasestra¹ilotím,¾ev¹ehnajehooblíbenáèísla
dávajístejnýzbytekpøidìlenítøemi.Kterézvíøátkoobèaspostra¹ístudenty?
2.úloha (3body)
Vmenzenashùzkáhorganizátorùmámepìknýzvyk.Kdy¾sesejdeme,posadímesedokruhu
azaènemetleskat.Netleskámealejentak.Tleskánímusímíttensprávnýrytmusaøád.Nejdøív
tleskne Mihal.Naka¾doudal¹ídobutlesknouti ajenti,jejih¾právìjedensousedna minu-
lou dobu tlesknul. Kdy¾ u¾nikdonetleská, shùzka mù¾e zaèít.Najedné shùze sese¹lo2 n
organizátorù.Mohlinìkdyzaèítshùzovat?
3.úloha (3body)
NajinéshùzesipotradiènímpozdravuMartinv¹imlzajímavénovinky,toti¾elápodlahaje
pokrytadla¾dièkamitypu"L"(vizobrázekna koni). David hneddodal,¾e jeto mopìkné,
proto¾e nejen menzu,ale rovnouelou rovinu lzepokrýt tìmitodla¾dièkamitak, ¾e ka¾dá je
pou¾itaprávìjednou.MáDavidspokrývánímrovinypravdu?
4.úloha (5bodù)
Mezitím,osiostatníorganizátoøido¹liproobèerstvení,Marekhlídalbundyahrálsisdrobeèky
nastole.Podaøilosemujeposkládatdozajímavéhoútvaru,kdyvokolíka¾déhodrobeèkujsou
právìtøijiné,kteréodnìjmajívzdálenost5m.Kolikmohlobýtdrobeèkù?
5.úloha (5bodù)
Jeliko¾jsou matfyzáilínípøeházet mezijednotlivýmimístnostmimenzy,vystavìlisiú¾asný
systém mikrotramvají.Mezi ka¾dými dvìma místnostmijezdí mikrotramvaj v právì jednom
smìru.Dinovizaèínávièenía¾zapùlhodiny,atakhonapadlo,¾evolnýèasmù¾evyplnittím,
¾esivyberenìjakouprvnímístnostapakseprojedemikrotramvajemipomenzetak,¾eka¾dou
místnostnav¹tívíprávìjednou(anebudemezimístnostmipøeházet).Doka¾te,¾etakovývýbìr
estováníseDinovimù¾epovést,a»u¾mikrotramvajejezdíjakkoliv.
6.úloha (5bodù)
Jednou sissebou na shùzku An¹a vzala velkédomino.V¹imlasi, ¾e její dominovékostièky
zakrývajíprávìdvìpolíèkatrohuzvlá¹tní¹ahovnie(2n + 1)krát(2n + 1),nakteréprávì
PavelsFrsemhráli¹ahy.Rozehraná¹ahovápartiejípøíli¹nezajímala,postupnìbralagurky
z¹ahovniea skládalananidominovékostièky.Nakone zaplnilaelou ¹ahovnii a¾na levé
dolnípolíèko.Honzasiv¹iml,¾esdominylzepo¹ahovniiposouvattak,¾eka¾dépolíèko,které
seodlevéhodolníholi¹ívobousouøadniíhosudéèíslo,mù¾ezùstatnezakryto.Napadloho,¾e
ikdybyAn¹aposkládaladominajinak(slevýmdolnímpolíèkemnezakrytým),budestáleplatit
jehopozorovánízpøedhozíhorozestavìní.PoraïteHonzovi,jakjehonápaddokázat.
7.úloha (5bodù)
Jídelnavmenzemáètverový pùdorysse¹ahovniovou podlahouon 2
políh.Vka¾démpoli
¹ahovnie je jedno místo k sezení. Ne v¾dy se obìd v menze podaøí uvaøit podle pøedstav
studentù. Jednou, kdy¾ byla menza plná, bylo pár porí dokone pøiotrávenýh salmonelou.
Navísepostupnìnakazovalidal¹ístudenti tak, ¾ekdykolivmìliaspoò dva sousedy(hranou,
nikolirohem)naka¾ené,nakazilisetaké.Koliknejménìmohlobýtotrávenýhporí,kdy¾víme,
¾esenakazilaelámenza?
8.úloha (5bodù)
Pomìrnìnedávno sevmenzeopravovaloosvìtlení.Elektrikáøinatahaliv¹ude pomenzedráty
(pøímky),nìkterédrátyseobèasprotínaly,ale¾ádnétøivjednombodì.Systémdrátùbylopravdu
velminepøehledný,míøilyodstropu kpodlaze,odpodlahykestìnám, od stìnkestìnám:::
Dokone¾ádnétøidrátynele¾elyvjednérovinì.Kolikdvojidrátùsenejvý¹emohloprotínat?
Øe¹ení 4. série
1.úloha
Vkopíhvokolímenzy¾ijespoustazvíøátek.Ka¾déznihmátøioblíbenáèísla.Li¹kymajísvé
prvníoblíbenéèíslodvojku,sovymajívprvníøadìrádytrojku,mazanékunymajínejoblíbenìj¹í
ètyøku,králíèipìtkuazajíèi¹estku,jelenivprvníøadìfandísedmièe,noriosmièeaméïové
devíte. Zvíøátkajsourùznobarevná. Hnìdázvíøátka majídruhéoblíbenéèíslodvanátku,bílá
jsouproètrnátku,èernábysivybralajakodruhéèíslo¹estnátkuaprozelenájedruhánejob-
líbenìj¹íosmnátka.Zvíøátkajsousamozøejmìirùznìvelká.Malázvíøátkamajítøetíoblíbené
èíslomaléèíslonula.Prùmìrnìvelkábyvolilaotrohuvìt¹ídesítku.Velkásivybírajíu¾elkem
velkoudvaítku.Aobrovskámajítøetínejoblíbenìj¹ísamozøejmìobrovskoupìtadvaítku.Jedno
zvíøátkoobèasnìkteré studentyvmenzetaktrohustra¹í. Jednou do nízabìhloapostra¹ilo
tím,¾esouèetjehooblíbenýhèíselje24.Jindyzasestra¹ilotím,¾ev¹ehnajehooblíbenáèísla
dávajístejnýzbytekpøidìlenítøemi.Kterézvíøátkoobèaspostra¹ístudenty?
Propøehlednostsije¹tìopi¹me,jakémù¾ebýtprvní,druhéatøetíoblíbenéèíslo.Prvnímù¾e
býtjednozèísel1,2,:::,9,druhé12,14,16,èi18atøetí0,10,20nebo25.Souèet prvního
a druhéhonejoblíbenìj¹íhoèísla jetedy alespoò 13,tedy tøetínejoblíbenìj¹íèíslo nemù¾ebýt
20ani25,jinakbyv¹ehnatøièísladávaladohromadyvíene¾ 24.Je-li10tøetínejoblíbenìj¹í
èíslona¹eho zvíøátka,potomjedinémo¾nédruhénejoblíbenìj¹íèíslodávajíístejnýzbytekpøi
dìlení tøemije16, dohromadydávají26,odkudplyne¾e souèetv¹ehtøíèíselnemù¾ebýt24,
tedy 10nemù¾e býttøetínejoblíbenìj¹íèíslo.Nyníu¾tedy víme,¾e sejedná omalé zvíøátko
(støetímoblíbenýmèíslem0).Prodruhéoblíbenéèíslo,má-lidávatstejnýzbytekjakonulapøi
dìlenítøemi,zbývá12nebo18.Bylo-libyto12,potomjevzhledemksouètu24iprvníèíslo12,
o¾nelze.Tedydruhéèísloje18ajednáseozelenézvíøátko.Odtudu¾plyne,¾eprvníèísloje6
(opìtsouèet24).Zvíøátko,kteréobèaspostra¹ístudentyvmenze,jetedymalýzelenýzajíèek.
Poznámkykdo¹lýmøe¹ením: Úlohanebylaobtí¾náanavíjsemjihodnotildostmírnì,proto
dostaladrtivávìt¹inaøe¹itelùplnýpoèetbodù.Cobyhv¹akhtìlzdùraznit,¾ehledanézvíøátko
nebylzají,èizaja,anizajaèik,ikdy¾tou¾jebli¾¹ískuteènosti,hledanézvíøátkobylZajíèek!
Ov¹empodstatnájeijehovelikostabarva,tojetoti¾plnáharakterizaezvíøátka,tak¾eúplná
správnáodpovìïje,¾estudentyobèaspostra¹íMalýZelenýZajíèek!
2.úloha
Vmenzenashùzkáhorganizátorùmámepìknýzvyk.Kdy¾sesejdeme,posadímesedokruhu
azaènemetleskat.Netleskámealejentak.Tleskánímusímíttensprávnýrytmusaøád.Nejdøív
tleskne Mihal.Naka¾doudal¹ídobutlesknouti ajenti,jejih¾právìjedensousedna minu-
lou dobu tlesknul. Kdy¾ u¾nikdonetleská, shùzka mù¾e zaèít.Najedné shùze sese¹lo2 n
organizátorù.Mohlinìkdyzaèítshùzovat?
Organizátoøisamozøejmì sedína obvodu kruhu, aby úloha dávala smysl (zatuto drobnou
nepøesnostseomlouváme).
Prozaèáteksiøeknìme,¾evzdálenostínìjakýhdvouorganizátorùPepyaTomá¹ebudeme
rozumìt men¹í z poètu organizátorù sedííh mezi Pepou a Tomá¹em po smìru hodinovýh
ruèièek zvìt¹eného ojedna apoètu organizátorùsedííhmeziPepoua Tomá¹emprotismìru
hodinovýhruèièekzvìt¹enéhoojedna.Tedynapøíkladdvasousedníorganizátoøimajívzdálenost
1,organizátoøisedíívkruhunaprotisobìmajívzdálenost2 n 1
.
1. doba 3. doba 5. doba 7. doba 9. doba
2. doba 4. doba 6. doba 8. doba
M ic h a l
Nakreslemesiobrázekvývojetleskání.Nax-ovouosuvyznaèujmeorganizátorytak,¾enìkam
vyznaèímeMihalaa napravoodMihala dávejmepostupnì jemunejbli¾¹íorganizátory proti
smìruhodinovýhruèièek,nalevoodMihaladávejmepostupnìjemunejbli¾¹íorganizátorypo
smìruhodinovýhruèièek.Nay-ovouosuznaèmedobu,nakterousetleská.Puntíkemvyznaème,
kdy¾nìjakýorganizátornanìjakou dobutleská.Naprvnímobrázkujsmeje¹tìnìjaképuntíky
spojiliúseèkami,abybylolépevidìt,jakýobrázekvzniká.
1. doba 2 k + 1
. doba 2 k+1 + 1
. doba
2 k . doba 2 k+1 . doba
M ic h a l
T
T T
V¹imnìmesizajímavévlastnostiobrázku.Prokmalá(tj.men¹íne¾n 1,abyobrázeknespojil
svùjpravýalevýkonetím,¾ejenakru¾nii)oznaème"T"obrázek,kterývzniknetleskánímdo
2 k
.doby(vèetnì),potomtleskánímdo2 k +1
.dobyvzniknoudal¹ídvastejné(akorátposunuté)
obrázky.To fungujekvùlitomu,¾e sezahovává vlastnost, ¾ena 2 i
.dobu (pro ka¾dé i <n)
v¹ihniorganizátoøi,kteøímajívzdálenostodMihalalihouamen¹íne¾2 i
,tleskají(atedyna
(2 i
+1) .dobu(proi <n 1) tleskajíprávìtiorganizátoøi,kteøímajívzdálenostodMihala
2 i
.Potomu¾jemy¹lenkaøe¹eníjasná,na2 n 1
dobu budoutleskatv¹ihniorganizátoøi,kteøí
majílihouvzdálenostodMihala(tj.ka¾dýdruhýorganizátor),atedyna(2 n 1
+1).dobuu¾
nebudetleskatnikdo.
Právìjsmepopsalipropøehlednostzákladnímy¹lenku,nynízbývámy¹lenkupoøádnìdokázat.
PokudseTimy¹lenkazdádostateènìprùkaznáanehe¹setrápitsindexy,tøebaipoøádnýdùkaz
vynehej.
Budemedokazovatindukíabudemedokazovat trohusilnìj¹ítvrzení,abysenáminduke
lépeprovádìla.
Mìjmedánol2Nak<n 1.Tleská-linìjakýorganizátorDavidnal .dobu azároveòdo
vzdálenosti2 k +1
1odDavidanikdonal :dobunetleská,potomzorganizátorù,kteøímajíod
Davidavzdálenostmen¹írovnou2 k
,na(2 k
+l 1) .dobutleskajíprávìti,jejih¾vzdálenostod
Davidajelihá.
Prok=1jetvrzeníjasné.
Nadálepøedpokládejme,¾etvrzeníplatíprok=iadokazujmehoprok=i+1<n 1.
V¹ihniorganizátoøitleskajíínal :dobumajívzdálenostodDavidaaspoò2 i+2
1>2 i+1
1,
tedymù¾emepou¾ítindukènípøedpokladaztìhorganizátorù,kteøímajíodDavidavzdálenost
men¹íneborovnou2 i
,na(2 i
+l 1) .dobutleskajíprávìti,jejih¾vzdálenostodDavidajelihá.
Dálesiv¹imnìme,¾eorganizátoøi,jejih¾vzdálenostodDavidaje2 i
+1,na(2 i
+l 1) .dobu
netleskají,nebo»nal :dobubylajejihvzdálenostodnejbli¾¹íhotleskajííhoorganizátoravìt¹í
ne¾2 i
1(pøedpoklad,¾edovzdálenosti2 i+2
1odDavidanikdonetleská)azaka¾doudobu
senejbli¾¹ítleskajíímù¾epøiblí¾itnanejvý¹ o1(rozmyslisi).Toale znamenápodlepravidel
tleskání,¾ena(2 i
+1) .dobutleskajíztìhorganizátorù,omajíodDavidavzdálenostmen¹í
neborovnou2 i
,právìtidva(HonzaaPavel),kteøímajívzdálenostpøesnì2 i
.
l. doba 2 i + l
. doba 2 i+1 + l
. doba
2 i . doba 2 i+1 . doba
D a v id P a v e l
H o n z a
2 i
z }| {
2 i
z }| {
Vzhledem k tomu, ¾e i+1 < n 1, majíHonza a Pavel od sebe vzdálenost 2 i
+2 i
=
2 i+1
(vzdálenostpøesDavidajekrat¹íne¾mimoDavida),tedysmìremkDavidovisenenajde
organizátor,kterýbyodnihmìlvzdálenostmen¹íneborovnou2 i+1
1atleskalby.Smìrem
odDavidasenenajdetaké,nebo»nìjakýtakovýFilipbymìlodDavidavzdálenostvìt¹íne¾2 i
,
ale men¹íne¾ 2 i+1
,o¾ byznamenalo,¾ebyFilipovavzdálenostodnejbli¾¹íhotleskajííhona
l :dobubyla(z pøedpokladu,¾e nal :dobu dovzdálenosti2 i+2
1 odDavidanikdonetleská)
vìt¹íne¾2 i
,o¾ jeopìt sporstím,¾e o2 i
dobpozdìjiFiliptleská.Tedyvíme,¾edostateènì
dalekoodHonzyaPavlanikdonetleská,mù¾emepou¾ítindukènípøedpokladadostaneme,¾e
na(2 i+1
).dobutleskajíti,kteøímajívzdálenostodHonzyèiPavlalihouamen¹íneborovnou
2 i
,o¾jsouti,kteøímajíodDavidavzdálenostlihouamen¹írovnou2 i+1
,anetleskajíti,kteøí
majívzdálenost od Honzy èiPavlasudou a men¹ínebo rovnou 2 i
,o¾ jsou ti,kteøí majíod
Davidavzdálenostsudouamen¹írovnou2 i+1
,o¾jsmehtìlidokázat.
Pron=1jeøe¹eníeléúlohysnadné,obaorganizátoøisevtleskánístøídajíashùzkanezaène.
Pro n > 1 u¾ jenpou¾ijeme právì dokázané tvrzení pro Mihala, 1. dobu a k = n 2,
dostaneme,¾ev¹ihni,kteøímajíodMihalavzdálenost lihou,na2 n 1
.dobutleskají,odkud
na(2 n 1
+1) .dobunetleskánikdo.
Poznámkykdo¹lýmøe¹ením: Úlohujsemhodnotilvelmimírnì,proto¾epøesnéøe¹ení(takové,
kterémubynebylomo¾nésemtamnìovytknout)nebylovùbesnadnénapsat.Tedyzamy¹lenku
øe¹eníjsemu¾(vìt¹inou{pokudbylaaspoòtrohuprùkazná)udìloval3body.Dvaimaginární
bodysizaslou¾iliVladoVirèíkaEvaÈernohorská,kteøíúlohudokazovaliindukíav¹imlisi,¾e
kdy¾tleská 2 n
organizátorùapozorujemejenka¾déhodruhéhoorganizátora,taktleskajízela
stejnì(a¾nanìjakéopo¾dìní),jakokdybytleskalojen2 n 1
organizátorù.
3.úloha
NajinéshùzesipotradiènímpozdravuMartinv¹imlzajímavénovinky,toti¾elápodlahaje
pokrytadla¾dièkamitypu"L"(vizobrázekna koni). David hneddodal,¾e jeto mopìkné,
proto¾e nejen menzu,ale rovnouelou rovinu lzepokrýt tìmitodla¾dièkamitak, ¾e ka¾dá je
pou¾itaprávìjednou.MáDavidspokrývánímrovinypravdu?
Doká¾eme,¾eDavidmápravdu,atotak,¾enajdemevhodnépokrytíroviny.OznaèmesiL
k
dla¾dièkutypu"L"obsahujííkètvereèkù.Pokrývámetedydla¾dièkamiL3,L4,::: Nejprvesi
uvìdomme,¾eprolibovolnépøirozenék3mù¾emepomoídla¾dièekL
k ,L
k +1 aL
k +2 pokrýt
obdélník(k+1)3bezètvereèkuvpravémhornímrohu,alenaopaksètvereèkemnavívlevém
hornímrohu(vizobrázek).Dùkazsnadnoplynezobrázku.
L k+2
L k
L k+1
Oznaèmetakový pozmìnìnýobdélník O
k
.PokudsenámrovinupodaøípokrýtútvaryO3,
O6,O9,:::,pou¾ijemeka¾doudla¾dièkutypu"L"právìjednou,hledejmetedytakovépokrytí.
Rozøe¾merovinu na pásyo tlou¹»e 3.Ka¾dý ztìhto pásùlze snadnopomoí pozmìnìnýh
obdélníkù pokrýt, musímev¹akpokrývat aspoò trohu hytøe,abyhomzaruèili,¾e iv¹ehny
pásybudoupokryté.
O 3
O 6
O 9
O 12
O 15
O 18
O 21
O 24
O 27
p
O 30
O 33
O 36
O 39
O 45
O 48
O 54
O 57
O 60
O 63
O 66
O 72
Zvolmesinìjakoupøímkupkolmounapásyanìjakýzpásùoznaèmezaprvní.O3umístìme
doprvníhonalevoodp(vizobrázek).Potompoøadìumís»ujme3,5,7,::: nejmen¹íhO
k ,ato
v¾dyodshoradoludosousedníhpásù tak,¾eumís»ujeme-li2i 1obdélníkù,budei:umístìn
doprvníhopásu.Navípravidelnìstøídejme,jestlipozmìnìnéobdélníkypokládámetìsnìvedle
nalevonebonapravoodji¾polo¾enýh(vpøípadì,¾evdanémpásuje¹tì¾ádnýpolo¾enýnení,
pokládejmenapøíkladtìsnìvedlep).
Uvìdomímesi,¾e takovýmzpùsobem u¾vydla¾dièkujemeelou rovinu.Staèí siuvìdomit,
¾evydla¾dièkujemeka¾dýzpásù.Mìjmetedynìjakýpássevzdálenostímodprvního.Potom
v¾dy kdy¾pokládáme2m+1,2m+3,2m+5,::: upravenýh obdélníkù,polo¾ímena tento
pásnìjakýznih.Tojenekoneènìmnohopozmìnìnýhobdélníkù,ajeliko¾pravidelnìstøídáme
pravoualevoustranu,nenítì¾késirozmyslet,¾epáspokryjemeelý(ètvereèek sevzdáleností
j odpøímkypnanejvý¹ po 2jkroíh{ alespoòj jihjena správnoustranua ka¾dýO
k má
tlou¹»kualespoò1).
Poznámkykdo¹lým øe¹ením: Vpodstatì nikdozøe¹itelù neprovedl poøádnýdùkaz toho,¾e
svýmzpùsobempokryjeskuteènìelourovinu.Nutnopodotknout,¾eúlohabylapomìrnìtì¾ká
{ tedynatøíbodovku.Ztohotodùvodujsemdávalzaþpouhéÿ nalezení zpùsobupokrytíplný
poèet bodù.V¹embyhale doporuèilpoøádnìprostudovatvzorovéøe¹ení.Èastýmproblémem
bylotakéto,¾enìkteøíøe¹itelénevìdìli,otoznamenápokrýtelourovinu,popø.tentopojem
¹patnìpohopili.Opìtbyhseodkázalnavzorovéøe¹eníadoplòujíípoznámkujakzjistit,zda-li
jsmepokryliskuteènì elourovinu.Pokrytí jeúplné,pokudplatí:Prolibovolnì velký ètvere
sestranamikoneèné délky,jen¾ mástøedvpevném(tzn. pro v¹ehnyètverestejném)bodì,
existujekoneènýpoèetkrokùpokrývání,pojejih¾provedeníbudevybranýètverepokrytý.
4.úloha
Mezitím,osiostatníorganizátoøido¹liproobèerstvení,Marekhlídalbundyahrálsisdrobeèky
nastole.Podaøilosemujeposkládatdozajímavéhoútvaru,kdyvokolíka¾déhodrobeèkujsou
právìtøijiné,kteréodnìjmajívzdálenost5m.Kolikmohlobýtdrobeèkù?
Pøedpokládejme,¾enastolejeaspoòjedendrobeèek.Paktedymusíbýtaspoòètyøi.Pro4
drobeèkyaleneexistujerozestavìnívyhovujíí podmínkámúlohy,o¾doká¾emesporem.Neh»
takovérozestavìníexistuje.Pakvzdálenostlibovolnédvojierùznýhdrobeèkùje5m.Ka¾dá
trojie drobeèkù tedy tvoøí rovnostranný trojúhelník o stranì 5 m. Oznaèíme-lisi drobeèky
písmenyA;B;C ;D,paktrojúhelníkyABC aABDjsourovnostranné,bodyCaDjsourùzné,
atedyCjeosovìsoumìrnýsDpodleosyABavzdálenosttìhtodvoubodùje p
35m6=5
m.
Drobeèkùtedymusíbýtaspoò5.Nemù¾ejihbýtalelihýpoèet,o¾zasedoká¾emesporem:
neh»existuje rozestavìní lihéhopoètu drobeèkùsplòujíípodmínkyúlohy.Paktakéexistuje
graf, jeho¾ vrholyjsou drobeèky a hranyjsou dvojiedrobeèkù,které majívzdálenost5 m.
Tentografmálihýpoèetvrholùaka¾dývrholmástupeò3(tedyjetakélihý).Tojealespor,
proto¾esouèetstupòùv¹ehvrholùvgrafujev¾dysudéèíslo(dvojnásobekpoètuhran).
Vímetedy,¾epoèetdrobeèkùmusíbýtsudéèíslovìt¹íneborovno6.Proka¾détakovéèíslo
ji¾existujerozmístìnívyhovujíízadání:
Mìjme2kdrobeèkù,kdek3jeeléèíslo.Rozdìlímejenadvìpoloviny,zprvnísestavíme
pravidelnýk-úhelníkostranì5mazdruhésestavímeshodnýk-úhelník,kterývznikneposu-
nutímtoho pùvodníhoo5mvevhodnémsmìru:existujejenkoneènìsmìrùtakovýh,¾eby
posunutýk-úhelníkmìlspoleènývrholspùvodnímk-úhelníkemajenkoneènìsmìrùtakovýh,
¾ebynìjakývrholposunutéhok-úhelníkamìloddvou vrholùpùvodníhok-úhelníka vzdále-
nost 5 m(pro libovolnoudvojiivrholùpùvodního k-úhelníkaexistují vrovinìnejvý¹edva
rùznébody,kterémajíodobouvrholùvzdálenost5m,advojivrholùjekoneènìmnoho).
Zezbylýh(nekoneènìmnoha)smìrùtedynìjakývyberemeavevzniklémrozmístìnídrobeèkù
pakplatí,¾e ka¾dývrholmáprávìdvasousedyvesvém k-úhelníkua právìjednohosouseda
vdruhémk-úhelníku(kdesousedznamenádrobeèekvzdálený5m).
Poznámkykdo¹lýmøe¹ením: Tentopríkladnebola¾taký»a¾kýaveµazváshopretomaloza
pä»bodov.Mnohív¹akna¹lilenjedenzmo¾nýhpoètovdrobeèkovatýmpádomnemohlima»
veµabodov.Na¹lisadokonaajrie¹itelia,ktorírozoberaliprípadprenekoneèneveµadrobeèkov
aleibajedenzvássiv¹imol,¾edrobeèkovmohloby»ajnula.
5.úloha
Jeliko¾jsou matfyzáilínípøeházet mezijednotlivýmimístnostmimenzy,vystavìlisiú¾asný
systém mikrotramvají.Mezi ka¾dými dvìma místnostmijezdí mikrotramvaj v právì jednom
smìru.Dinovizaèínávièenía¾zapùlhodiny,atakhonapadlo,¾evolnýèasmù¾evyplnittím,
¾esivyberenìjakouprvnímístnostapakseprojedemikrotramvajemipomenzetak,¾eka¾dou
místnostnav¹tívíprávìjednou(anebudemezimístnostmipøeházet).Doka¾te,¾etakovývýbìr
estováníseDinovimù¾epovést,a»u¾mikrotramvajejezdíjakkoliv.
Úlohuvyøe¹ímeindukívzhledemkpoètu místnostímenzy.Prodvìaménìmístnostínení
o øe¹it.Pøedpokládejme tedy,¾edanou trasulze najít prolibovolnì jezdíítramvajemezin
místnostmi,arozhodnìme,zdajetomutakipron+1místností.
Mezi prvníminmístnostmisemù¾emepodleindukèníhopøedpokladuprojet.Bez újmyna
obenostitramvajejezdízprvnídodruhé,zdruhédotøetí,:::,zn 1.don.místnosti(kdy¾
ne,takjepøeèíslujeme).Otázka je,zdalzev¾dy natutotrasunìjaknapojitna¹ipøebyteènou
n+1.místnost.
Pokudjedetramvajzna¹ípøebyteèné n+1.místnosti doprvní místnosti,jevymalováno,
nebo» poté pøejedeme zn+1. místnosti do první a pokraèujemepo pøede¹lé trase. Tedy se
omezímenapøípad,kdytramvajejezdízprvnídon+1.místnosti.
Pokudtramvajejezdízprvéa¾k.místnostidon+1.místnosti,alenaopakzn+1.místnosti
dok+1.místnosti,jsmetakéhotovi,nebo»potomna¹itrasuprojedemevpoøadímístností1,2,
:::,k,n+1,k+1,k+2,:::,n.
Zbývátedydoøe¹it poslednípøípad,kdy¾tramvajedon+1.místnostipouze pøijí¾dìjí,ale
neodjí¾dìjízní.Tojev¹akjednoduhé,místnostiprojedemepøesnìtak,jakjsouoèíslovány{od
1don+1.
Poznámkykdo¹lýmøe¹ením: Správnáøe¹eníbylavesmìspodobnaautorskému,odli¹népøístupy
kílispí¹enevedly,nebo»vnihøe¹iteléèastobralizazøejmátvrzení,kterábuïtozdalekazøejmá
nebyla(bylapøinejmen¹ímstejnìobtí¾nájakoúlohasama),nebovùbeneplatila.
6.úloha
Jednou sissebou na shùzku An¹a vzala velkédomino.V¹imlasi, ¾e její dominovékostièky
zakrývajíprávìdvìpolíèkatrohuzvlá¹tní¹ahovnie(2n + 1)krát(2n + 1),nakteréprávì
PavelsFrsemhráli¹ahy.Rozehraná¹ahovápartiejípøíli¹nezajímala,postupnìbralagurky
z¹ahovniea skládalananidominovékostièky.Nakone zaplnilaelou ¹ahovnii a¾na levé
dolnípolíèko.Honzasiv¹iml,¾esdominylzepo¹ahovniiposouvattak,¾eka¾dépolíèko,které
seodlevéhodolníholi¹ívobousouøadniíhosudéèíslo,mù¾ezùstatnezakryto.Napadloho,¾e
ikdybyAn¹aposkládaladominajinak(slevýmdolnímpolíèkemnezakrytým),budestáleplatit
jehopozorovánízpøedhozíhorozestavìní.PoraïteHonzovi,jakjehonápaddokázat.
Oznaèmesouøadniemi(i;j)políèkovi-témøádkuaj-témsloupitak,¾edolnílevépolíèko
má souøadnie (1;1). Políèka sobìma souøadniemilihými nazvìme èerná, políèka sobìma
souøadniemisudými¹edá,ostatníbílá.Másetedydokázat,¾epøilibovolnémrozestavìní,kdy
jepolíèko(1;1)nezakryté,lzeposouvánímdominodkrýtka¾dézostatníhèernýhpolíèek.
Zvolme libovolnìnìjaké èernépolíèko C0 = (i0;j0), kteréjena zaèátku zakryto. Domino
le¾íínaC0pokrýváje¹tìjednosousedníbílépolíèkoB0=(i0+a0;j0+b0)(právìjednozèísel
a0;b0jerovno0,druhé1nebo 1).OznaèmeC1=(i0+2a0;j0+2b0)(nejbli¾¹íèernépolíèkove
smìrudominovékostkyle¾íínaC0).PokudnaC1 le¾ídomino,najdemepodobnýmzpùsobem
políèkoC
2
,atd.Obenìpokudprok0napolíèkuC
k
=(i
k
;j
k
)le¾ídominopokrývajííje¹tì
políèkoB
k
=(i
k +a
k
;j
k +b
k
),oznaèímeC
k +1
=(i
k +2a
k
;j
k +2b
k ).
Pokud pro ¾ádné pøirozené k nenastane C
k
= (1;1), musíse nìkde posloupnost C
0 , C
1 ,
::: zayklit. Oznaème tedy m nejmen¹ípøirozené èíslo takové, ¾e Cm = C
k
pro nìjakék 2
f0;1;:::;m 1g.PolíèkaC
k ,B
k ,C
k +1 ,B
k +1 ,:::,C
m 1 ,B
m 1
tedyohranièujímnohoúhel-
ník M
1
slo¾enýzr
1
<(2n+1)(2n+1) ¹ahovniovýhpolíèek(do tohotomnohoúhelníkuse
nezapoèítávajípolíèkaC
k
,:::,Bm
1
),mezinimi¾jeaspoòjedno¹edé(napøíkladprávìjedno
zedvou¹edýhpolíèek,kterárohemsousedísCmaCm+1),oznaèmesijejS0.Totopolíèkonení
rohové,musítedybýtpokryto dominem,kterésouèasnìpokrývánìjakésousedníbílépolíèko
le¾íívM1.Podobnì jako posloupnost C0,C1,::: sestrojme posloupnost ¹edýh políèek S0,
S1,::: V¹ehnatatopolíèkale¾ívM1,jsoutedypokrytadominyaposloupnostseopìtzayklí,
èím¾dostanememnohoúhelníkM2slo¾enýzr2<r1¹ahovniovýhpolíèek,mezinimi¾jeaspoò
jednoèerné.TaktobyhompostupnìzkonstruovalinekoneènouposloupnostmnohoúhelníkùM
1 ,
M
2
,:::,jejih¾obsahyr
1 ,r
2
,::: sevka¾démkrokuzmen¹ujíaspoòo1,o¾jespor.(Kesporu
sedádojítijinak{napøíkladkdy¾sedoká¾e,¾eobsahr
1
mnohoúhelníkuM
1
jelihéèíslo.)
Existujetedypøirozenéèíslok,prokteréC
k
=(1;1).PolíèkoC0 lzeodkrýtpoktazíh:pøi
p-tém tahu posuneme dominole¾íína políèku C
k p
o jednopolíèko tak, ¾ezakryje C
k p+1
aodkryjeC
k p .
Poznámkykdo¹lýmøe¹ením: Väè¹inarie¹iteµovdokazovala,¾eka¾dépolektoréHonzauvolní,
musíby»odlavéhodolnéhorohuvzdialenéopárnypoèetriadkoviståpov.Zatakétorie¹enie
somnekompromisneudeloval0bodov:-(.Takihv¹etkýhprosím,venujtetomuhvíµkuèasu
auvedomtesi:Jetopodstatneináúlohaapodstatnelah¹iaúlohane¾dokazova»,¾ev¹etkypolia
ktoré súodlavéhodolnéhovzdialenéopárnypoèetriadkova ståpovm¾eHonzaposúvaním
domínuvolni».
7.úloha
Jídelnavmenzemáètverový pùdorysse¹ahovniovou podlahouon 2
políh.Vka¾démpoli
¹ahovnie je jedno místo k sezení. Ne v¾dy se obìd v menze podaøí uvaøit podle pøedstav
studentù. Jednou, kdy¾ byla menza plná, bylo pár porí dokone pøiotrávenýh salmonelou.
Navísepostupnìnakazovalidal¹ístudenti tak, ¾ekdykolivmìliaspoò dva sousedy(hranou,
nikolirohem)naka¾ené,nakazilisetaké.Koliknejménìmohlobýtotrávenýhporí,kdy¾víme,
¾esenakazilaelámenza?
Nakreslemesiplánjídelnydo nekoneèné ètverovésítìjako ètvere ostranìdélkyn(ka¾-
démustudentoviodpovídájednopolíèkosítì).Oznaèmekpoèetotrávenýhporí(nebolipoèet
naka¾enýhstudentùnazaèátku) aobarvìmepøíslu¹nýhkpolíèekzelenì,ostatnípolíèkajsou
bílá. Oznaème P poèet hran,které sousedí s bílýmizeleným políèkem (P jesouèet obvodù
v¹ehzelenýh mnohoúhelníkù).Musí platitP 4k,proto¾eka¾dé zelenépolíèko pøispìjedo
výslednéhosouètumaximálnì4hranami.
V¾dy,kdy¾ senakazí dal¹í student, obarvíme jemu odpovídajíípolíèko zelenì.Pøitom se
èíslo P nezvìt¹í:pokudpolíèko pøedobarvenímsousedilosk 2zelenými políèky,ubudepo
jehoobarveníkhranoddìlujííhzelenéabílépolíèkoa pøibudejihjen4 k.Dohromadyse
tedyèísloPzvìt¹ío4 2k0.A¾senakazíelámenza,budezelenìobarvenelýètverenkrát
n,èísloP tedybuderovno4n.StálebudeplatitP 4k,zèeho¾plynekn,tedynaotrávení
elémenzyjepotøebaaspoònotrávenýhporí.
Tentopoèetjetaképostaèujíí: napøíkladpokudjsounazaèátku naka¾eni v¹ihnistudenti
sedíínajednéúhlopøíèeètvere(napolíèkáhosouøadniíh(1;1)i,(2;2),:::,(n;n)),nakazí
se vprvním krokuv¹ihnistudenti na souøadniíh(i;j), kde ji jj= 1 (sousedí se dvìma
naka¾enými studenty na souøadniíh (i;i) a (j;j)), obenì vk-tém krokuse nakazí v¹ihni
studentinasouøadniíh(i;j),kdeji jj=k.Pon 1kroíhtedybudenaka¾enáelámenza.
Poznámkykdo¹lýmøe¹ením: Témìøv¹ihniøe¹itelépøi¹linato,¾ennaka¾enýhporístaèí
na naka¾ení elé menzy.Za tuto (jednoduhou) èást jsem udìloval 1 bod.Bylov¹akpotøeba
je¹tìdokázat,¾emen¹ípoèetnaka¾enýhporínestaèípøilibovolnémpoèáteènímrozmístìní(4
body).Stímji¾mìlomnohoøe¹itelùproblémy.Èastáhybnáargumentaespoèívalavtvrzení,
¾eoptimálnírozmístìnípromenzu(n+1)(n+1)musívzniknoutzoptimálníhorozmístìnípro
menzunnpøidánímjednénaka¾enépore,proo¾neexistujevna¹empøípadì¾ádnýzjevný
dùvod.Navíto nenípravda (rozmyslete si,¾e existuje spoustaoptimálníh rozmístìní,které
tímtozpùsobemnevzniknou).
8.úloha
Pomìrnìnedávno sevmenzeopravovaloosvìtlení.Elektrikáøinatahaliv¹ude pomenzedráty
(pøímky),nìkterédrátyseobèasprotínaly,ale¾ádnétøivjednombodì.Systémdrátùbylopravdu
velminepøehledný,míøilyodstropu kpodlaze,odpodlahykestìnám, od stìnkestìnám:::
Dokone¾ádnétøidrátynele¾elyvjednérovinì.Kolikdvojidrátùsenejvý¹emohloprotínat?
Zaènemestím,¾e siøekneme pár pojmùtýkajííhsegrafù, pokudví¹,o jegraf, stupeò
vrholuatrojúhelníkvgrafu,mù¾e¹následujíídvaodstavepøeskoèit.
GrafemGbudemerozumìtuspoøádanoudvojiiG=(V;E),kdeV budemenazývatmno¾inou
vrholùaE mno¾inouhran.Pooboumno¾ináhbudemehtít,abybylykoneèné.Pomno¾inì
Ebudemenavíhtít,abybylapodmno¾inoudvojivrholù.Grafsitedymù¾emepøedstavovat
jakonìjakoumno¾inubodù(=vrholù)napøíkladvrovinì,pøièem¾nìjakédvojievrholùjsou
spojenéhranami.Abydvavrholyspojovalovíehranjezakázáno,stejnìjakojezakázáno,aby
nìjaká hranavedlaznìjakéhovrholuv opìt do v.Stupnìmdegvvrholuv rozumímepoèet
hranzvrholuvvyházejííh.NakonetrojúhelníkemvgrafuGbudemerozumìttakovoutrojii
vrholùu,v,w,¾efuvg,fuwgafvwgjsouhrany(tj.le¾ívmno¾inìhran).
1
2
3
4
5
6
NaobrázkujejakopøíkladnakreslengrafG=(V;E),kdeV =f1;2;3;4;5;6g,E=ff23g,
f24g,f34g,f35g,f45g,f46gg.Tentografobsahujedvatrojúhelníkytvoøenévrholy234a345.
Nakonedeg1=0,deg2=2,deg3=3,deg4=4,deg5=2,deg6=1.
Nynísidoká¾emelemma,kterénámbudevelminápomoné.
(~)GrafGbeztrojúhelníkùsnvrholymánanejvý¹ j
n 2
4 k
hran 1
.
Dùkaz.Oznaèmempoèethran.Dáleoznaèmev
1 ,v
2 ,:::,v
n
vrholygrafuGae
1 ,e
2 ,:::,
e
m
hranyG.Nakoneprohranue
k
=fv
i v
j
goznaèmedege
k
=degv
i +degv
j .
Uvìdommesi,¾eplatí
2m
n
= n
P
i=1 degv
i
n
v
u
u
u
t n
P
i=1 deg
2
v
i
n
= v
u
u
u
t m
P
k =1 dege
k
n
r
mn
n
= p
m: (})
Potomdostáváme 2m
n
p
m, p
m
n
2 ,m
n 2
4
.Vzhledemktomu,¾emjeelé,tedyplatí
m
j
n 2
4 k
.Kúspì¹némudokonèenídùkazutedyzbýváuvìdomitsi(}).
Prvnírovnostjesnadná,sèítáme-litoti¾stupnìv¹ehvrholù,mù¾emesipøedstavit,¾epøièí-
támejednièkuzaka¾douhranu,kterávededodanéhovrholu,prov¹ehnyvrholy.Tímka¾dou
hranuzapoèítámedvakrát,nebo»vedemezidvìmavrholy.
Následujíínerovnostplynepøímoznerovnostimeziaritmetikýmakvadratikýmprùmìrem.
1
Výraz bxproxreálné znaèídolníelou èástèísla x,tj.nejvìt¹íelé èíslo,kteréjemen¹í
neborovnox.
Dal¹írovnostsiuvìdomímepodobnýmargumentemjakoprvnírovnost.Souèetdruhýhmo-
ninstupòùsitoti¾lzepøedstavittak,¾ezaka¾douhranu,kterávededodanéhovrholu,pøièteme
stupeòvrholu,prov¹ehnyvrholy.Zaka¾douhranue
k
=fv
i v
j
gtedyjednoupøiètemestupeò
vrholuv
i
ajednoustupeòvrholuv
j
,o¾jepøesnìdege
k .
Vposlednínerovnostikoneènìvyu¾ijemetoho,¾esejednáografbeztrojúhelníkù.Cheme
si uvìdomit,¾e m
P
k =1 dege
k
mn,k èemu¾ sistaèí uvìdomit,¾e pro ka¾dé k jedege
k n.
Pøedpokládejme, ¾ee
k
=fvivjg.Neh» pro spor jedegvi+degvj >n. Tedy zDirihletova
prinipu(vrholù jepouze n)existuje vrhol v
l
takový,¾e fv
i v
l g ifv
j v
l
g jsou hrany.Zøejmì
l6=i;l6=j,proto¾ehrananemù¾evést zv
i dov
i
,respektivezv
j dov
j
.Jen¾e tímdostáváme
sporstím,¾eGneobsahujetrojúhelníky,v
i v
j v
l
jetoti¾trojúhelník.
v i
v j
v l
e k
Tímjedùkaz(~)ukonèen.
Nyníu¾vyøe¹ímezadanouúlohu.Pøedpokládejme,¾emámendrátù.UtvoømegrafG,jeho¾
mno¾inouvrholùbudemno¾inadrátùahranyvedoumezitìmidráty(vrholy),kteréseprotí-
nají.Tentografneobsahujetrojúhelníky.Kdybytoti¾pronìjakétøidrátyd
i ,d
j ,d
k
platilo,¾e
sed
i ad
j
protínají,d
i ad
k
protínajíad
j ad
k
protínajívetøehrùznýhbodeh,potomd
i ,d
j
ad
k
le¾í vjednérovinì,o¾ jesporspøedpokladyúlohy.Podle(~)máGnejvý¹e j
n 2
4 k
hran,
tedynejvý¹etolikdvojidrátùsemù¾eprotínat.
x y
p 1
p 2
p 3
p 4
q 1
q 2
q 3
q 4
Nadruhoustranu naleznemepøíklad,kde seu¾ j
n 2
4 k
dvojipøímek(drátù) protíná,a tím
uká¾eme,¾e n
4
jehledanáhodnota.Pøímkynaleznemenapøíkladnagrafufunkef(x;y)=xy.
Prvníh
n
2
pøímekoznaème p
1 ,p
2 ,:::,p
b n
2
,zbývajííhn
n
2
pøímekoznaème q
1 ,q
2 ,
:::, q
n
b n
2
.Pøímkup
k
nalezneme tak, ¾e polo¾ímey = ka z =f(x;k) =kx, tedy p
k
=
f[x;y;z℄jx2R;y=k;z=kxg.Pøímkuq
k
naleznemetak,¾epolo¾ímex=kaz=f(k;y)=ky,
tedy q
k
=f [x;y;z℄jy2R;x=k;z=kyg.Pøímkyp
1 ,p
2 ,:::,p
b n
2
jsounavzájemmimobì¾né
(majírùznésmìrniejakofunkexale¾ívrovnobì¾nýhrovináhy=k),podobnìq1,q2,:::,
q
n b n
2
jsounavzájemmimobì¾né,odtudu¾snadnoplyne,¾e¾ádnétøinele¾ívjednérovinìani
se¾ádnétøineprotínajívjednombodì(na¹libyhomtamdvìmimobì¾né).Nadruhoustranu
mají
n
2
n
n
2
prùseèíkùf(i;j)proi2f1;2;:::;
n
2
gaj2f1;2;:::;n
n
2
g.Nyníu¾
sistaèíuvìdomit,¾e
n
2
n
n
2
= j
n 2
4 k
.Pronsudéje
j
n
2 k
n j
n
2 k
= n
2
n n
2
= n
2
4
=
n 2
4
;
pronlihéje
j
n
2 k
n j
n
2 k
= n 1
2
n n 1
2
= n
2
1
4
=
n 2
4
:
Tímjeúlohavyøe¹ena.
Poznámkykdo¹lýmøe¹ením: Øe¹itelelzezhrubarozdìlitdotøískupin.Øe¹itelévprvnískupinì
vyøe¹ili úlohu ze zadání a získali 5 bodù. Vdruhé skupinì seobjevili øe¹itelé, kteøí vyøe¹ili
jinouúlohu.Toti¾poèítalipoèetmo¾nýhprùseèíkùprolibovolnémno¾stvípøímek(avy¹lojim
nekoneèno).Tatoúlohajevýraznìlehèí(jednáseolehèítøíbodovouúlohu),atakøe¹itelemohlo
napadnout,¾etoasinebudesprávnáinterpretae(navíelektrikáøibudouasitì¾komítnekoneènì
mnohodrátù,abymìlinekoneènìmnohoprùseèíkù).Niménì,proto¾esedojistémíryjednalo
iona¹ihybu(poèetpøímekjsmeneoznaèili),rozhodljsemsezatakováøe¹eníudìlovat3body.
Tøetí skupinu tvoøili øe¹itelé, kteøínevyøe¹ili úlohu vùbe. Kuriózníbylonapøíklad øe¹ení, ve
kterémpoèetmo¾nýhprùseèíkùvy¹elvìt¹íne¾poèetdvojipøímek.
