4. príklad - Vzorové riešenie

Kategórie:
5
6
7
8

Zadanie

V bosoráckej ubytovni je 16 izieb a dokopy 16 ubytovaných (vrátane vedúcich). Izby sú rozmiestnené do štvorca 4 \times 4 a sú číslované po riadkoch. Ubytovaní si ale každú minútu menia izby, aby si vychutnali nezabudnuteľný zážitok pobytu v tomto podniku zo všetkých uhlov.

V plániku nižšie vidíte čísla izieb a tiež, do ktorej miestnosti sa ubytovaný posúva po pobyte v danej izbe.

č. 1 → č. 9
č. 2 → č. 8
č. 3 → č. 5
č. 4 → č. 14
č. 5 → č. 13
č. 6 → č. 12
č. 7 → č. 6
č. 8 → č. 4
č. 9 → č. 15
č. 10 → č. 16
č. 11 → č. 1
č. 12 → č. 11
č. 13 → č. 7
č. 14 → č. 10
č. 15 → č. 3
č. 16 → č. 2

Na začiatku (v prvej minúte) bol Majko v izbe č.1, Sebik v č.2, Krivoš v č.4 a Štepi v č.16.

  1. V koľkej minúte budú Krivoš a Štepi prvýkrát v susedných miestnostiach?
  2. V koľkej minúte budú Sebik a Majko 42-krát v susedných miestnostiach (okrem prvej minúty)?
Poznámka: Susedné miestnosti sú tie, ktoré majú spoločnú stenu, napr. pre izbu č.2 sú to izby 1, 3 a 6.

Vzorové riešenie

Opravovali: Danko, Tamarka_Krivosikova, TomasZuzik

Vo všeobecnosti je niekedy dobré sa trochu pohrať so zadaním na lepšie pochopenie toho, ako príklad funguje. Vypíšme si teda prvých pár presunov pre Krivoša a Štepiho z podúlohy a)​.

Minúta
1
2
3
4
5
6
7
Krivoš
4
​14
​10
16
2
8
4
Štepi
16
2
8
4
14
10
16

Môžeme si všimnúť, že v siedmej minúte sú Krivoš aj Štepi tam, kde začínali. Odtiaľ budú pokračovať rovnako ako pokračovali po prvej minúte, až sa znova dostanú na začiatok. Táto postupnosť presunov sa teda bude opakovať stále rovnako, každých 6​ minút. Zároveň môžeme v tabuľke skontrolovať, že žiadnej minúte sa Štepi a Krivoš nenachádzajú v susednej miestnosti. Z toho vyplýva, že sa nikdy nestretnú.

Podobne ako v časti a)​, v podúlohe b)​ si môžeme všimnúť, že presuny chlapcov sa po nejakom čase začnú opakovať. Konkrétne Sebikove presuny sa začnú opakovať po 6​ presunoch a Majkove po 10​ presunoch. Tieto postupnosti (cykly), ktoré sa pravidelne opakujú sú zapísané v tabuľke.

Minúta
1
2
3
4
5
6
7
8
9
10
11
Sebik
2
8
4
14
10
16
2
...



Majko
1
9
15
3
5
13
7
6
12
11
1

Keďže cykly nie sú rovnako dlhé, Majko nebude po jednom Sebíkovom cykle (6​ krokov) na rovnakom mieste. V ďalšom Sebíkovom cykle bude potom nejak posunutý oproti prvému, a teda aj keď sa v prvom nestretli, môžu sa stretnúť v niektorom ďalšom. Keby sme ale našli minútu, v ktorej sa obaja dostanú do svojich pôvodných miestností, našli by sme cyklus, ktorý sa bude opakovať. Potom by sme mohli spočítať koľkokrát budú v prvom cykle v susedných miestnostiach, a budeme to vedieť aj pre všetky ďalšie.

Taká minúta bude existovať, pretože v minúte, ktorá je násobkom dĺžok oboch cyklov budú končiť oba cykly, a v nasledujúcej minúte budú obaja v pôvodných miestnostiach. Teda hľadáme jednu minútu po násobku čísel 6​ a 10​ , ktorý ideálne bude čo najmenší, aby sme si zbytočne nekomplikovali prácu. Takéto číslo sa volá aj najmenší spoločný násobok. Najmenší spoločný násobok nsn(a;b)​ je najmenšie číslo také, že je násobok oboch čísel a aj b. V našom prípade je nsn(6;10)​ číslo 30​ (musí byť násobkom 2, 3​ aj 5​). Z toho vyplýva, že dĺžka cyklu, po ktorom sa obaja budú nachádzať v svojich pôvodných miestnostiach, je 30​.

Vypíšme si teraz tento cyklus:

Minúta
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sebik
\underline {2}
8
4
14
10
16
2
8
4
14
10
16
2
8
4
Majko
\underline {1}
9
15
3
5
13
7
6
12
11
1
9
15
3
5
Min
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Seb.
\underline{14}
10
16
2
8
4
14
10
16
2
8
4
17
10
16
\underline{2}
Maj.
\underline{13}
7
6
12
11
1
9
15
3
5
13
7
6
12
11
\underline{1}

Teraz nájdeme minúty, v ktorých sa chlapci nachádzajú v susedných miestnostiach*. Sú to minúty 1​ a 16​ podčiarknuté v tabuľke. Úplne prvú minútu ale nezapočítame (ako bolo napísané v zadaní), započítame až prvé minúty ďalších opakovaní tohto cyklu.

Počas jedného cyklu sa nachádzajú v susedných miestnostiach dvakrát. Po 21​ opakovaniach cyklu sa budú nachádzať v susedných miestnostiach 21 \cdot 2-1=41​ krát (odčítali sme 1​, lebo úplne prvú minútu nezarátavame). V ďalšom cykle sa potom budú nachádzať v susedných miestnostiach hneď v prvej minúte. Každý cyklus má 30​ minút, teda štyridsiaty druhý raz sa strretnú v 30 \cdot 21+1=631.​minúte.

*poznámka: Ak sa nám nechcú minúty hľadať stálym kontrolovaním v tabuľke, môžeme si to rozmyslieť takto: Budú to minúty, v ktorých čísla ich izieb majú rozdiel 4​ (potom sa budú nachádzať pod sebou v tabuľke), alebo kde majú rozdiel 1​ a zároveň menšie z čísel týchto dvoch izieb nie je deliteľné 4​ (teda napríklad 4​ a 5​ nesusedia, lebo 4​ je deliteľné 4, izba číslo 4​ je posledná v svojom riadku a 5​ je až v ďalšom riadku. Koniec riadku nastane práve keď je menšie z čísel deliteľné 4​).

Odpoveď: Krivoš a Štepi sa nestretnú. Sebik a Majko sa stretnú 42. krát v 631.​ minúte.

Komentár

Pri riešení podúlohy b)​ si treba dať pozor na počítanie s celými cyklami. Dve stretnutia sa totiž neudejú na jeho konci. Preto sa napríklad 41. krát nestretnú presne v 630. minúte, ale už v 616.​ minúte. Preto formulácie ako "Po tom, čo sa v 630.​ minúte stretnú 41.​ krát už musíme pridať len jednu minútu." nie sú úplne správne.​