Feladat: 1394. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bárány Imre ,  Deák Jenő ,  Domokos L. ,  Herényi I. ,  Kiss A. ,  Márki László ,  Vesztergombi Katalin 
Füzet: 1966/március, 106 - 108. oldal  PDF  |  MathML 
Témakör(ök): Számelrendezések, Konstruktív megoldási módszer, Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok: 1965/május: 1394. 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.

a) Általában két s jelű lemez közé s további lemez kerül, így ha az első lemez az l-edik helyre kerül, akkor a második az l+s+1-edikre. Ha s páros, akkor az egyik sorszám páros, a másik páratlan, ha viszont s páratlan, akkor vagy mindkét sorszám páros vagy mindkettő páratlan. Az 1.‐2k. sorszámok fele páratlan, fele páros, a páros jelű lemezek egyike páros, másika páratlan sorszámú helyen van, így ugyanannyi páratlan jelű lemezpár kerül páratlan sorszámú helyre, mint páros sorszámú helyre.
b) k=3 esetén a páratlan és a páros sorszámú helyekre egyaránt egy 2-es és két páratlan jelű lemez jut. A két 3-as lemezt a 2. és 6. helyre állítva a 4. helyre 2-es lemez jut, így az 1. helyre is, és az elrendezés

2,3,1,2,1,3.(1)

A 3-as pár másik lehetséges helyzetéből, az 1. és 5. helyből kiindulva az előbbi elrendezést fordított sorrendben kapjuk. Ezt nem tekintjük az előbbitől lényegesen különbözőnek, ugyanígy k további értékeinek esetében sem.
c) A k=4 esetben hasonlóan a 2-es és a 4-es lemezek egyik példánya páros, másika páratlan sorszámú helyre jut, és a maradó 2 páros és 2 páratlan sorszámú hely‐pár egyikére az 1-esek, másikára a 3-asok jutnak.
Megmutatjuk, hogy a két 3-as között középen álló helyre állítandó páros jelű lemez nem lehet 4-es. Legyen e hely sorszáma a sor hozzá közelebbi végétől számítva n ‐ azaz n≦4 ‐, és tegyünk ide 4-es lemezt. Ekkor a két 3-as az n±2-edik helyeken áll, és az ezekkel egyenlő párosságú n+4-edik helyen 2-es. Ennek párja az n+1-edik helyen áll, hiszen nem állhat az n+7-edik helyen, mert n-2≧1 miatt n+7>8; a második 4-es lemez hasonlóan csak az n+5-ödik helyen állhat, így a két 1-es számára az n-1-edik és az n+3-adik hely marad, ezek között azonban 3 lemez áll.
Az n-edik helyre 2-est téve a 4-esek hely‐sorszáma hasonlóan n+4 és n-1. A második 2-es nem állhat az n+3-adik helyen, viszont az n-3-adikra téve megfelelő elrendezést kapunk:
2,3,4,2,1,3,1,4.(2)
Más megoldás nincs.
d) Írjuk (1)-ben 1, 2, 3 helyére rendre a 2-szeresénél 1-gyel nagyobb számot, és legyen a még betöltendő helyek jele x. Így adódik pl. az
x,x,x,5,x,7,x,x,3,5,x,x,3,7,x,x,x,
rész‐elrendezés, és ebből próbálgatással k=7-re
1,4,1,5,6,7,4,2,3,5,2,6,3,7.
Hasonlóan adódnak, 1, 2, 3 helyén a 4, 6, 7, ill. 4, 5, 7 lemezekkel:
26327435614175,62742356437151,ill.35743625427161.



1, 2, 3 helyén 5, 6, 7-tel próbálkozva nem találtunk megoldást. Hasonlóan kapjuk k=8 céljára (2)-ben 1, 2, 3, 4 helyére rendre a 2, 4, 6, 8, ill. a 4, 6, 7, 8 számot írva a következő elrendezéseket:
1514678542362738,ill.3627328564171548.

1, 2, 3, 4 helyén 5, 6, 7, 8-cal próbálkozva nem találtunk megoldást.
e) Az a) feltétel csak akkor teljesülhet, ha k-ig páros számú páratlan szám van. k=4j+1-ig és k=4j+2-ig egyaránt 2j+1 páratlan szám van, tehát ezekben az esetekben a feladat nem oldható meg.
 
