Vzorové riešenia 2. kola

Môžme si všimnúť, že náš útvar sa skladá zo 7​ dielikov. Ofarbime si každú stranu dielika jednou farbou, najkratšiu zelenou, šikmú stranu oproti najkratšej modrou, najdlhšiu čiernou a poslednú červenou. Aby sa nám ľahšie počítal obvod útvaru, rozdelíme si ho na časti zložené z menej dielikov.

Pozrime sa najprv iba na spodný obdĺžnik zložený zo 4 dielikov:

Tento útvar má obvod  2 \cdot čierna + 2 \cdot červená + 4 \cdot zelená. Teraz k nemu pridáme hornú "šípku":

Táto šípka má obvod 2 \cdot červená + 2 \cdot zelená + 2 \cdot modrá . Vidíme, že spodná červená strana šípky sa dotýka obdĺžnika. To znamená, že úsek ktorým sa dotýkajú sme zarátali dvakrát (pre každý z útvarov sme ho zarátali raz) a nemáme ho zarátať ani raz. Môžeme si všimnúť, že sa dotýkajú dĺžkou presne 2 \cdot zelená. Takže musíme odpočítať 4 zelené (máme ich započítané každú dvakrát a má byť nulakrát).

Tieto dve časti majú obvod dokopy 2 \cdot čierna + 4 \cdot červená + 2 \cdot zelená + 2 \cdot modrá (sčítali sme obvody dvoch častí a odčítali dĺžku ktorou sa dotýkajú). Pozrime sa na posledný dielik:

Tento dielik má obvod 1 \cdot čierna + 1 \cdot červená + 1 \cdot zelená + 1 \cdot modrá. Všimnime si, že zvyšku sa dotýka dĺžkou presne jednej červenej strany, čo znamená, že musíme odpočítať 2 červené strany. Takže celkový obvod je 3 \cdot čierna + 3 \cdot červená + 3 \cdot zelená + 3 \cdot modrá. Vidíme, že toto je 3-krát obvod jedného dielika takže 3 \cdot 17 = 51.

Odpoveď: Obvod útvaru je 51.

V príklade, ako je tento, sa oplatí si neznáme čísla v krúžkoch označiť. Ľahšie sa nám o nich bude hovoriť, že D=8, ako "ľavé stredné políčko je 8".

Zamerajme sa na D. Jeho krúžok je spojený so šiestimi inými. Potom ale D=2 nie je možné, lebo potom F=1 aj F=3, keďže inde tieto čísla dať nemôžeme. Podobne vylúčime pre D aj 3,4,5,6,7. Teda D=1 alebo D=8. Rovnako takto odvodíme, že E=1 alebo E=8. Ak by však D=1, tak potom F=2, aby sa jednotka a dvojka nedotýkali. Ale podľa zadania mý byť F nepárne, čo nie je. Preto situácia na ľavom obrázku nastať nemôže.

Nutne musí platiť D=8, z čoho vyplýva, že F=7, aby sa tieto čísla nedotýkali. Potom už zostáva jedine možnosť E=1, a teda C=2. Táto sitácia je na obrázku vpravo.

Teraz sa zamerajme na A. To nemôže byť 3, lebo by sa dotýkala dvojky, no zároveň to nemôže byť ani 4 a ani 6, lebo A musí byť nepárne. Preto nutne A=5. Keďže A,B sa dotýkajú, B=4,\,B=6 nie sú možné. Takže B=3. Nakoniec si všimnime, že H=6 nie je možné, lebo by sa dotýkala sedmičky. Preto G=6 a nakoniec už zostáva len H=4. Celé riešenie je na nasledujúcom obrázku:

Odpoveď: Jediné možné rozmiestnenie je na poslednom obrázku.

Komentár

Väčšina z Vás zvládla úlohu bez problémov, čomu svedčí aj priemer vyše 8 bodov. Potešili ste ma. V tejto úlohe bolo veľmi nápomocné pracovať múdro: označiť si krúžky, zvoliť si dobré poradie dopĺňania čísel, a tak podobne.

