Kezdőlap


Feladat:	1998. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	1999/február, 71 - 72. oldal		PDF \| MathML
Témakör(ök):	Interpolációs polinomok, Egész együtthatós polinomok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1999/február: 1998. évi Kürschák matematikaverseny 2. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Először olyan $p$ polinomot mutatunk, amely az egymástól különböző $a_{1}$ , $a_{2}$ , $...$ , $a_{n}$ helyeken rendre az egymástól nem feltétlenül különböző $b_{1}$ , $b_{2}$ , $...$ , $b_{n}$ értékeket veszi fel. Ehhez tekintsük $i = 1$ , 2, $...$ , $n$ esetén a következő $p_{i}$ polinomot:

\begin{matrix} p_{i} (x) = \prod_{\begin{matrix} j \neq i \\ 1 \leq j \leq n \end{matrix}}^{} \frac{x - a_{j}}{a_{i} - a_{j}} . \end{matrix}

Világos, hogy

p_{i} (a_{i}) = 1

és

p_{i} (a_{j}) = 0

, ha

j \neq i

. Ezért a

p (x) = b_{1} \cdot p_{1} (x) + ... + b_{n} \cdot p_{n} (x)

összefüggéssel definiált polinom, az ún. Lagrange-féle interpolációs polinom, megfelelő lesz. Könnyen látható, hogy ezen

p

polinom fokszáma legfeljebb

n - 1

. Azonban

p

még akkor sem lesz mindig egész együtthatós, ha

a_{1}

...

a_{n}

és

b_{1}

...

b_{n}

egész számok.
Legyen most

a_{1} = 1

a_{2} = 2

...

a_{n} = n

. Milyen

b_{1}

...

b_{n}

egész értékek mellett tudunk egyszerűen következtetni arra, hogy a

p

polinom együtthatói egész számok? A

p

polinom minden együtthatója olyan racionális szám, amelynek a nevezője valamilyen

1 \leq i \leq n

indexre

\begin{matrix} \begin{matrix} \prod_{\begin{matrix} j \neq i \\ 1 \leq j \leq n \end{matrix}}^{} (a_{i} - a_{j}) & = (i - 1) (i - 2) ... (i - (i - 1)) (i - (i + 1)) ... (i - n) = \\ = {(- 1)}^{n - i} (i - 1)! (n - i)! \end{matrix} \end{matrix}

alakú, számlálója pedig ugyanekkor

b_{i}

-vel osztható egész szám. Könnyen látható, hogy az így adódó nevezők mindegyike osztója az

N = {[(n - 1)!]}^{2}

számnak. Ha tehát a

b_{i}

értékek mindegyike osztható

N

-nel, akkor a fenti konstrukcióval létrehozott

p

polinom egész együtthatós lesz.
Az általunk keresett polinomnak azonban az előírt helyeken 2-hatvány értékeket kell felvennie, azok pedig nem oszthatók

N

-nel, ha

n \geq 4

. Hogyan lehet ezen segíteni? Válasszunk ki

n

darab különböző 2-hatványt, ami ugyanannyi ‐ mondjuk

m

‐ maradékot ad

N

-nel osztva. Ezt megtehetjük, hiszen végtelen sok különböző 2-hatvány van. Legyenek ezek

c_{1}

c_{2}

...

c_{n}

, és tekintsük a

b_{i} = c_{i} - m

(

1 \leq i \leq n

) számokat. Ezekre igaz, hogy

b_{i}

osztható

N

-nel, létezik tehát olyan egész együtthatós polinom, amelyre

p (i) = b_{i}

minden 1 és

n

közé eső

i

egész számra. Ennek a

p

polinomnak konstans tagját

m

-mel megnövelve olyan, továbbra is egész együtthatós

p^{*}

polinomhoz jutunk, amelyre

p^{*} (i) = c_{i}

. Ezzel a feladat állítását igazoltuk.

Megjegyzések. 1. A megoldásból kitűnik, hogy különböző 2-hatványok helyett különböző 3-hatványokat vagy éppen különböző prímszámokat is előírhattunk volna a keresett polinom 1, 2,

...

n

helyen felvett értékeiként. Sőt, még ennél is tovább mehetünk. Mivel

\begin{matrix} (\binom{n - 1}{i - 1}) = \frac{(n - 1)!}{(i - 1)! (n - i)!} \end{matrix}

egész szám, az

a_{1} = 1

a_{2} = 2

...

a_{n} = n

alappontokra épített Lagrange-féle interpolációs polinom együtthatói már akkor is egész számok, ha minden

b_{i}

osztható

(n - 1)!

-sal. A skatulya-elv szerint

(n - 1) (n - 1)! + 1

szám között mindig található

n

olyan, amelyik

(n - 1)!

-sal osztva ugyanolyan maradékot ad. Megfogalmazhatjuk tehát a következő, a feladatban szereplőnél erősebb állítást.
Legyen

H

egy legalább

(n - 1) (n - 1)! + 1

elemű egész számokból álló halmaz. Ekkor létezik olyan, legfeljebb

(n - 1)

-ed fokú egész együtthatós polinom, amelynek az 1, 2,

...

n

helyeken felvett értékei a

H

különböző elemei.