Feladat: 1388. matematika feladat Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Berger Tibor ,  Freud Géza ,  Sándor Gyula 
Füzet: 1938/március, 205 - 206. oldal  PDF  |  MathML 
Témakör(ök): Abszolútértékes egyenlőtlenség-rendszerek, Egyenlőtlenség-rendszerek, Kombinatorikai leszámolási problémák, Permutációk, Feladat
Hivatkozás(ok):Feladatok: 1938/január: 1388. matematika feladat

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.

Kimutatjuk, hogy

i1=k,  ha  k=2,3,...(n-2),(n-1)
nem lehetséges, azaz az 1,2,...n elemek olyan permutációira, amelyekben az első helyen 2,3,...(n-2),(n-1) áll, az 1a) és 1b)-ből álló rendszer nem oldható meg.
Ha ugyanis i1=k [ahol k=2,3,...(n-2),(n-1)], és a szóbanforgó rendszernek volna megoldása, akkor 1b) szerint |xk|>|xk-j| és 1a) szerint xk-j>xk 1 csak úgy lehetséges, ha xk<0; ekkor azonban 1a) szerint
0>xk>xk+l2  míg  1b)  szerint  |xk|>|xk+l|,
tehát ellenmondásra jutunk. 2
Eszerint i1 csak 1 vagy n lehet, más szóval az 1,2,...n elemek legkisebbike vagy legnagyobbika (a természetes sorrend szerint). Már most nyilvánvaló, hogy ha i1 helyébe az előbbiek egyikét helyeztük, akkor az
i2,i3,...in
is csak oly permutáció lehet, amelyben az i2 helyén az i1 helyére tett elemen kívül fennmaradó elemek közül is a legkisebb vagy a legnagyobb kerülhet. Ha tehát az
i2,i3,...in
helyeken álló és megfelelő permutációk száma pn-1, és az
i1,i2,i3,...in
helyeken képzett megfelelő permutációk száma pn, akkor
pn=2pn-1.

Minthogy p2=2, azaz az
x1>x2  és  |xi1|>|xi2|
rendszer az 1, 2 elemek 2 permutációjára megoldható,
p3=2p2=22,p4=23,...pn=2n-1.

Tehát az 1,2,...n elemeknek 2n-1 számú olyan permutációja van, amelyre az 1a) ‐ 1b) rendszer megoldható.
Pl. legyen n=5. Az
x1>x2>x3>x4>x5...(1a)|xi1|>|xi2|>|xi3|>|xi4|>|xi5|...(1b)


rendszernek az 1, 2, 3, 4, 5 elemeknek következő permutációinál van megoldása:
12345152345123454123123541524351243541321253415423514235431212543154325143254321   

1j=1,2,...(k-1).

2l=1,2,...(n-k).