Zamyslime sa najprv nad tým, aké súčty mohli byť na jednotlivých stranách. Najmenší možný súčet je 1+2+3=6, najväčší naopak 7+8+9=24. Môžeme si všimnúť, že 24 je 4-násobkom 6. Toto je teda jediné možné rozdeleni pozdĺž čiarkovanej čiary. Ak by sme zmenšili 24, museli by sme na zachovanie pomeru zmenšiť aj 6, čo nejde, podobne ako nejde zväčšiť 24, pri zväčšení 6. Navyše, keďže jednotlivé cifry musia byť rôzne, máme jednoznačne dané aj cifry, z ktorých musíme dané súčty poskladať.

Čo ďalej? Máme k dispozícii cifry 1,\, 2,\, 3,\, 7,\, 8,\, 9. Pri delení podľa plnej čiary musí byť súčet na jednej strane dvojnásobný ako na druhej. Keď sčítame dokopy čísla na oboch stranách, dostaneme 1+2 = 3-násobok súčtu na menšej strane. My však poznáme, ktoré čísla sú v krúžkoch, takže vieme aj ich súčet. Ten je 30. Na menšej strane podľa plnej čiary musí byť teda súčet 10, na väčšej bude 20. To so zadaním sedí.

Skúsme sa teraz zamyslieť nad tým, ako budú čísla umiestnené. Prvé čo si môžeme všimnúť je, že ak otočíme obrázok o 180 \degree dostaneme to isté. Vymenia sa len jednotlivé strany pozdĺž čiar.

Zvoľme si teda také otočenie, že naľavo od čiarkovanej čiary budú čísla 1,\, 2,\, 3 a napravo 7,\, 8,\, 9. Označme si ľavé horné číslo LH a pravé dolné PD. Môžeme si všimnúť, že súčet nad plnou čiarou je rovnaký ako súčet napravo od čiarkovanej, len sa v ňom miesto PD vyskytne LH. Keďže napravo sú väčšie čísla ako naľavo, touto výmenou sa súčet zmenší.

Opäť nás môže zaujímať o koľko? Ak nahradíme najväčšie možné číslo (9) najmenším možným (1), nastane najväčšia zmena, konkrétne o 8. Súčet nad plnou čiarou by bol 14. Naopak ak nahradíme najmenšie možné číslo (7) najväčším možným (3), súčet sa zmení najmenej, konkrétne o 4. Bude tak 20. My chceme zmeniť súčet na 10 alebo 20, čo sú zmeny o 14, respektíve o 4. Prvé dosiahnuť nevieme a druhé má len jedinú možnosť -- spomínaých 7 za 3.

Prejdime teraz k bodkovanej čiare. Vidíme, že na jednej strane má 3, na druhej 7. Okrem toho od seba oddeľuje 8 a 9 a taktiež 1 od 2. Naľavo od bodkovanej čiary teda môže byť súčet najmenej 1+3+8 = 12 a najviac 2+3+9 = 14. To znamená, že máme len tri možné súčty. Po rozdelení teda môže byť na jednotlivých stranách buď 12 a 18, alebo 13 a 17, alebo 14 a 16. Zadanie nám hovorí, že dvojnásobok súčtu na jednej polovici bude rovnaký ako trojnásobok súčtu na tej druhej. To platí len pri prvom rozdelení. Čísla tak už vieme jednoznačne doplniť. Nesmieme ešte zabudnúť na otočenie.

Odpoveď: V krúžkoch boli cifry 1,\, 2,\, 3,\, 7,\, 8,\, 9 v jednom z dvoch poradí:

Ako prvé sa môžeme pozrieť na to, ako využiť podmienku "súčet každých troch susedných políčok (v jednom riadku alebo jednom stĺpci) je 6". Nazvime si takéto tri políčka ako Trojicu. Môžme si teraz všimnúť, že vieme celú tabuľku rozdeliť na takých 8 Trojíc, že sa žiadne dve z nich neprekrývajú. Po takomto rozdelení nám zostane iba jedno políčko v strede tabuľky ktoré nepatrí do ani jednej Trojice.

Konkrétne rozloženie čísel v jednej Trojici nám neovplyvňuje súčet celej tabuľky, lebo každá z týchto Trojíc podľa pravidiel má súčet 6, nech sú čísla v nich hocijaké. Tak isto, každé číslo sa nachádza v práve jednej Trojici, takže bude v celkovom súčte zarátané práve raz.

Z nášho rozdelenia vidíme, že celkový súčet v tabuľke bude ( 6 \cdot 8 ) + stred. V strede teda chceme mať čo najväčšie číslo, aby sme mali celkový súčet čo najväčší. Aké najväčšie číslo vieme použiť v jednom políčku tabuľky?

