Zadanie
Mr. Mira pozvali do školy na besedu. Pre žiakov si chce pripraviť nasledovnú úlohu. Povie im, že si myslí monický polynóm1 stupňa 2017 s celočíselnými koeficientmi. Potom im povie $k$ celých čísel $n_1,\,n_2,\,\dots,\,n_k\text{,}$ hodnotu súčinu $P(n_1)P(n_2)\dots P(n_k)$ a „Easy!“ Úlohou žiakov je nájsť polynóm, ktorý vyhovuje týmto podmienkam. Mr. Miro navyše chce, aby existoval len jeden polynóm, ktorý vyhovuje spomenutým podmienkam. Nájdite najmenšie prirodzené číslo $k$, pre ktoré sa Mr. Mirovi môže podariť pripraviť takúto úlohu.
Monický polynóm je polynóm s vedúcim koeficientom $1$, teda v tvare $x^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0$. ↩
Ukážeme, že riešením je \(k=2017\). Na to, aby sme to dokázali, potrebujeme urobiť dve veci. Nájsť konštrukciu pre \(k=2017\) (t. j. polynóm a 2017 čísel, ktoré Mr. Miro povie deťom) a ukázať, že pre menšie \(k\) to Mr. Miro nevie spraviť.
Prepokladajme preto, že \(k\le 2016\). Nech si Mr. Miro myslí polynóm \(P(x)\). Ukážeme, že v tomto prípade úloha, ktorú Mr. Miro zadá nebude mať nikdy jednoznačné riešenie. A to tak, že nájdeme iný polynóm, ktorý vyhovuje podmienkam. Bude to polynóm \(Q(x)=P(x)+(x-n_1)(x-n_2)\cdots(x-n_k)\). Zjavne \(Q(x)\) má celočíselné koeficienty (aj \(P(x)\) mal) a je monický stupňa \(2017\), pretože \(k\le 2016\). Tak isto platí, že \(Q(n_i)=P(n_i)\), pre všetky \(1\le i\le k\). Preto aj \(P(n_1)P(n_2)\cdots P(n_k)=Q(n_1)Q(n_2)\cdots Q(n_k)\). To znamená, že polynóm \(Q(x)\) vyhovuje všetkým podmienkam Mr. Mira, a preto riešenie nie je jednoznačné.
Teraz potrebujeme zostrojiť polynóm a nájsť 2017 čísel, tak aby úloha Mr. Mira mala jenoznačné riešenie. Dobré bude položíť súčin \(P(n_1)P(n_2)\cdots P(n_{2017})=1\), lebo potom bude málo možností na \(P(n_i)\). Presnejšie dve – pre všetky \(i\) bude \(P(n_i)=\pm 1\).
Mirov polynóm môže byť preto \(P(x)=(x-n_1)(x-n_2)\cdots(x-n_{2017})+1\), pre vhodnú voľbu čísel \(n_i\). Bolo by dobré, keby deti vedeli vylúčiť možnosť \(P(n_i)=-1\). Na to použijeme takú vec, že pre polynómy s celočíselnými koeficientami platí \(a-b\mid P(a)-P(b)\). Ak teda máme \(a,\,b\) také, že \(P(a)=1\) a \(P(b)=-1\), tak nutne \(a-b\mid 2\). Preto položíme \(n_i=3i\), pre všetky \(1\le i \le 2017\). Zjavne potom nemôže nastať situácia, že \(P(n_i)=1\) a \(P(n_j)=-1\), pre nejaké \(i,\,j\). A keďže nemôže pre všetky \(i\) platiť, že \(P(n_i)=-1\), lebo \(2017\) je nepárne, tak nutne naozaj \(P(n_i)=1\) pre všetky \(1\le i \le 2017\).
Otázka je tá, či je týmto už polynóm jednoznačne určený. Odpoveď je áno, pretože \(P(x)-1\) musí mať za korene všetky čísla \(3,\,6,\,9,\,\dots,\, 3\cdot 2017\) Preto nutne \(P(x)-1=(x-3)(x-6)\cdots(x-2017\cdot 3)R(x)\), pre nejaký polynóm \(R(x)\). No keďže \(P(x)-1\) je monický polynóm stupňa \(2017\), tak nutne \(R(x)=1\). Samozrejme, ak je jednoznačne určený polynóm \(P(x)-1\), tak z neho vieme jednoznačne určiť \(P(x)\). Našli sme preto polynóm a \(2017\) čísel, pre ktoré má úloha od Mr. Mira jediné riešenie. Záver je, že \(k=2017\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.