Kategórie:
5
6
7
8
9

Zadanie

Každý z 15 kameňov je označený nejakým číslom od 2 po 2020, pričom čísla žiadnych dvoch kameňov nemajú spoločného deliteľa väčšieho ako 1. Dokážte, že aspoň jedno z čísel na kameňoch je prvočíslo.

Vzorové riešenie

Opravovali: Qwedux, david

Podmienka "Žiadne dve čísla nemajú spoločného deliteľa väčšieho ako 1", je veľmi dobrá keď sa na ňu začneme pozerať cez prvočísla. Hovorí totižto, že ak už jedno z pätnástich čísel obsahuje nejaké prvočíslo v prvočíselnom rozklade, tak žiadne iné z našich pätnástich čísel toto prvočíslo v prvočíselnom rozklade mať nebude.

Pozrime sa na nejaké konkrétne číslo m v našej pätnástici. Ak má v prvočíselnom rozklade dve rôzne prvočísla p, q a p < q, tak môžme zapísať m = p \cdot q \cdot z, kde z je nejaké prirodzené číslo. m totižto nemusí byť súčinom len dvoch prvočísel. Vďaka podmienke ale vieme, že žiadne iné číslo v našej pätnástici nie je deliteľné p, pričom p\cdot p < p\cdot q \cdot z, nakoľko p < q \cdot z, keďže z je aspoň 1. To ale znamená, že p\cdot p je tiež číslo od 2 po 2020 a teda naše m ním môžme nahradiť. Takto sme sa teda dostali k tomu, že každé číslo v našej pätnástici môžme zameniť za druhú mocninu najmenšieho prvočísla v ňom a tým dostať novú vyhovujúcu pätnásticu. Keď sa však pozrieme na druhé mocniny prvých pätnástich prvočísel, tak zistíme, že 47^2 = 2209, pričom 47 je pätnáste prvočíslo. To znamená, že ani z prvých pätnástich prvočísel nevieme poskladať vyhovujúcu pätnásticu. To znamená, že nemôže existovať žiadna vyhodujúca pätnástica, nakoľko druhá mocnina ľubovoľného prvočísla väčieho ako 47 by bola viac ako 2209.