Kedže každá trojica má súčet práve 6 a v každom políčku máme kladné celé číslo, tak najväčšie číslo dosiahneme tak, že zvyšné dve budú najmenšie možné. Najmenšie kladné celé číslo je 1, takže najväčšie číslo v políčku bude 6 - 1 - 1 = 4. V strede teda bude najviac 4. V takomto prípade bude mať naša tabuľka súčet ( 6 \cdot 8 ) + 4 = 52.

Teraz keď sme dokázali, že 52 je najväčší možný súčet v tabuľke, tak nám stačí nájsť jedno vyplnenie tabuľky také, že spĺňa zadanie a má súčet 52. Tu sú dve ukážky takéhoto vyplnenia tabuľky:

Odpoveď: Najväčší možný súčet čísel v tabuľke je 52.

Na úvod sa zamyslime nad počtom cifier dvojnásobku nášho hľadaného čísla. Najväčšie štvorciferné číslo je 9999, takže najväčší možný dvojnásobok je 19998. Bude mať teda štyri alebo päť cifier. Vieme však, že toto číslo je dvojnásobok a zároveň palindróm. Keďže je dvojnásobok, bude isto párne a teda bude končíť na párnu cifru. Keďže je to palindróm tak má prvú a poslednú cifru rovnakú. Daný dvojnásobok teda musí začínať na párnu cifru, čo 1 nie je. Všetky prípustné päťciferné čísla však začínajú 1, náš dvojnásobok teda bude mať len štyri cifry.

Zadanie si teraz môžeme zapísať pod seba:

\begin{matrix} A & B & C & D \\ & & \cdot & 2 \\\hline E & F & F & E \end{matrix}

ABCD je naše hľadané číslo, jeho cifry sú navzájom rôzne a platí A+B+C+D = 16. Číslo EFFE je jeho dvojnásobok, pričom o E sme už zistili, že je to párna cifra.

Odrazme sa práve od E, toho na začiatku. Najväčší prechod cez desiatku, ktorý môžeme dostať pri násobení dvomi je 1. (9 \cdot 2 + 1 = 19.) O E na začiatku teda platí buď E = 2 \cdot A alebo E = 2 \cdot A + 1. My však vieme, že E je párne, čomu druhá možnosť nevyhovuje.

Preskočme teraz s novým zistením na koniec. A a D sú rôzne cifry, ktoré keď vynásobíme dvomi, dajú číslo končiace tou istou cifrou (E). Pri jednom násobení teda príde k prechodu cez 10, v druhom nie. Vidíme, že pri násobení nepribúdajú cifry, takže bez prechodu bude násobenie A. Máme 2 \cdot A = E a 2 \cdot D = 10 + E = 10 + 2 \cdot A, čo znamená, že D = 5 + A.

Pokračujme teraz k druhej pozícii odzadu. Keďže pri násobení D máme prechod cez desiatku, vidíme, že F bude nepárne. Dvojnásobok C bude končiť párnou cifrou, čo sa nám pričítaním 1 zmení. Túto myšlienku však vieme využiť aj naopak. Aby F, teraz druhá cifra, bolo nepárne, nestačí nám len vynásobiť B dvomi. Musíme pripočítať ešte prechod cez 10, ku ktorému musí dôjsť pri násobení C.

Spomeňme si teraz na to, že pri násobení A nepripočítavame prechod. Platí teda 2 \cdot B + 1 = F a 2 \cdot C + 1 = 10 + F = 10 + 2 \cdot B + 1, odkiaľ vieme dopočítať C = B + 5.

Vráťme sa teraz k podmienke s ciferným súčtom. Tá hovorí, že A+B+C+D=16. My však vieme, že D = A+5 a C = B + 5. Takže A + B + B+5 + A+5 = 16, odkiaľ 2 \cdot (A+B) = 6. Súčet A a B je teda 3. Keďže sú nenulové, musia byť 1 a 2, len nevieme v akom poradí.

Overme teda obe možnosti. Ak A=1 a B=2 dostávame C=7 a D = 6. Cifry sú rôzne a ich súčet sedí. 1276 \cdot 2 = 2552, čo je palindróm. Naopak, pre A=2 a B=1 dostávame C=6 a D=7. Cifry ani ich súčet sa nezmenili, zostáva overiť dvojnásobok. 2167 \cdot 2 = 4334, čo je opäť palindróm. Máme teda dve riešenia.

