7. príklad - Vzorové riešenie
Kategórie:
5
6
7
8
9
Zadanie
Lístky na Merlinovu kúzelnícku show stáli nejaký celočíselný počet dukátov, väčší ako 1. Navyše platilo, že súčet ceny detskej a dospeláckej vstupenky, rovnako ako ich súčin, bol mocninou prvočísla. Nájdite všetky možné ceny vstupeniek.
Vzorové riešenie
Opravovali: Paľo
*** Poznámka: Riešitelia, ak sa vám zdá nejaká časť zadania nepresne zadaná, neváhajte sa spýtať v komentároch pod zadaním. Na tento príklad sa dvaja z vás v komentároch spýtali, no zjavne nie všetci si tieto komentáre prečítali. Stratili preto dotyční body. Nestrácajte prosím takto zbytočne body a radšej sa spýtajte/prečítajte tie komentáre. ***
Označme si najprv cenu dospeláckeho lístka a a cenu detského lístka ako c. Potom ak p, q budú prvočísla a x, y budú kladné celé čísla, tak potom zadanie nám poskytuje nasledovné dve rovnice:
Práve tieto p^x, q^y, to je definícia toho, čo je kladná mocnina prvočísla. To, že je kladná a nie nulová, vyplýva z toho, že p^0 = 1 a v tom prípade by musel stáť aspoň jeden typ lístka menej ako 1, čo je v rozpore so zadaním.
Ak dve čísla v súčine sú mocnina prvočísla, tak aj samotné čísla musia byť mocninami toho istého prvočísla. To vyplýva z vlastností prvočísel a prvočíselných rozkladov. Zároveň vieme, že opať ani jedna táto mocnina nesmie byť nultá, lebo by sme mali vstupenku s cenou 1. Preto, ak k,m sú kladné celé čísla, vieme zapísať a = q^k, b = q^m.
Dosadením tohto poznatku do rovnice so súčtom máme:
Teraz môžeme celú rovnicu vydeliť q^m, získame q^{k-m} + 1 = q^{x-m}. Zároveň si môžeme byť istí, že x-m \geq 1, inak by bola druhá vstupenka zápornej (alebo nulovej) ceny, čo nemôže. V tom prípade q^{x-m} je kladná mocnina prvočísla q.
Ak teraz by bolo číslo q nepárne, tak jeho nezáporná mocnina q^{k-m} by bola nepárna a rovnako tak aj jeho kladná mocnina q^{x-m}. Lenže potom by sme mali rovnicu nepárne + 1 = nepárne, čo nemôže nastať.
Preto je q párne číslo. Vzhľadom na to, že q je zároveň prvočíslo, nutne platí, že q = 2. V tom prípade máme na pravej strane rovnice párne číslo a na ľavej strane máme 2^{m-k}+1. Na to, aby tento súčet bolo párne číslo, musí byť 2^{m-k} nepárne. Jediná nepárna mocnina dvojky je 1 a to sa stane práve vtedy, ak m = k.
Jediná vhodná možnosť je teda taká, že cena detskej a dospeláckej vstupenky je rovnaká a navyše sú to kladné mocniny dvojky.
* Poznámka: to, že je to bez ujmy na všeobecnosti, vieme z toho, že tá rovnica je symetrická v tých dvoch premenných. Ak by bola nerovnosť medzi nimi naopak, nič v postupe by to nezmenilo, iba značenie.
Označme si najprv cenu dospeláckeho lístka a a cenu detského lístka ako c. Potom ak p, q budú prvočísla a x, y budú kladné celé čísla, tak potom zadanie nám poskytuje nasledovné dve rovnice:
\begin{aligned}
a + c = p^x\\
a \cdot c = q^y
\end{aligned}
Práve tieto p^x, q^y, to je definícia toho, čo je kladná mocnina prvočísla. To, že je kladná a nie nulová, vyplýva z toho, že p^0 = 1 a v tom prípade by musel stáť aspoň jeden typ lístka menej ako 1, čo je v rozpore so zadaním.
Ak dve čísla v súčine sú mocnina prvočísla, tak aj samotné čísla musia byť mocninami toho istého prvočísla. To vyplýva z vlastností prvočísel a prvočíselných rozkladov. Zároveň vieme, že opať ani jedna táto mocnina nesmie byť nultá, lebo by sme mali vstupenku s cenou 1. Preto, ak k,m sú kladné celé čísla, vieme zapísať a = q^k, b = q^m.
Dosadením tohto poznatku do rovnice so súčtom máme:
\begin{aligned}
q^k + q^m = p^x
\end{aligned}
Bez ujmy na všeobecnosti*, nech k \geq m. Potom môžeme na ľavej strane vyňať pred zátvorku:
\begin{aligned}
q^m \cdot (q^{k-m} + 1) = p^x
\end{aligned}
Teraz ľavá strana je deliteľná q^m, kde m \geq 1, čo zároveň znamená, že ľavá strana je deliteľná q. Z toho vyplýva, že q delí aj pravú stranu. Keďže p je prvočíslo, ktoré je deliteľné iným prvočíslom q, nutne platí p = q.Teraz môžeme celú rovnicu vydeliť q^m, získame q^{k-m} + 1 = q^{x-m}. Zároveň si môžeme byť istí, že x-m \geq 1, inak by bola druhá vstupenka zápornej (alebo nulovej) ceny, čo nemôže. V tom prípade q^{x-m} je kladná mocnina prvočísla q.
Ak teraz by bolo číslo q nepárne, tak jeho nezáporná mocnina q^{k-m} by bola nepárna a rovnako tak aj jeho kladná mocnina q^{x-m}. Lenže potom by sme mali rovnicu nepárne + 1 = nepárne, čo nemôže nastať.
Preto je q párne číslo. Vzhľadom na to, že q je zároveň prvočíslo, nutne platí, že q = 2. V tom prípade máme na pravej strane rovnice párne číslo a na ľavej strane máme 2^{m-k}+1. Na to, aby tento súčet bolo párne číslo, musí byť 2^{m-k} nepárne. Jediná nepárna mocnina dvojky je 1 a to sa stane práve vtedy, ak m = k.
Jediná vhodná možnosť je teda taká, že cena detskej a dospeláckej vstupenky je rovnaká a navyše sú to kladné mocniny dvojky.
* Poznámka: to, že je to bez ujmy na všeobecnosti, vieme z toho, že tá rovnica je symetrická v tých dvoch premenných. Ak by bola nerovnosť medzi nimi naopak, nič v postupe by to nezmenilo, iba značenie.