A B. 5033. feladat (2019. május)

B. 5033. Az $\displaystyle \binom{n+1}{2}$ darab $\displaystyle a_{1,1}, a_{1,2}, \ldots, a_{1,n}, a_{2,1}, a_{2,2}, \ldots, a_{2,n-1}, \ldots, a_{k,1}, \ldots, a_{k,n+1-k}, \ldots, a_{n,1}$ számot $\displaystyle n$-edrendű fordított Pascal-piramisnak hívjuk, ha tetszőleges $\displaystyle 2 \le k \le n$ és $\displaystyle 1 \le j \le n+1-k$ esetén $\displaystyle a_{k,j}=a_{k-1,j} + a_{k-1,j+1}$. Egy példa 3-adrendű fordított Pascal-piramisra:

Jelentse $\displaystyle s_k$ a piramis $\displaystyle k$-adik sorában lévő számok összegét, azaz $\displaystyle s_k = a_{k,1} + a_{k,2} + \ldots + a_{k,n+1-k}$. Egy piramis jelváltó a $\displaystyle k$-adik ($\displaystyle k>1$) sorában, ha $\displaystyle s_{k-1} \cdot s_k <0$. Adott $\displaystyle n$ esetén legfeljebb mekkora lehet a $\displaystyle k$ értéke, ha egy $\displaystyle n$-edrendű piramis jelváltó a $\displaystyle 2., 3., \ldots, k$-adik sorában, de a $\displaystyle (k+1)$-edik sorában már nem? (A fenti példában $\displaystyle k=2$, mert $\displaystyle s_1 \cdot s_2 = -2 <0$, de már $\displaystyle s_2 \cdot s_3 = 4 >0$.)

(5 pont)

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