Odpoveď: Hľadané štvorciferné číslo môže byť 1276 alebo 2167.

Pozrime sa detailnejšie na cesty vlakov:

• najprv oba naraz vyrazia z hradu,
• potom oba naraz prídu do dediny,
• osobák ide z dediny do hradu, zatiaľ čo rýchlik ide z dediny do mesta a naspäť do dediny,
• rýchlik ide z dediny a na hrad príde o 20 minút neskôr ako osobák.

Každý z vlakov šiel z hradu do dediny a naspäť a rýchlik si k tomu ešte pridal cestu z dediny do mesta a naspäť. Rýchlika táto cesta z dediny do mesta a naspäť stála 20-minútové zdržanie. Keďže cesta z dediny do mesta a z mesta do dediny trvá rýchliku rovnako dlho, bude to 20:2=10​ minút. Vieme, že rýchlik bol v meste o 7\text{:}00, keďže tam vtedy nakladal druhú skupinu študentov. Z toho teda vyplýva, že v dedine musel byť rýchlik o 6\text{:}50​, keďže mu cesta z dediny do mesta trvá 10​ minút. Ak prvá skupina vyrazila o 6\text{:}00​ a vlaky boli v dedine v rovnaký čas (6\text{:}50​), znamená to, že chôdza musela študentom prvej skupiny zabrať 50 minút.

Iné riešenie

Označme si hľadaný čas chôdze študentov z mesta do dediny t_\text{chôdza}, čas cesty vlaku z dediny na hrad t_{DH}​, čas cesty rýchlikov z mesta do dediny t_{MD}.

Potom si čas t od odchodu prvej skupiny z mesta (6\text{:}00​) do príchodu druhej skupiny do hradu vieme vyjadriť ako

t = t_\text{chôdza} + t_{DH} + 20,\\ t = 60 + t_{MD} + t_{DH}.

Z čoho vyplýva

t_{chôdza} = t_{MD} + 40.

Tu nám zostal jeden neznámy člen t_{MD}. V takomto prípade (keď nám zostane neznáma, ktorú si už nevieme z ničoho doteraz použitého vyjadriť), je vhodné zamyslieť sa, čo zo zadania sme v rovniciach ešte nevyužili. Nevyužili sme fakt, že vlaky vyrazili naraz, a teda jednoduchou úvahou z riešenia vyššie, si vieme za t_{MD} dosadiť 10 minút, čím nám vyjde rovnaké riešenie ako vyššie, a to 50 minút.

Odpoveď: Študentom trvalo prejsť peši z mesta do dediny 50​ minút.

Keďže nsn(AB, BA) = 5 \cdot AB, tak 5 \cdot AB je násobok BA. Ak by BA nebolo deliteľné 5, tak by BA muselo byť nejakým deliteľom AB. To by však znamenalo, že nsn(AB, BA) = AB, čo podľa zadania neplatí. To znamená, že BA musí byť násobok 5.

Aby nejaké číslo bolo deliteľné 5, musí sa jeho posledná cifra rovnať 0 alebo 5. Keďže však AB aj BA sú dvojciferné čísla, tak cifry A, B sú nenulové. To znamená, že aby BA bolo deliteľné 5, musí byť cifra A rovná 5.

Z prvej rovnice vieme, že AB je deliteľné A + B. AB = 10 \cdot A + B = 50 + B a A + B = 5 + B. Keďže 5 + B delí 50 + B, potom 5 + B delí aj 50 + B - (5 + B) = 45. Keďže B je cifra a číslo BA je dvojciferné, tak B je aspoň 1 ale najviac 9, takže 5 + B je aspoň 6, ale najviac 14. Delitele čísla 45 sú 1, 3, 5, 9, 15 a 45, z toho je len jeden väčší ako 6 ale menší ako 14, a to 9, ktorý dostaneme ak B = 4.

Trikové riešenie

Najprv dokážeme známe tvrdenie, že NSD(a,b) \cdot nsn(a,b) = a \cdot b. Samotné riešenie príkladu sa začne až v 3. odseku.

