Az A. 898. feladat (2025. január)

A. 898. Legyen \(\displaystyle n\) egy adott pozitív egész szám. Ana és Bob a következő játékot játsszák: Ana választ egy egész együtthatós \(\displaystyle n\)-edfokú \(\displaystyle p\) polinomot. Bob minden egyes körben választhat egy pozitív egészekből álló véges \(\displaystyle S\) halmazt, Ana pedig egy listával válaszol, mely a \(\displaystyle p\) polinom \(\displaystyle S\) halmazon felvett értékeit tartalmazza multiplicitással (növekvő sorrendben). Határozzuk meg \(\displaystyle n\) függvényében azt a legkisebb \(\displaystyle k\) pozitív egész számot, melyre Bob mindig ki tudja találni a \(\displaystyle p\) polinomot legfeljebb \(\displaystyle k\) kör alatt.

Javasolta: Andrei Chirita (Cambridge)

(7 pont)

A beküldési határidő 2025. február 10-én LEJÁRT.

Belátjuk, hogy rögzített \(\displaystyle n\) pozitív egész esetén lehet találni egészek egy olyan véges \(\displaystyle S\) halmazát, melyre \(\displaystyle P(S)=Q(S)\)-ből következik, hogy \(\displaystyle P=Q\) tetszőleges \(\displaystyle n\)-edfokú \(\displaystyle P,Q\in \mathbb{Z}\left[X\right]\) polinomok esetén.