Megoldás. A megoldás során $\displaystyle n$ a piramis rendjét fogja jelölni (és a leírásban szereplő piramisok -ha máshogy nem rendelkezünk- $\displaystyle n$-edrendűek lesznek).
Legyen $\displaystyle \mathcal{A}=\{ a_{1,1} ; ... ; a_{n,1} \}$ és $\displaystyle \mathcal{B}=\{ b_{1,1} ; ... ; b_{n,1} \}$ két $\displaystyle n$-edrendű Pascal-piramis. Ekkor a $\displaystyle c \mathcal{A}=\{ c \cdot a_{1,1} ; ... ; c \cdot a_{n,1} \}$, és az $\displaystyle \mathcal{A+B}=\{ a_{1,1}+b_{1,1} ; ... ; a_{n,1} +b_{n,1}\}$ is $\displaystyle n$-edrendű Pascal-piramisok. (Azaz piramisok összege, piramis konstansszorosa újra piramis.)
Legyen $\displaystyle \mathcal{E}_k$ az az "egység-piramis", ahol $\displaystyle a_{1,1}=a_{1,2}=...=a_{1,n}=0$ és $\displaystyle a_{1,k}=1$.
Ha a piramisom $\displaystyle k$-dik sorában csak az érdekel, hogy ott a sorösszeg mekkora, akkor egy piramis és a függőleges tükörtengelyére tükrözött képe (pl $\displaystyle \mathcal{E}_k; \mathcal{E}_{n+1-k}$) megegyezik.
Ezek alapján az $\displaystyle \mathcal{A}$ piramis felírható az egység piramisok segítségével $\displaystyle \mathcal{A}= a_{1,1} \cdot \mathcal{E}_1 + a_{1,2} \cdot \mathcal{E}_2 + ... + a_{1,n} \cdot \mathcal{E}_n$ alakban, és mivel csak a sorösszeget szeretnénk vizsgálni, áttérhetünk egy olyan $\displaystyle \mathcal{A}'$ piramisra, ami bármely sorösszegét vizsgálva azonos $\displaystyle \mathcal{A}$-val, de az alsó sorának „második fele” ($\displaystyle n$ páratlan volta esetén a középső mezőt kivéve) csupa nulla, jelesül $\displaystyle \mathcal{A}'= \left( a_{1,1} + a_{1,n} \right) \cdot \mathcal{E}_1 + \left( a_{1,2} + a_{1,n-1} \right) \cdot \mathcal{E}_2 + ... + \left( a_{1,\frac{n}{2}} + a_{1,\frac{n}{2}+1} \right) \cdot \mathcal{E}_{\frac{n}{2}} + 0 \cdot \mathcal{E}_{\frac{n}{2}+1} + ... + 0 \cdot \mathcal{E}_n$ . (Ez az az eset, ha $\displaystyle n$ páros; ha $\displaystyle n$ páratlan, akkor $\displaystyle \mathcal{A}'$ hasonlóan leírható.)
Ezek után esetszétválasztással megvizsgáljuk $\displaystyle n=2k$ (páros) és $\displaystyle n=2k+1$ (páratlan) eseteket.
I. eset: A piramisunk $\displaystyle n=2k$ (páros) rendű.
Lemma: Azt mutatjuk meg, hogy ekkor akárhogyan is van kitöltve az alsó sor, legfeljebb $\displaystyle k$-ad rendben jelváltó a piramis.
Indirekt tegyük fel, hogy a piramis legalább $\displaystyle k+1$-ed rendben jelváltó. Legyen a piramisunk olyan, hogy alulról első sorára $\displaystyle s_1>0$, majd második sorára $\displaystyle s_2<0$, és így tovább... A fentiek alapján választhatunk olyan $\displaystyle \mathcal{A}$ piramist, aminek alsó sorában az utolsó $\displaystyle k$ darab $\displaystyle a_{1,k+1},a_{1,k+2},...,a_{1,2k}$ elem mind 0. Ekkor persze az $\displaystyle a_{j,l}$ számok definíciója alapján $\displaystyle 0=a_{1,2k}=a_{2,2k-1}=a_{3,2k-2}=...=a_{k,k+1}$ (a piramis „jobb széle" egy ideig 0 elemeket tartalmaz.)
Mivel az alsó sorban lévő összes nem 0 $\displaystyle a_{1,m}$ szám az $\displaystyle a_{1,1}$ kivételével ($\displaystyle 0=a_{1,n}$!) az alulról második sorban lévő $\displaystyle a_{2,l}$ számokban (mint összegekben) két-két helyen „szerepel”, emiatt $\displaystyle 0>s_2 = 2 s_1 - a_{1,1} \rightarrow a_{1,1} > 2 s_1 > 0$.
Teljesen hasonlóan mivel az alulról második sorban lévő összes nem 0 $\displaystyle a_{2,m}$ szám az $\displaystyle a_{2,1}$ kivételével ($\displaystyle 0=a_{2,n-1}$!) az alulról harmadik sorban lévő $\displaystyle a_{3,l}$ számokban (mint összegekben) két-két helyen „szerepel”, emiatt $\displaystyle 0<s_3 = 2 s_2 - a_{2,1} \rightarrow a_{2,1} < 2 s_2 < 0$.
Ezt folytatva az alulról $\displaystyle k$-dik sorig (mivel $\displaystyle 0=a_{k,k+1}$!) adódik, hogy az $\displaystyle a_{1,1} ; a_{3,1} ; a_{5,1} ...$ számok pozitívak, míg az $\displaystyle a_{2,1} ; a_{4,1} ; a_{6,1} ...$ számok negatívak (és így $\displaystyle a_{k,1}$ és $\displaystyle a_{k+1,1}$ is ellentétes előjelű).
Most pedig a „bal oszlopban" szereplő $\displaystyle a_{1,1};a_{2,1};...;a_{k+1,1}$ számok előjeléből fogunk következtetni az alsó sorban lévő $\displaystyle a_{1,1};a_{1.2};...;a_{1,k}$ előjelére,és abszolútértékére!
Mivel a fenteik alapján $\displaystyle 0<a_{1,1}$ és $\displaystyle 0>a_{2,1} = a_{1,1} + a_{1,2}$ emiatt $\displaystyle 0>a_{2,1} > a_{1,2}$ és $\displaystyle |a_{1,1}|<|a_{1,2}|$.
Hasonlóan $\displaystyle 0>a_{2,1}$ és $\displaystyle 0<a_{3,1} = a_{2,1} + a_{2,2} = \underbrace {a_{2,1}}_{<0} + (\underbrace{a_{1,2}}_{<0} + a_{1,3})$ emiatt $\displaystyle 0< a_{1,3}$ és $\displaystyle |a_{1,2}|<|a_{1,3}|$. (És innen $\displaystyle a_{2,2} = a_{1,2} + a_{1,3}$ miatt $\displaystyle a_{2,2}>0$ is teljesül.
Tovább lépve: $\displaystyle 0<a_{3,1}$ és $\displaystyle 0>a_{4,1} = a_{3,1} + a_{3,2} = a_{3,1} + (a_{2,2} + a_{2,3}) = \underbrace {a_{3,1}}_{>0} + \underbrace{a_{2,2}}_{>0} + (\underbrace{a_{1,3}}_{>0}+a_{1,4})$ emiatt $\displaystyle 0>a_{4,1} > a_{1,4}$ és $\displaystyle |a_{1,3}|<|a_{1,4}|$. (És $\displaystyle 0> \underbrace {a_{3,1}}_{>0} + a_{3,2}$ miatt $\displaystyle a_{3,2}<0$, valamint $\displaystyle a_{2,3} = a_{1,3} + a_{1,4} < 0$ is teljesül.)
Ezt folytatva adódik, hogy az $\displaystyle a_{1,1}; a_{1,2}; a_{1,3}; ...; a_{1,k}$ számok felváltva pozitívak, illetve negatívak, valamint $\displaystyle |a_{1,1}| < |a_{1,2}| < |a_{1,3}| < ... < |a_{1,k}|$.
Ekkor ha $\displaystyle k(=2m)$ páros, akkor
$\displaystyle s_1= \underbrace {(a_{1,1} + a_{1,2})}_{<0} + \underbrace {(a_{1,3} + a_{1,4})}_{<0} + ... + \underbrace {(a_{1,2m-1} + a_{1,2m})}_{<0} + \underbrace {(a_{1,2m+1} + ...+a_{1,4m})}_{=0} <0$ ellentmondásban azzal, hogy az első sor összegére $\displaystyle s_1>0$. míg ha $\displaystyle k(=2m+1)$ páratlan, akkor
$\displaystyle s_2=2s_1 - a_{1,1}= a_{1,1} + 2\underbrace {(a_{1,2} + a_{1,3})}_{>0} + 2\underbrace {(a_{1,4} + a_{1,5})}_{>0} + ... +2 \underbrace {(a_{1,2m} + a_{1,2m+1})}_{>0} + 2\underbrace {(a_{1,2m+2} + ...+a_{1,4m+2})}_{=0} >0$
ellentmondásban azzal, hogy a második sor összegére $\displaystyle s_2<0$.
Mivel ellentmondáshoz jutottunk, az $\displaystyle n=2k$ (páros) magas piramis nem lehet $\displaystyle (k+1)$-ed rendben jelváltó.
Viszont adunk egy konstrukciót arra, hogy $\displaystyle k$-adrendben lehet jelváltó a piramis.
Tekintsük azt az $\displaystyle (n+1)=(2k+1)$-ed rendű piramist, amelynek alsó sorának számai: a „bal oldalon": $\displaystyle a_{1,1}=1; a_{1,2}=-2 ; a_{1,3}=4;a_{1,4}=-8;...;a_{1,k}=(-2)^{k-1}$, középen:$\displaystyle a_{1,k+1}=0$, míg a „jobb oldalon": $\displaystyle a_{1,n+1}=-1; a_{1,n}=2 ; a_{1,n-1}=-4;...;a_{1,k+2}=a_{1,n+1-(k-1)}= -(-2)^{k-1}$. (Azaz az $\displaystyle \mathcal{A}$ piramist a függőleges tükörtengelyére tükrözve éppen $\displaystyle \mathcal{A}' = -\mathcal{A}$ piramist kapjuk).
Erre a piramisra $\displaystyle s_1=s_2=...=s_n=0$ nyilván; másfelől a piramis „bal szélének" a számaira: $\displaystyle a_{1,1}=1; a_{2,1}=-1;a_{3,1}=1;a_{4,1}=-1;...;a_{k,1}=(-1)^{k-1}$ felváltva +1/-1 értékűek az alsó $\displaystyle k$ sorban.
Ha ennek az $\displaystyle (n+1)$-ed rendű $\displaystyle \mathcal{A}$ piramisnak elhagyjuk a bal oszlopát (az $\displaystyle a_{1,1};a_{2,1};a_{3,1};...$ elemeket), akkor egy olyan $\displaystyle n=(2k)$-ad rendű $\displaystyle \mathcal{B}$ piramist kapunk, ahol a sorösszegek felváltva éppen: $\displaystyle s(\mathcal{B})_1=s(\mathcal{A})_1-a_{1,1}=0-1=-1$; $\displaystyle s(\mathcal{B})_2=s(\mathcal{A})_2-a_{2,1}=0-(-1)=+1$; $\displaystyle s(\mathcal{B})_3=s(\mathcal{A})_3-a_{3,1}=0-1=-1$;... $\displaystyle s(\mathcal{B})_k=s(\mathcal{A})_k-a_{k,1}=0-(-1)^{k-1}=(-1)^k$ azaz a piramis valóban $\displaystyle k$-ad rendben jelváltó. (Hasonlóan a jobb szélső elemek elhagyásával is megfelelő piramist kapnánk.)
II. eset: A piramisunk $\displaystyle n=2k+1$ (páratlan) rendű.
Megmutatjuk, hogy ekkor a piramis maximum $\displaystyle (k+1)$-ed rendben jelváltó.
Ahhoz, hogy megmutassuk, hogy ilyen rendben lehet jelváltó a piramis, csak annyit kell tennünk, hogy a fenti jól megkonstruált $\displaystyle 2k$-rendű piramis „alá" beszúrunk be egy megfelelő sort.
Az új sor elemeit $\displaystyle a_{0,1}, a_{0,2}, ..., a_{0,2k+1}$-gyel fogjuk jelölni. Ha $\displaystyle a_{0,1}$ helyett $\displaystyle x$-t írunk, akkor $\displaystyle a_{0,2}=a_{1,1}-a_{0,1}=-x+a_{1,1}$, hasonlóan $\displaystyle a_{0,3}=a_{1,2}-a_{0,2}=a_{1,2}-(a_{1,1}-x)=x+a_{1,2}-a_{1,1}$, hasonlóan $\displaystyle a_{0,4}=a_{1,3}-a_{0,3}=a_{1,3}-(x+a_{1,2}-a_{1,1}) = -x + a_{1,3}-a_{1,2}+a_{1,1}$;...; $\displaystyle a_{0,2k+1} = x +a_{1,2k}-a_{1,2k-1} \pm ... - a_{1,1}$.
Az alsó sor $\displaystyle s_0$ összegére: $\displaystyle s_0=x+(-x+a_{1,1}) + (x-a_{1,1} + a_{1,2}) + (-x+a_{1,1}-a_{1,2} + a_{1,3}) + ... + (x-a_{1,1}+a_{1,2}-a_{1,3} \pm ... + a_{1,2k}) = x + a_{1,2} + a_{1,4} + a_{1,6} + ... + a_{1,2k}$. Ekkor $\displaystyle x$-t megválaszthatjuk úgy is, hogy az összeg pozitív legyen és úgy is, hogy negatív, azaz elérhető, hogy $\displaystyle s_0$ előjele más legyen, mint $\displaystyle s_1$ előjele, de akkor a piramisunk $\displaystyle (k+1)$-ed rendben lesz jelváltó.
Másfelől a piramisunk nem lehet $\displaystyle (k+2)$-ed rendben jelváltó, mert akkor elhagyva az alsó sorát egy olyan $\displaystyle 2k$-ad (páros!) rendű piramist kapnánk, amely $\displaystyle (k+1)$-ed rendben jelváltó, ellentétben az előzőekkel.
Összefoglalva: ha a piramisunk $\displaystyle n=2k$-rendű, akkor legfeljebb $\displaystyle k$-ad rendben lehet jelváltó,
míg, ha a piramisunk $\displaystyle n=2k+1$-rendű, akkor legfeljebb $\displaystyle (k+1)$-ed rendben lehet jelváltó.

Statisztika:

13 dolgozat érkezett.
5 pontot kapott:	Weisz Máté.
4 pontot kapott:	Beke Csongor.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2019. májusi matematika feladatai