Nech a = a’ \cdot NSD(a,b) a b = b’ \cdot NSD(a,b), teda a’ je súčin prvočísel, ktoré obsahuje len a a b’ je súčin prvočísel, ktoré obsahuje len b. Najmenší spoločný násobok a a b sa počíta ako súčin prvočísel ktoré obsahuje len a krát súčin prvočísel ktoré obsahuje len b, krát súčin prvočísel, ktoré obsahuje a aj b. To znamená, že nsn(a,b) = a’ \cdot b’ \cdot NSD(a,b). Po prenásobení rovnosti NSD(a,b) a dosadení a’ \cdot NSD(a,b) = a a b’ \cdot NSD(a,b) = b dostávame NSD(a,b) \cdot nsn(a,b) = a \cdot b.

Zadané rovnice prenásobime medzi sebou, pravé strany spolu a ľavé strany spolu. Dostaneme

\begin{aligned} NSD(AB, BA) \cdot nsn(AB,BA) = (A + B) \cdot 5 \cdot (AB). \end{aligned}

Ľavá strana sa z dokazovaného tvrdenia rovná AB \cdot BA.

\begin{aligned} AB \cdot BA &= (A+B) \cdot 5 \cdot (AB), \\ BA &= 5 \cdot (A+B). \end{aligned}

Zápis BA sa dá rozpísať ako 10 \cdot B + A.

\begin{aligned} 10 \cdot B + A &= 5 \cdot A + 5 \cdot B, \\ 5 \cdot B &= 4 \cdot A. \end{aligned}

Cifry A a B nemôžu byť 0, inak by AB alebo BA nebolo dvojciferné číslo. Z rovnice je vidno, že 4 \cdot A je deliteľné piatimi, avšak to je možné len A je deliteľné piatimi. Jediná nenulová cifra deliteľná piatimi je 5, čo bude naše A. Po dosadení A = 5 do rovnosti 5 \cdot B = 4 \cdot A a predelení 5 dostávame B = 4.

Odpoveď: Jediná dvojica cifier A, B vyhovujúca zadaniu je A = 5 a B = 4.

Najprv si rozmyslime, čo musí platiť pre náš hľadaný bod Z​. Vieme, že je to stred súmernosti medzi bodmi A​ a D​. Zo stredovej súmernosti vieme, že potom musia byť body A​, Z​ aj D​ na jednej priamke a zároveň pre vzdialenosti medzi týmito bodmi platí |AZ|=|ZD|. Teda vidíme, že Z​ musí byť stred úsečky AD. Teraz skúsime nájsť tento bod.

Všimnime si, že bod A​ je stredovo súmerný podľa X​ s bodom B​ a zároveň bod C​ je stredovo súmerný s bodom D​ tiež podľa X​. Z toho nám vyplýva, že celá úsečka BC je stredovo súmerná s úsečkou AD​ podľa X​. 

Ďalej vieme, že Y​ je stred súmernosti podľa ktorej sa nám bod B​ zobrazí do bodu C​. Preto musí byť bod Y​ stredom úsečky BC.

Teraz si môžeme všimnúť, že stred úsečky BC​ sa nám v stredovej súmernosti podľa X​ musí zobraziť do stredu úsečky AD​, keďže tieto úsečky sú súmerné práve podľa bodu X​. Teda ak zobrazíme bod Y​ v stredovej súmernosti podľa X​ nájdeme stred úsečky AD​, čo je náš hľadaný bod Z​.

Ešte by sme sa mali zamyslieť nad tým, čo by sa stalo ak by úsečky BC​ a AD neexistovali, teda  by body B​ a C​ a body A​ a D boli totožné. V takomto prípade je B​ zároveň bod Y​. Podobne bod Z​ musí byť zároveň bod A​, lebo bod A​ sa zobrazí podľa Z​ sám do seba. No a keďže vieme, že bod B​ sa nám podľa X​ zobrazí do A, tak potom bod Z tiež vieme nájsť ako obraz bodu Y​ podľa X​. 

Odpoveď:  Hľadaný bod Z​ vieme nájsť ako obraz bodu Y​ v stredovej súmernosti podľa bodu X​.

Komentár

Väčšina z vás prišla k správnemu riešeniu. Napriek tomu, len málo riešení bolo ohodnotených na plný počet bodov. Najčastejšou chybou, na ktorú by sme chceli upozorniť bolo, že ste nevyriešili všetky možné konfigurácie bodov X,Y​ a A​. Veľa z vás úlohu dokazovalo pomocou súmernosti trojuholníkov XAD​ a XBC​ alebo pomocou rovnobežníka BCAD​. V takýchto prípadoch bolo potrebné prešetriť aj možnosti, keď nám tieto útvary nevznikli. 

