Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 727. feladat (2018. május)

A. 727. Tetszőleges \(\displaystyle (x_1,\ldots,x_n)\) véges sorozatra jelölje \(\displaystyle N(x_1,\ldots,x_n)\) az olyan \(\displaystyle (i,j)\) indexpárok számát, amelyekre \(\displaystyle 1\le i<j\le n\) és \(\displaystyle x_i=x_j\).

Legyen \(\displaystyle p\) páratlan prímszám, \(\displaystyle 1\le n<p\), továbbá \(\displaystyle a_1,a_2,\ldots,a_n\) és \(\displaystyle b_1,b_2,\ldots,b_n\) tetszőleges modulo \(\displaystyle p\) maradékosztályok. Bizonyítsuk be, hogy az \(\displaystyle 1,2,\ldots,n\) indexeknek létezik olyan \(\displaystyle \pi\) permutácója, amire

\(\displaystyle N\big(a_1+b_{\pi(1)},a_2+b_{\pi(2)},\ldots,a_n+b_{\pi(n)}\big) \le \min \big(N(a_1,a_2,\ldots,a_n), N(b_1,b_2,\ldots,b_n) \big). \)

(5 pont)

A beküldési határidő 2018. június 11-én LEJÁRT.


Megoldás (Gáspár Attila és Matolcsi Dávid dolgozata felhasználásával). A megoldás során a \(\displaystyle p\) prímszám rögzített lesz. "Maradékosztályon" mindig modulo \(\displaystyle p\) maradékosztályt fogunk érteni, és \(\displaystyle S_m\)-nel fogjuk jelölni az \(\displaystyle \{1,2,\ldots,m\}\) halmaz permutációnak halmazát. Tetszőleges \(\displaystyle \sigma\in S_m\) permutáció esetén \(\displaystyle \sgn\sigma\) fogja jelölni a \(\displaystyle \sigma\) előjelét: értéke páros permutáció esetén \(\displaystyle +1\), páratlan permutáció esetén \(\displaystyle -1\).

Látható, hogy az \(\displaystyle N(\ldots)\) értéke nem függ az argumentumok sorrendjétől; a \(\displaystyle b_i\)-ket az \(\displaystyle a_i\)-khoz kell párosítani. A két sorozat szerepe szimmetrikus, felcserélhető.

Először abban az esetben oldjuk meg a feladatot, ha \(\displaystyle a_1,\ldots,a_n\) különböző.

I. állítás: Ha a \(\displaystyle n<p\), az \(\displaystyle a_1,\ldots,a_n\) maradékosztályok páronként különbözők, és \(\displaystyle b_1,\ldots,b_n\) tetszőleges maradékosztályok, akkor van olyan \(\displaystyle \pi\in S_n\) permutáció, hogy az \(\displaystyle a_1+b_{\pi(1)}, \ldots, a_n+b_{\pi(n)}\) maradékosztályok is páronként különbözők.

Az I. állításra kétféle bizonyítást is mutatunk. Mindkét bizonyításhoz szükségünk lesz az úgynevezett Vandermonde-polinomokra.

Az \(\displaystyle x_1,\ldots,x_n\) változók Vandermonde-polinomja $$\begin{align*} V(x_1,x_2,\ldots,x_n) &= \prod_{1\le i\lt j\le n} (x_j-x_i) = \\ &= \det\begin{pmatrix} 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \ldots & x_n^{n-1} \\ \end{pmatrix} = \\ &= \sum_{\sigma\in S_n} (\sgn\sigma)\cdot x_1^{\sigma(1)-1}x_2^{\sigma(2)-1}\cdots x_n^{\sigma(n)-1}. \end{align*}$$ A polinom néhány fontos tulajdonsága, amit fel fogunk használni:

\(\displaystyle \bullet\) A Vandermonde-polinom értéke akkor és csak akkor nem nulla, ha a behelyettesített számok mind különbözők.

\(\displaystyle \bullet\) A Vandermonde-polinom alternáló polinom, vagyis bármely \(\displaystyle \pi\in S_n\) permutációra

\(\displaystyle V(x_{\pi(1)},\ldots,x_{\pi(n)}) = (\sgn\pi)\cdot V(x_1,\ldots,x_n). \)

1. bizonyítás az I. állításra. A fő eszközünk a következő Lemma lesz:

