KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem A. 496. (December 2009)

A. 496. Let a1,a2,...,a2k be distinct integers and let M be a set of k integers not containing 0 and s=a1+a2+...+a2k. A grasshopper is to jump along the real axis, starting at the point 0 and making 2k jumps with lengths a1,a2,...,a2k in some order. If ai>0 then the grasshopper jumps to the right; while if ai<0 then the grasshopper jumps to the left, to the point in the distance |ai| in the respective steps. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

(5 pont)

Deadline expired on 11 January 2010.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Sn-nel fogjuk jelölni az (1,2,...,n) indexek permutációinak csoportját. Minden egyes \pi\inSn-re \mathrm{sgn}(\pi) jelöli a \pi permutáció előjelét, ami páros permutációra +1, páratlan permutációra -1.

Legyen


P(x_1,\ldots,x_n) = 
\sum_{\pi\in S_{2k}} \sgn(\pi) \prod_{\ell=1}^{2k-1} \prod_{m\in M} 
\big((x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)})-m\big), (1)

és tekintsük a P(a_1,\ldots,a_{2k}) számot.

Ha P(a_1,\ldots,a_{2k})\ne0, akkor létezik legalább egy olyan \pi\inS2k permutáció, amire


\prod_{\ell=1}^{2k-1} \prod_{m\in M} 
\big((x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)})-m\big) \ne 0.

Ez utóbbi viszont akkor és csak akkor nem 0, ha az a_{\pi(1)}, (a_{\pi(1)}+a_{\pi(2)}), ..., (a_{\pi(1)}+a_{\pi(2)}+\dots+a_{\pi(2k-1)}) számok különböznek az összes M-beli számtól; más szóval akkor, ha a szöcske végig tud ugrálni a 0, a_{\pi(1)}, a_{\pi(1)}+a_{\pi(2)}, ..., a_{\pi(1)}+a_{\pi(2)}, ..., a_{\pi(1)}+\ldots+a_{\pi(2k-1)}, s számokon. Célunk tehát annak igazolása, hogy P(a_1,\ldots,a_{2k})\ne0.

 

A P polinom alternáló, vagyis bármelyik két változó felcserélésével a polinom (-1)-szeresét kapjuk, és ha bármelyik két változó helyére ugyanazt az értéket helyettesítjük, a polinom értéke 0 lesz. Jól ismert, hogy minden alternáló polinom, tehát P is, töbszöröse a


V(x_1,\ldots,x_{2k}) = 
\prod\limits_{1\le i<j\le2k}(x_j-x_i) =
\sum_{\pi\in S_{2k}} \sgn(\pi) \, x_{\pi(2) }x_{\pi(3)}^2\cdots x_{\pi(2k)}^{2k-1}

úgynevezett Vandermonde-polinomnak. A P foka legfeljebb k(2k-1), ami megegyezik a V(x_1,x_2,\ldots,x_{2k}) Vandermonde-polinom fokával. A P tehát konstansszorosa a Vandermonde-polinomnak:


P(x_1,x_2,\ldots,x_{2k}) = 
(-1)^k c_k \cdot V(x_1,x_2,\ldots,x_{2k}).

(A (-1)k előjel egy kis magyarázatra szorul. A \prod\limits_{\ell=1}^{2k-1} \prod\limits_{m\in M}
\big((x_1+x_2+\ldots+x_\ell)-m\big) szorzatban a Vandermonde-polinom tagjai közül az x12k-1x22k-2...x2k-1 szerepel a legtöbbször; a Vandermonde-polinomban ennek a tagnak az együtthatója (-1)k.)

 

Észrevehetjük, hogy a P polinom, és vele együtt a ck szám egyáltalán nem függ az M halmaztól. Ezért ugyanazzal a ck konstanssal az is igaz, hogy


  P(x_1,\ldots,x_{2k}) =
  \sum_{\pi\in S_{2k}} \sgn(\pi) \prod_{\ell=1}^{2k-1}
  \big(x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)}\big)^k =
  (-1)^k c_k \cdot V(x_1,x_2,\ldots,x_{2k}). (2)

 

Az ugrásokat behelyettesítve,


P(a_1,a_2,\ldots,a_{2k}) = 
(-1)^k c_k \cdot V(a_1,a_2,\ldots,a_{2k}).

Mvel az a_1,\ldots,a_{2k} ugrások különbözőek, V(a_1,a_2,\ldots,a_{2k})\ne0. A feladat megoldásához már csak annyi hiányzik, hogy ck\ne0, avagy, (1) jobboldala nem esik ki szőröstül-bőröstül.

 

A ck\ne0 állításnál többet bizonyítunk.