Bodovanie

Dobrým začiatkom pri takomto príklade je nakresliť niektorý z prípadov (napr. pre n = 7) a skúsiť si strany a uhlopriečky vyfarbiť. Bez ohľadu na to, či sa nám to podarí vieme prísť k niekoľkým záverom. Ako prvé si môžeme uvedomiť, že každý trojuholník vieme vyfarbiť inou farbou. Ak dva trojuholníky majú rovnakú farbu a žiadnu spoločnú stranu, prefarbením jedného z nich nič nepokazíme. Ak by mali rovnakú farbu aj spoločnú stranu, tak si kraje tejto úsečky označíme A a B a máme dva možné body C, čo podľa zadania nemôžeme.

Ako prvé teda vidíme, že každá uhlopriečka a strana musí byť jednej z niekoľkých farieb. Ich počet označíme f. Každej farby sú tri strany jedného trojuholníka, takže všetkých uhlopriečok musí byť 3 \cdot f, čo je násobok 3. Počet všetkých úsečiek v n-uholníku je n \cdot (n-1) : 2. Overíme, ktoré n túto podmienku spĺňajú.

n = 7{:}~~~ 7 \cdot 6 : 2 = 21 = 3 \cdot 7,\\ n = 8{:}~~~ 8 \cdot 7 : 2 = 28 = 3 \cdot 9 + 1,\\ n = 10{:}~~~ 10 \cdot 9 : 2 = 45 = 3 \cdot 15,\\ n = 11{:}~~~ 11 \cdot 10 : 2 = 55 = 3 \cdot 18 + 1,\\ n = 12{:}~~~ 12 \cdot 11 : 2 = 66 = 3 \cdot 22.

Teraz by sme mohli skúsiť nakresliť si 7-,\, 10-,\, 12-uholníky a vyfarbiť im uhlopriečky, aby sme overili, že to ide. Pri 10- a 12-uholníku sa nám to však nepodarí. Prečo?

Vráťme sa späť k trojuholníkom. Z každého vrcholu trojuholníka vychádzajú 2 strany. Teda z každého vrcholu n-uholníka musia vychádzať dve hrany za každú farbu trojholníka, ktorému patrí daný vrchol. Z vrcholu n-uholníka vychádza n-1 strán a uhlopriečok, ktoré chceme rozdeliť na dvojice. To ide iba ak je n-1 párne a teda n je nepárne. To vylučuje n = 10 a n = 12.

Pre správnosť by sme mali ešte overiť, že 7-uholník zadanie spĺňa. Mohlo by sa nám stať, že sme len nejaké pravidlo vynechali a že v skutočnosti nefunguje ani tento prípad. Najľahšie overenie je nájsť správne ofarbenie -- napríklad ako na obrázku.

Odpoveď: Uhlopriečky a strany vieme podľa zadania ofarbiť len v 7-uholníku.

Komentár

Aj keď sa to tak z riešenia nemusí zdať, príklad sa ukázal byť pomerne náročný a odovzdalo ho len málo riešiteľov. Tí mali poväčšinou správnu myšlienku s rozdeľovaním na trojuholníky, no využili ju len na overenie deliteľnosti tromi. Ako však môžeme vidieť tento postup nevylúči 10-uholník ani 12-uholník.

Niektorým z Vás by mohlo ešte vŕtať v hlave, čo s prípadom 9-uholníka, ktorý sa v zadaní nevyskytuje. Po overení výpočtov prídete aj sami na to, že by mohol zadaniu vyhovovať. A skutočne, ak si k tomu na chvíľu sadnete, mohlo by sa Vám podariť nájsť správne ofarbenie strán a uhlopriečok.

Kľúčová myšlienka v tomto príklade bola pozrieť sa na prvočíselné rozklady čísel a, b, c. Nech p_1, p_2, \dots, p_k sú všetky (rôzne) prvočísla, ktoré sú v prvočíselnom rozklade aspoň jedného z a, b. Teraz vieme čísla a, b jednoznačne zapísať ako prvočíselný rozklad:

​a=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} a b=p_1^{b_1}p_2^{b_2}\dots p_k^{b_k},

kde a_1,\dots , a_k, b_1, \dots, b_k sú nezáporné celé čísla.