Lemma. Legyen \(\displaystyle F\) algebrai test, és legyen \(\displaystyle f(x_1,\ldots,x_n)\) egy \(\displaystyle F\) feletti polinom.
  Legyenek \(\displaystyle t_1,\ldots,t_n\) nemnegatív egészek úgy, hogy \(\displaystyle \deg f=t_1+\ldots+t_n\);
  legyenek \(\displaystyle S_1,\ldots,S_n\subset F\) olyan halmazok, amelyekre \(\displaystyle |S_i|>t_i\) mindegyik \(\displaystyle i\) index esetén;
  végül tegyük fel, hogy \(\displaystyle f(x_1,\ldots,x_n)\) kifejtésében az \(\displaystyle x_1^{t_1}\ldots x_n^{t_n}\) együtthatója nem \(\displaystyle 0\).
Ekkor léteznek olyan \(\displaystyle s_1\in S_1,\ldots.,s_n\in S_n\) elemek, amelyekre \(\displaystyle f(s_1,\ldots,s_n)\ne0\).

A Lemma és egy bizonyítása megtalálható Noga Alon Combinatorial Nullstellensatz című cikkében (1.2. tétel). A tételt — kissé helytelenül — szokás "combinatorial Nullstellensatz"-nak (kombinatorikus nullhelytétel) is hívni, noha valójában az 1.1. tétel felelhetne meg a klasszikus, Hilbert-féle Nullstellensatznak.

Az I. állítás bizonyításához legyen \(\displaystyle F\) a \(\displaystyle p\)-elemű test (a modulo \(\displaystyle p\) maradékosztályok teste),

\(\displaystyle f(x_1,\ldots,x_n) = V(x_1,\ldots,x_n) \cdot V(x_1+b_1,\ldots,x_n+b_n), \)

legyen \(\displaystyle t_1=\ldots=n-1\) (ekkor valóban \(\displaystyle \deg f=t_1+\ldots+t_n=n(n-1)\)), végül \(\displaystyle S_1=\ldots=S_n=\{a_1,\ldots,a_n\}\).

Az \(\displaystyle x_1^{n-1}\ldots x_n^{n-1}\) együtthatójának leolvasásához vegyük észre, hogy $$\begin{align*} f(x_1,\ldots,x_n) &= \left( \sum_{\sigma\in S_n} (\sgn\sigma)\cdot \prod_{i=1}^n x_i^{\sigma(i)-1} \right) \left( \sum_{\tau\in S_n} (\sgn\tau)\cdot \prod_{i=1}^n (x_i+a_i)^{\tau(i)-1} \right) = \\ &= \sum_{\sigma\in S_n} \sum_{\tau\in S_n} (\sgn\sigma)\cdot (\sgn\tau)\cdot \left( \prod_{i=1}^n x_i^{\sigma(i)-1} \right) \left( \prod_{i=1}^n (x_i+a_i)^{\tau(i)-1} \right). \end{align*}$$ Az \(\displaystyle x_1^{n-1}\ldots x_n^{n-1}\) monom azokban a tagokban fordul elő, amelyekben \(\displaystyle \sigma(i)+\tau(i)=n+1\). Legyen \(\displaystyle \varphi\) az a permutáció, amelyre \(\displaystyle \varphi(i)=n+1-i\); az \(\displaystyle x_1^{n-1}\ldots x_n^{n-1}\) tehát azokban a tagokban szerepel, amelyekben \(\displaystyle \tau=\varphi\circ\sigma\). Az \(\displaystyle n!\) különböző \(\displaystyle \sigma\) mindegyikéhez pontosan egy megfelelő \(\displaystyle \tau\) permutáció létezik, és a tag előjele minden esetben \(\displaystyle (\sgn\sigma)(\sgn\tau) = \sgn(\sigma\tau^{-1}) =\sgn\varphi\), vagyis az előjel mindig ugyanaz. Tehát az \(\displaystyle x_1^{n-1}\ldots x_n^{n-1}\) együtthatója \(\displaystyle n!\cdot\sgn\varphi\), ami nem osztható \(\displaystyle p\)-vel, azaz \(\displaystyle p\)-elemű testben nem a \(\displaystyle 0\) elem.