Bárány Imre (Budapest‐Mátyásföld, Corvin M. G. III. o. t.)
Márki László (Budapest, Fazekas M. gyak. G. IV. o. t.)

 
Megjegyzések. 1. Jelöljük (a, b)-vel az összes egyenlő párosságú számok egymásutánját az a-tól a b-ig növekedő vagy csökkenő sorrendben, aszerint, hogy a<b vagy a>b. Ekkor k=4m-1 és k=4m, m≧2 esetén a következő elrendezés mindig megoldást ad. Mindkét esetben a
(4m-4,2m),4m-2,(2m-3,1),4m-1,(1,2m-3),(2m,4m-4)
rész‐elrendezéssel kezdjük a megoldást, és közös a továbbiakban a
(4m-3,2m+1),4m-2,(2m-2,2),2m-1,4m-1,(2,2m-2),(2m+1,4m-3)


rész is. E két rész közé k=4m-1 esetén a hátra levő 2m-1-es lemez teendő, k=4m esetén pedig az első 4m-es lemez, és ekkor az elrendezés végén 2m-1, 4m áll. Ezek m=1 esetén (1)-et, ill (2)-t adják (a zárójeles sorozatok elmaradnak).
A kizárt k esetekben is van ilyen megoldás, ha előírjuk egy 0-jelű lemez közbeiktatását. k=4m-3 (azaz 4j+1), m≧3 esetére:
(4m-6,2m-2),4m-5,(2m-5,1)4m-4,(1,2m-5),(2m-2,4m-6),4m-3,(4m-7,2m-1),4m-5,(2m-4,2),2m-3,4m-4,(2,2m-4),(2m-1,4m-7),2m-3,0,4m-3.



k=4m-2 (azaz 4j+2), m≧4 esetére pedig:
1,2m-3,1,(4m-8,2m-2),(2m-5,3),4m-3,2m-3,4m-6,(3,2m-5),4m-4,(2m-2,4m-8),4m-2,(4m-5,2m-1),(2m-4,2),4m-6,4m-3,(2,2m-4),4m-4,(2m-1,4m-5),0,4m-2.



Ezeket az általános megoldásokat R. O. Davies közölte.1
 
2. Az, hogy k=4j+1 és k=4j+2 esetén a feladat nem oldható meg, más úton is belátható (ugyancsak párossági meggondolásokkal):
α) Jelöljük az i lemez első előfordulásának sorszámát si-vel, ekkor a második i-lemezé si+i+1, így valamennyi sorszám összege:
2(s1+s2+...+sk)+[2+3+...+k+(k+1)],
másrészt a szóban forgó sorszámok összege
1+2+3+...+(2k-1)+2k=k(2k+1).
A két kifejezés egyenlőségéből az 1, 2, ..., k lemez első előfordulása sorszámainak összege
s1+s2+...+sk=2k(2k+1)-k(k+3)4=14k(3k-1).
Ez azonban k=4j+1 és k=4j+2 esetén nem egész szám, ezért ezekben az esetekben nincs megfelelő elrendezés.
 Bárány Imre
 
β) A lemezek 1, 1, 2, 2, ..., k, k sorrendjéből elindulva minden elrendezéshez eljuthatunk szomszédos párok cseréjében álló lépésekkel. Olyan sorrendet akarunk elérni, amelyben az egyező jelű lemezek közt lévő lemezek összes száma 1+2+...+(k-1)+k=k(k+1)/2. Egy szomszédos l és m jelű lemez cseréjével csak a két l jelű és a két m jelű lemez közti lemezek száma változik, mégpedig mindegyik vagy nő vagy csökken 1-gyel. Így az egyező jelű lemezek közti lemezek számának összege vagy 2-vel nő, vagy 2-vel csökken, vagy nem változik, párossága tehát nem változik. A kiinduló helyzetben ez az összeg 0, tehát páros, így mindig páros kell hogy legyen. Azonban k=4j+1-re és 4j+2-re k(k+1)/2 páratlan, tehát a kívánt elrendezés nem létezik.
 
Deák Jenő (Budapest, Kölcsey F. G. III. o. t.)
1The Mathematical Gazette 43 (1959) 253‐255. o.