Každé vyhovujúce c sa bude tiež skladať len z týchto prvočísel. Ak by obsahovalo aj nejaké iné prvočíslo p, nemohlo by platiť, že c|ab​ (c delí ab), pretože potom by p muselo deliť aj ab a to vieme, že nedelí. Teda hľadáme c tiež v tvare c=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}, kde c_1,\dots,c_k sú opäť nezáporné celé čísla.

Podmienky zo zadania sa dajú vyjadriť aj tak, že \frac{ab}{c}, \frac{ac}{b}, \frac{bc}{a}majú všetky byť všetky celé čísla. Keď to prepíšeme pomocou našich prvočíselných rozkladov dostaneme:

​p_1^{a_1+b_1-c_1}p_2^{a_2+b_2-c_2}\dots p_k^{a_k+b_k-c_k},

​p_1^{a_1+c_1-b_1}p_2^{a_2+c_2-b_2}\dots p_k^{a_k+c_k-b_k},

​p_1^{b_1+c_1-a_1}p_2^{b_2+c_2-a_2}\dots p_k^{b_k+c_k-a_k}.

Tieto čísla budú celé práve vtedy, ak každý exponent bude nezáporný. Z toho vyplýva, že c bude vyhovujúce práve vtedy, ak platia nasledujúce nerovnosti:

a_i+b_i \ge c_i,

​a_i+c_i \ge b_i,

​b_i+c_i \ge a_i.

pre každé 1 \le i \le k.

Pre konkrétne i môžeme bez újmy na všeobecnosti predpokladať, že a_i \le b_i. Z prvých dvoch nerovníc dostávame a_i + b_i \ge c_i \ge b_i-a_i. Ľahko sa dá vidieť, že každé c_i z tohto intervalu bude spĺňať aj tretiu nerovnosť.

Keďže b_i \ge a_i tak c_i \ge b_i - a_i \ge 0. To znamená, že b_i+c_i \ge b_i \ge a_i. Takže možnosti pre c_i sú všetky celé čísla od b_i-a_i do a_i+b_i. To je (a_i+b_i)-(b_i-a_i)+1=2a_i+1 možností, čo je nepárne číslo.

Takže vidíme, že máme nepárny počet možností pre každý exponent. Keďže každý exponent môžeme vybrať úplne nezávisle, celkový počet možností bude iba súčin počtov možností pre každý z nich. No a súčin nepárnych čísel je vždy nepárny.​

Iné riešenie

Nech d je najväčší spoločný deliteľ a, b. Potom vieme nájsť nesúdeliteľné celé čísla f,g také, že a=df a b=dg. Podľa zadania má platiť:

1. a|bc, teda df|dgc čo je ekvivalentné s f|gc. Keďže f,g sú nesúdeliteľné, znamená to, že f|c.
2. ​b|ac, teda dg|dfc. Podobným spôsobom dostaneme g|c.
3. c|ab, teda c|d^2fg.

Keďže f,g sú nesúdeliteľné, 1. a 2. nám dokopy dávajú fg|c. To môžeme zapísať ako c=kfg a dosadiť do 3.:

​kfg|d^2fg,​

​k|d^2.

Môžeme vidieť, že všetky takéto c spĺňajú všetky podmienky:

1. a|bc \iff df|dg\cdot kfg \iff 1|kg^2 platí.
2. ​b|ac \iff dg|df\cdot kfg \iff 1|kf^2 platí.
3. c|ab \iff kfg|d^2fg \iff k|d^2 platí.

Teda nám stačí nájsť počet možností pre k, čo je iba počet deliteľov d^2. Konkrétne teda ukázať, že tento počet je nepárny.

Toto sa dá ukázať viacerými spôsobmi. Vieme napríklad ukázať, že máme rovnako veľa deliteľov menších ako d a väčších ako d. Ku každému deliteľu t\lt d môžeme priradiť deliteľ \frac{d^2}{t}\gt d. Týmto pokryjeme všetky delitele väčšie ako d, pretože každý z nich sa dá zapísať ako \frac{d^2}{t} pre nejaké t\lt d. Takže máme niekoľko deliteľov menších ako d a rovnako veľa väčších ako d. To nám dokopy dáva párny počet, ale ešte sme nazapočítali d, ktorý je tiež deliteľ. Spolu s ním máme nepárne veľa deliteľov.

Týmto sme ukázali, že máme nepárny počet možností pre c.​​