Definíció. Legyen tetszőleges u,v\ge0 egészekre


  P^{(n,u,v)}(x_1\ldots,x_n) =
  \sum_{\pi\in S_n} \sgn(\pi) \left( \prod_{\ell=1}^{n-1}
  \big(x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)}\big)^u \right)
  (x_1+\ldots+x_n)^v. (3)

Tetszőleges d_1>\ldots>d_n\ge0 egészekre jelöljük \alpha^{(n,u,v)}_{d_1,\ldots,d_n}-nel x1d1...xndn együtthatóját a P(n,u,v) polinomban. Mivel a polinom alternáló,


  P^{(n,u,v)}(x_1,\ldots,x_n) =
  \sum_{d_1>\ldots>d_n\ge0} \alpha^{(n,u,v)}_{d_1,\ldots,d_n}
  \sum_{\pi\in S_n} \sgn(\pi) \, 
  x_{\pi(1)}^{d_1} x_{\pi(2)}^{d_2} \cdots x_{\pi(n)}^{d_n}.
  (4)

Az egyszerűség kedvéért az \alpha^{(n,u,v)}_{d_1,\ldots,d_n} együtthatót akkor is definiáljuk, ha di=di+1 valamelyik 1\lei<n indexre, vagy ha dn<0; ilyenkor \alpha^{(n,u,v)}_{d_1,\ldots,d_n}=0.

 

1. lemma. n\ge2 esetén

(a) tetszőleges d_1>\ldots>d_n>0 sorozatra


\alpha^{(n,u,0)}_{d_1,\ldots,d_n} = 0

és

(b) tetszőleges d_1>\ldots>d_{n-1}>0 sorozatra


\alpha^{(n,u,0)}_{d_1,\ldots,d_{n-1},0} = \alpha^{(n-1,u,u)}_{d_1,\ldots,d_{n-1}}.

Bizonyítás. Tekintsük a


  P^{(n,u,0)}(x_1,\ldots,x_n) = \sum_{\pi\in S_n} \sgn(\pi) \prod_{\ell=1}^{n-1}
  \big(x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)}\big)^u =


  = \sum_{d_1>\ldots>d_{n-1}>0} \alpha^{(n,u,0)}_{d_1,\ldots,d_{n-1},0}
  \sum_{\pi\in S_n} \sgn(\pi) \, 
  x_{\pi(1)}^{d_1} x_{\pi(2)}^{d_2} \cdots x_{\pi(n-1)}^{d_{n-1}}

polinomot.

A baloldalon a \prod_{\ell=1}^{n-1}
\big(x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)}\big)^u szorzatban nem szerepel az x_{\pi(n)} változó. Ezért x1d1x2d2...xn-1dn-1 alakú tagot csak az olyan permutációkra kaphatunk, amikben \pi(n)=n. Az ilyen permutációkra összegezve pedig


\sum_{\pi\in S_n,\,\pi(n)=n} \sgn(\pi) \prod_{\ell=1}^{n-1}
\big(x_{\pi(1)}+x_{\pi(2)}+\ldots+x_{\pi(\ell)}\big)^u = 
P^{(n-1,u,u)}(x_1,\ldots,x_{n-1}).

Tehát x1d1x2d2...xn-1dn-1 együtthatója a P(n,u,0) polinomban ugyanaz, mint a P(n-1,u,u) polinomban.

 

2. lemma. Ha v\ge1, akkor tetszőleges d_1>\ldots>d_n\ge0 sorozatra


\alpha^{(n,u,v)}_{d_1,\ldots,d_n} = 
\sum_{i=1}^n \alpha^{(n,u,v-1)}_{d_1,\ldots,d_{i-1},d_i-1,d_{i+1},\ldots,d_n}.

Bizonyítás. A P(n,u,v) definiója alapján


P^{(n,u,v)}(x_1,\ldots,x_n) = P^{(n,u,v-1)}(x_1,\ldots,x_n) \cdot (x_1+\ldots+x_n)
= \sum_{i=1}^n P^{(n,u,v-1)}(x_1,\ldots,x_n) \cdot x_i.

Az x1d1x2d2...xndn együtthatója a baloldalon \alpha^{(n,u,v)}_{d_1,\ldots,d_n}, a jobboldalon az P^{(n,u,v-1)}(x_1,\ldots,x_n) \cdot x_i polinomban pedig \alpha^{(n,u,v-1)}_{d_1,\ldots,d_{i-1},d_i-1,d_{i+1},\ldots,d_n}.

 

3. lemma. Tetszőleges n\ge1, u,v\ge0 és d_1\ge\ldots\ge d_n\ge0 egész számokra