Ezt az állítást felhasználva Bob egyetlen kérdéssel ki tudja találni az Ana által gondolt polinomot felhasználva Ana válaszát, \(\displaystyle P(S)\)-t: először az összes lehetséges \(\displaystyle (x_0,P(x_0))\), \(\displaystyle (x_1,P(x_1)\),..., \(\displaystyle (x_n,P(x_n))\) kombinációra (ahol \(\displaystyle x_i\)-t \(\displaystyle S\)-ből, a hozzá tartozó \(\displaystyle P(x_i)\) értéke \(\displaystyle P(S)\)-ből választja) konstruál egy megfelelő \(\displaystyle Q\) polinomot a Lagrange-interpoláció segítségével. Ezután megvizsgálja, hogy teljesül-e \(\displaystyle P(S)=Q(S)\). A fenti állítás alapján ha teljesül az egyenlőség, akkor \(\displaystyle P=Q\), így véges sok próbálkozás után fog találni egy megfelelő polinomot, amely meg fog egyezni az Ana által gondolt polinommal.

Az eredeti állítás bizonyításához tekintsünk különböző \(\displaystyle x_1\), \(\displaystyle x_2\),..., \(\displaystyle x_m\) egészeket, ahol \(\displaystyle m=7n+1\). Tegyük fel, hogy \(\displaystyle y_1\), \(\displaystyle y_2\),..., \(\displaystyle y_m\) az \(\displaystyle x_1\), \(\displaystyle x_2\),..., \(\displaystyle x_m\) egy permutációja, melyre teljesül, hogy \(\displaystyle P(x_i)=Q(y_i)\) minden \(\displaystyle 1\le i \le m\) esetén.

Ha legalább \(\displaystyle n+1\) esetben teljesül, hogy \(\displaystyle x_i=y_i\), akkor \(\displaystyle P-Q\)-nak legalább \(\displaystyle n+1\) gyöke van, így (mivel a foka legfeljebb \(\displaystyle n\)), azonosan nulla, azaz \(\displaystyle P=Q\). Tegyük fel tehát, hogy nem ez a helyzet.

Ekkor tekintsük azokat az \(\displaystyle \{x_i,y_i\}\) (rendezetlen) párokat, ahol \(\displaystyle x_i\neq y_i\). A fenti feltevés alapján legalább \(\displaystyle 6n+1\) darab ilyen pár van. Mivel minden párnak legfeljebb két másik párral lehet közös eleme, így ha a lehető legtöbb, \(\displaystyle l\) darab diszjunkt párt választunk, akkor \(\displaystyle 3l\ge 6n+1\), azaz \(\displaystyle l\ge 2n+1\). Ez azt jelenti, hogy tudunk választani \(\displaystyle 2n+1\) darab \(\displaystyle \{a_1,b_1\}\), \(\displaystyle \{a_2,b_2\}\),..., \(\displaystyle \{a_{2n+1},b_{2n+1}\}\) diszjunkt párt.

Legyen \(\displaystyle P(X)=c_nX^n+c_{n-1}X^{n-1}+...+c_0\) és \(\displaystyle Q(x)=d_nX^{n}+d_{n-1}X^{n-1}+...+d_0\). Ekkor a \(\displaystyle P(a_i)=Q(b_i)\) egyenlőségekből következik, hogy a

\(\displaystyle c_n a_1^n + c_{n-1} a_1^{n-1} + \dots + c_0 = d_n b_1^n + d_{n-1} b_1^{n-1} + \dots + d_1 b_1 + d_0,\\ c_n a_2^n + c_{n-1} a_2^{n-1} + \dots + c_0 = d_n b_2^n + d_{n-1} b_2^{n-1} + \dots + d_1 b_2 + d_0, \\ \phantom{c_n a_2^n + c_{n-1} a_2^{n-1} + \dots + c_0 =} \vdots \phantom{= d_n b_2^n + d_{n-1} b_2^{n-1} + \dots + d_1 b_2 + d_0} \\ c_n a_{2n+1}^n + c_{n-1} a_{2n+1}^{n-1} + \dots + c_0 = d_n b_{2n+1}^n + d_{n-1} b_{2n+1}^{n-1} + \dots + d_1 b_{2n+1} + d_0. \)

lineáris egyenletrendszer nemtriviális megoldása \(\displaystyle c_n\), \(\displaystyle c_{n-1}\), ..., \(\displaystyle c_1\), \(\displaystyle c_0-d_0\), \(\displaystyle d_n\),..., \(\displaystyle d_1\), azaz

\(\displaystyle \begin{vmatrix} a_1^n & a_1^{n-1} & \dots & a_1 & 1 & -b_1^n & -b_1^{n-1} & \dots & -b_1 \\ a_2^n & a_2^{n-1} & \dots & a_2 & 1 & -b_2^n & -b_2^{n-1} & \dots & -b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{2n+1}^n & a_{2n+1}^{n-1} & \dots & a_{2n+1} & 1 & -b_{2n+1}^n & -b_{2n+1}^{n-1} & \dots & -b_{2n+1} \end{vmatrix} =0. \)

Vagyis ha a fenti determináns nem nulla, akkor

\(\displaystyle c_n=c_{n-1}=\ldots=c_0-d_0=d_n=\ldots=d_1=0,\)

azaz \(\displaystyle P=Q\) (és ráadásul konstans polinomok, vagyis nem \(\displaystyle n\)-ed fokúak).

Ezután a kulcsmegfigyelés után a következő a célunk: szeretnénk találni egy olyan \(\displaystyle 7n+1\) elemű \(\displaystyle S\) halmazt, melyből akárhogy választunk különböző \(\displaystyle z_1\),..., \(\displaystyle z_{4n+2}\) elemeket, az

\(\displaystyle f(z_1,z_2,\dots,z_{4n+2})=\begin{vmatrix} z_1^n & z_1^{n-1} & \dots & z_1 & 1 & -z_2^n & -z_2^{n-1} & \dots & -z_2 \\ z_3^n & z_3^{n-1} & \dots & z_3 & 1 & -z_4^n & -z_4^{n-1} & \dots & -z_4 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ z_{4n+1}^n & z_{4n+1}^{n-1} & \dots & z_{4n+1} & 1 & -z_{4n+2}^n & -z_{4n+2}^{n-1} & \dots & -z_{4n+2} \end{vmatrix}\)

polinom értéke nem nulla. Természetesen maga az \(\displaystyle f(X_1,...,X_{4n+2})\) polinom nem azonosan nulla.

Végül ha

\(\displaystyle R(X_1,\dots,X_{m})=\prod_{1\le i_1,i_2,\dots,i_{4n+2}\le m}f(X_{i_1},X_{i_2},\dots,X_{i_{4n+2}}),\)

akkor az \(\displaystyle R\) polinom nem azonosan 0, így annyi a feladat, hogy találjunk különböző \(\displaystyle x_1\), \(\displaystyle x_2\),..., \(\displaystyle x_m\) egészeket, melyre \(\displaystyle R(x_1,...,x_m)\neq 0\).

Lemma: Bármely \(\displaystyle n\) pozitív egész szám és bármely nem azonosan nulla \(\displaystyle n\)-változós \(\displaystyle T(X_1,X_2,\dots,X_{n})\) polinomra léteznek különböző \(\displaystyle a_1,a_2,\dots,a_n\) egészek, melyekre

\(\displaystyle T(a_1,a_2,\dots,a_n)\ne 0.\)

Bizonyítás: Az állítás azonnal következik a kombinatorikus nullstellensatzból (ha a polinumunkat még megszorozzuk az \(\displaystyle X_i-X_j\) tényezőkkel, hogy a különbözőség technikai feltételétől megszabaduljunk), de a teljesség kedvéért adunk rá bizonyítást \(\displaystyle n\)-szerinti teljes indukcióval.

\(\displaystyle n=1\)-re triviális az állítás, mert egy nem azonosan nulla polinomnak csak véges sok gyöke van.

Az indukciós lépés bizonyításához írjuk a polinomot

\(\displaystyle T(X_1,X_2,\dots,X_{n+1})=X_{n+1}^dA_d(X_1,\dots,X_n)+X_{n+1}^{d-1}A_{d-1}(X_1,\dots,X_n)+\dots+A_0(X_1,\dots,X_n)\)

alakban, ahol \(\displaystyle A_d\), \(\displaystyle A_{d-1}\),..., \(\displaystyle A_0\) az \(\displaystyle X_1\), \(\displaystyle X_2\),..., \(\displaystyle X_n\) változók polinomjai. Mivel \(\displaystyle T\) nem azonosan 0, létezik olyan \(\displaystyle 0\le i\le d\), melyre az \(\displaystyle A_i\) polinom nem azonosan 0. Az indukciós feltevés szerint találhatók olyan egymástól páronként különböző \(\displaystyle a_1\), \(\displaystyle a_2\),..., \(\displaystyle a_n\) egészek, melyekre \(\displaystyle A_i(a_1,...,a_n)\neq 0\). Ekkor pedig a \(\displaystyle T(a_1,...,a_n,X)\) egyváltozós polinom sem azonosan 0, vagyis csak véges sok gyöke van, így \(\displaystyle a_{n+1}\)-et meg tudjuk választani a gyököktől és a véges sok \(\displaystyle a_1\), \(\displaystyle a_2\),..., \(\displaystyle a_n\) számtól különbözőnek, mellyel \(\displaystyle T(a_1,...,a_n,a_{n+1})\neq 0\), és ezzel a bizonyítás teljes.

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Forrai Boldizsár.
6 pontot kapott:	Varga Boldizsár.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2025. januári matematika feladatai