A Lemma szerint vannak olyan \(\displaystyle s_1,\dots,s_n\in\{a_1,\ldots,a_n\}\) elemek, amelyekre \(\displaystyle f(s_1,\ldots,s_n)\ne0\). Ez azt jelenti, hogy sem \(\displaystyle V(s_1,\ldots,s_n)\), sem \(\displaystyle V(s_1+b_1,\ldots,s_n+b_n)\) nem \(\displaystyle 0\). Az, hogy \(\displaystyle V(s_1,\ldots,s_n)\ne0\), azt jelenti hogy az \(\displaystyle s_1,\ldots,s_n\) elemek különbözők, tehát \(\displaystyle (s_1,\ldots,s_n)\) az \(\displaystyle (a_1,\ldots,a_n)\) sorozat egy permutációja: \(\displaystyle s_i=a_{\pi(i)}\). A második tényező, \(\displaystyle V(s_1+b_1,\ldots,s_n+b_n=V(a_{\pi(1)}+b_1,\ldots,a_{\pi(n)}+b_n)\) akkor nem \(\displaystyle 0\), ha az \(\displaystyle a_{\pi(1)}+b_1,\ldots,a_{\pi(n)}+b_n\) maradékosztályok mind különbözők. Ezzel az I. állítást igazoltuk.

2. bizonyítás az I. állításra (Matolcsi Dávid).

Azt fogjuk igazolni, hogy

\(\displaystyle \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}) = n! \cdot V(x_1,\ldots,x_n). \tag{1} \)

Az (1) bizonyításához legyen

\(\displaystyle P(x_1,\ldots,x_n,y_1,\ldots,y_n) = \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}). \)

Fejtsük ki a \(\displaystyle V(x_1+y_1,\ldots,x_n+y_n)\) polinomot \(\displaystyle x_1,\ldots,x_n\) szerint:

\(\displaystyle V(x_1+y_1,\ldots,x_n+y_n) = \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \, x_1^{k_1}\ldots x_n^{k_n}, \)

ahol a \(\displaystyle k_1,\ldots,k_n\) kitevők nemnegatív egészek, és minden ilyen kitevősorozatra \(\displaystyle C_{k_1,\ldots,k_n}(y_1,\ldots,y_n)\) egy-egy \(\displaystyle n\)-változós polinom.

Helyettesítsünk be a \(\displaystyle P\) definíciójába, rendezzük a Vandermonde-polinom argumentumait az \(\displaystyle y_i\)-k indexei szerint, majd cseréljük fel az összegzéseket: $$\begin{align*} P(x_1,\ldots,x_n,y_1,\ldots,y_n) &= \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}) = \\ &= \sum_{\pi\in S_n} (\sgn\pi^{-1})\cdot V(x_{\pi^{-1}(1)}+y_1,\ldots,x_{\pi^{-1}(n)}+y_n) = \\ &= \sum_{\tau\in S_n} (\sgn\tau) \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \, x_{\tau(1)}^{k_1}\ldots x_{\tau(n)}^{k_n} = \\ &= \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \sum_{\tau\in S_n} (\sgn\tau)\cdot x_{\tau(1)}^{k_1}\ldots x_{\tau(m)}^{k_n} = \\ &= \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \cdot\det \begin{pmatrix} x_1^{k_1} & \ldots & x_1^{k_n} \\ \vdots & \ddots & \vdots \\ x_n^{k_1} & \ldots & x_n^{k_n} \\ \end{pmatrix}. \end{align*}$$ Ha a \(\displaystyle k_1,\ldots,k_n\) kitevők közül valamelyik kettő egyenlő, akkor az utolsó determinánsban az ezekhez tartozó két oszlop megegyezik, ezért a determináns biztosan \(\displaystyle 0\). Ha viszont a \(\displaystyle k_1,\ldots,k_n\) kitevők mind különbözők, akkor — mivel a \(\displaystyle P\) polinom foka legfeljebb \(\displaystyle \tbinom{n}{2}=0+1+\ldots+(n-1)\) — az csak úgy lehet, ha \(\displaystyle (k_1,\dots,k_n)\) az \(\displaystyle (0,1,\ldots,n-1)\) sorozat egy permutációja. Ilyenkor a \(\displaystyle C_{k_1,\ldots,k_n}(y_1,\ldots,y_n)\) polinom legfeljebb csak konstans lehet, tehát a fenti összegben az \(\displaystyle y_1,\ldots,y_n\) változók kiesnek. Emiatt

\(\displaystyle P(x_1,\ldots,x_n,y_1,\ldots,y_n) = P(x_1,\ldots,x_n,0,\ldots,0) = \)

\(\displaystyle = \sum_{\pi\in S_n} V(x_1+0,\ldots,x_n+0) = n! \cdot V(x_1,\ldots,x_n); \)

ezzel az (1) azonosságot igazoltuk.

Az (1)-be behelyettesítve az \(\displaystyle a_1,\ldots,a_n\) és \(\displaystyle b_1,\ldots,b_n\) értékeket,

\(\displaystyle \sum_{\pi\in S_n} V(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)})\equiv n! \cdot V(a_1,\ldots,a_n) = n! \cdot \prod_{i<j} (a_j-a_i) \not\equiv 0 \pmod{p}.\)

A jobboldal nem nulla, tehát a baloldalon álló összegnek biztosan van legalább egy nemnulla tagja, azaz van olyan \(\displaystyle \pi\in S_n\) permutáció, amelyre

\(\displaystyle V(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) = \prod_{i<j} (a_j+b_{\pi(j)}-a_i-b_{\pi(i)})\ne0, \)

ami viszont éppen azt jelzi, hogy az \(\displaystyle a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}\) maradékosztályok különbözők modulo \(\displaystyle p\).

II. állítás: Ha \(\displaystyle 0\le n<p\), akkor van olyan \(\displaystyle \pi\in S_n\), amelyre \(\displaystyle N(a_1+b_{\pi(1)}, a_2+b_{\pi(2)}, \ldots, a_n+b_{\pi(n)})\le N(a_1, a_2, \dots, a_n)\).

Bizonyítás (Gáspár Attila). Az \(\displaystyle n\) szerinti indukcióval bizonyítunk. \(\displaystyle n=0\) (az üres sorozat) és \(\displaystyle n=1\) esetén az állítás triviális. Legyen \(\displaystyle 2\le n<p\), és tegyük fel, hogy kisebb értékekre az állítás igaz.

Legyen \(\displaystyle k\) az \(\displaystyle a_1, a_2, \dots, a_n\) között előforduló különböző elemek száma. Rendezzük az az \(\displaystyle a_i\)-kat olyan sorrendbe, hogy \(\displaystyle a_1,a_2,\ldots,a_k\) mind különböző legyen. Az \(\displaystyle a_{k+1},\ldots,a_n\) mindegyike pontosan egyszer szerepel \(\displaystyle a_1,a_2,\ldots,a_k\) között, így pontosan \(\displaystyle n-k\) olyan \(\displaystyle i,j\) indexpár van, amelyre \(\displaystyle i\le k<j\) és \(\displaystyle a_i=a_j\). Tehát,

\(\displaystyle N(a_1,\ldots,a_n) = (n-k) + N(a_{k+1},\ldots,a_n). \tag{2} \)

Az I. állítás miatt az \(\displaystyle 1, 2, \dots, k\) számoknak van olyan \(\displaystyle \pi_1\) permutációja, amelyre \(\displaystyle a_1+b_{\pi_1(1)}, a_2+b_{\pi_1(2)}, \ldots, a_k+b_{\pi_1(k)}\) mind különbözők. Az indukciós feltevés szerint a \(\displaystyle k+1, k+2, \dots, n\) számoknak van olyan \(\displaystyle \pi_2\) permutációja, amelyre

\(\displaystyle N(a_{k+1}+b_{\pi_2(k+1)}, a_{k+2}+b_{\pi_2(k+2)}, \ldots, a_n+b_{\pi_2(n)})\le N(a_{k+1}, a_{k+2}, \dots, a_{n}). \tag{3} \)

Legyen a \(\displaystyle \pi_1\) és \(\displaystyle \pi_2\) egyesítésével kapott permutáció.

A \(\displaystyle \pi_1\) konstrukciója szerint az \(\displaystyle a_1+b_{\pi(1)},\ldots,a_k+b_{\pi(k)}\) maradékosztályok különbözők, így \(\displaystyle i<j\le k\) esetén \(\displaystyle a_i+b_{\pi(i)}\ne a_j+b_{\pi(j)}\).

Mindegyik \(\displaystyle k<j\le n\)-hez legfeljebb egy olyan \(\displaystyle i\le k\) lehet, amelyre \(\displaystyle a_i+b_{\pi(i)}=a_j+b_{\pi(j)}\). Ezért

\(\displaystyle N(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) \le (n-k) + N(a_{k+1}+b_{\pi(k+1)},\ldots,a_n+b_{\pi(n)}). \tag{4} \)

A (4,3,2) becslések együtt az adják, hogy

\(\displaystyle N(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) \le N(a_1,\ldots,a_n). \)

Ezzel a II. állítást igazoltuk.

A feladat megoldása: A szimmetria miatt feltételezhetjük, hogy \(\displaystyle N(a_1, \dots, a_n)\le N(b_1, \dots, b_n)\). Ekkor a II. állítás éppen a feladat állítása.


Statisztika:

3 dolgozat érkezett.
5 pontot kapott:Gáspár Attila.
2 pontot kapott:1 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2018. májusi matematika feladatai