\alpha^{(n,u,v)}_{d_1,\ldots,d_n}\ge0.

Bizonyítás. Indukció. n=1 esetén P(1,u,v)(x1)=x1v, az egyetlen együttható pozitív. Innen, az 1. és 2. lemmát alkalmazva, triviális.

 

4. lemma. Legyenek n\ge1, u\gen/2 és v\ge0 egészek. Ekkor \alpha^{(n,u,v)}_{d_1,\ldots,d_n}>0 minden olyan, egészekből álló d_1>\ldots>d_n\ge0 sorozatra, amelyben d_1+\ldots+d_n=(n-1)u+v és dn\lev.

Bizonyítás. Teljes indukcióval bizonyítunk.

Az n=1 esetben P(1,u,v)(x1)=x1v, és az egyetlen együttható \alpha(1,u,v)v=1>0. A továbbiakban feltételezzük, hogy n>1, és az állítás igaz minden olyan esetben, amikor

(a) n-et kisebbre cseréljük, vagy pedig

(b) v értékét csökkentjük, miközben n értéke változatlan marad.

 

1. eset: v=0. A dn\lev feltétel miatt csak dn=0 lehetséges. Az 1. lemma szerint


\alpha^{(n,u,0)}_{d_1,\ldots,d_{n-1},0} = \alpha^{(n-1,u,u)}_{d_1,\ldots,d_{n-1}}.

Az indukciós feltételt az (n',u',v')=(n-1,u,u) hármasra és az (d'_1,\ldots,d'_{n-1})=(d_1,\ldots,d_{n-1}) számokra alkalmazzuk.

Az u'>\frac{n'}2 feltétel teljesül, mert u'=u\ge\frac{n}2>\frac{n'}2.

Mivel v=dn=0,


d'_1+d'_2+\ldots+d'_{n'} = d_1+d_2+\ldots+d_{n-1}+d_n = (n-1)u = (n'-1)u' + v'.

Végül,


d'_{n'} = d_{n-1} \le \frac{d_1+d_2+\ldots+d_{n-1}}{n-1} = u = v'.

A lemma feltételei tehát mind teljesülnek, és \alpha^{(n,u,0)}_{d_1,\ldots,d_{n-1},0} =
\alpha^{(n-1,u,u)}_{d_1,\ldots,d_{n-1}}>0.

 

2. eset: v>0. Az indukciós feltevést most az (n',u',v')=(n,u,v-1) hármasra alkalmazzuk, mert a 2. lemma szerint


\alpha^{(n,u,v)}_{d_1,\ldots,d_n} = 
\sum_{i=1}^n \alpha^{(n,u,v-1)}_{d_1,\ldots,d_{i-1},d_i-1,d_{i+1},\ldots,d_n}.

A 3. lemma szerint a jobboldalon csupa nemnegatív szám áll; azt kell megmutatnunk, hogy van közöttük legalább egy pozitív is.

Mivel


d_1+\ldots+d_n = (n-1)u+v > (n-1)\cdot\frac{n}2+0 = (n-1)+(n-2)+\ldots+1+0,

létezik legalább egy olyan 1\lei\len index, amire di>n-i. Tekintsük az utolsó ilyen indexet. Ha i<n, akkor di-1>di+1; ha pedig i=n, akkor dn-1\ge0.

Alkalmazzuk az indukciós feltevést az (d'_1,\ldots,d'_n)=(d_1,\ldots,d_{i_0-1},d_{i_0}-1,d_{i_0+1},\ldots,d_n) számokra. Az i választásából következik, hogy d'_1>\ldots>d'_n\ge0.

Az u'\ge\frac{n'}2 feltétel triviálisan teljesül.

Végül, d'n=max (dn-1,0)\lev-1 miatt az igaz, hogy d'n\lev.

Az indukciós feltevés tehát az \alpha^{(n-1,u,u)}_{d_1,\ldots,d_{i-1},d_{i}-1,d_{i+1},\ldots,d_n} számok közül legalább egyre alkalmazható.

Ezzel a Lemmát igazoltuk.

 

Következmény. ck>0 minden egyes pozitív egész k-ra.

Bizonyítás. Alkalmazzuk a 4. lemmát az n=2k, u=k, v=0, (d_1,\dots,d_{2k})=(2k-1,2k-2,\ldots,1,0) számokra. A lemma feltételei teljesülnek, ezért

 c_k = \alpha^{(2k,k,0)}_{2k-1,2k-2,\ldots,1,0} > 0.


Statistics:

2 students sent a solution.
4 points:Nagy 235 János.
3 points:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley