Feladat: F.1785 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1972/május, 200 - 202. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikus geometria síkban, Kombinációk, Feladat
Hivatkozás(ok):Feladatok: 1971/október: F.1785

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.

I. megoldás. Jelöljük meg az adott konvex n-szög csúcsait (pozitív körüljárás szerint) rendre az 1, 2, ..., n számokkal. Minden egyes, a követelményt teljesítő négyes csúcskiválasztásnak megfelel egy olyan számnégyes, amelyben
A) nincs szomszédos (1 különbségű) számpár,
B) nem lép föl együtt az 1 és az n szám.

(Ugyanis szomszédos számok, vagy az 1 és n együttes fellépése azt jelentené, hogy a választott négyszög egyik oldala a sokszögnek is oldala volna.) Fordítva, minden ilyen számnégyesnek megfelel egy, az eredeti követelménynek megfelelő csúcsnégyes. Ezek szerint a kívánt csúcsnégyesek számát megadja az A- és B-tulajdonságú számnégyesek száma. Ez utóbbit úgy határozzuk meg, hogy az A-tulajdonságú számnégyesek N(A) számából levonjuk azoknak az A-tulajdonságú számnégyeseknek az N(AB¯) számát, melyeknek nincs meg a B tulajdonságuk.
Az N(A) szám meghatározása lényegében azonos feladat az 1970. évi Kürschák-verseny 2. feladatával*, csupán a lottószámok 90-es száma helyére kell n-et, és az egyszerre kihúzott lottószámok 5-ös száma helyére 4-et helyettesítenünk. Alkalmazzuk ezekkel a változtatásokkal az idézett helyen olvasható I. megoldás gondolatmenetét.
Jelöljük egy megfelelően kiválasztott számnégyes számait növekvő rendben a-val, b-vel, c-vel, és d-vel, így a számnégyes megfelelő volta ekvivalens az

1≦a<a+1<b<b+1<c<c+1<d≦n(1 )
egyenlőtlenség-lánc teljesülésével. Így pedig a
b'=b-1,c'=c-2,d'=d-3(2)
jelöléssel teljesül a
1≦a<b'<c'<d'≦n-3(3)
egyenlőtlenség-lánc is. Fordítva, ha az a, b', c', d' számokra teljesül (3), akkor a belőlük (2) szerint származtatott a, b, c, d számokra teljesül (1). Ezek szerint N(A) egyenlő a (3)-nak eleget tevő számnégyesek számával, vagyis az első (n-3) természetes szánt közül kiválasztható különböző számokból álló (és monoton növekvően elrendezett) számnégyesek számával:
N(A)=(n-34).

Ha egy számnégyesnek megvan az A tulajdonsága, de nincs meg a B tulajdonsága, akkor az elemei között szerepel az 1-es és az n, és a másik két elemére
3≦b<b+1≦n-2(4)
teljesül, ahol b és c jelöli ezeket az elemeket. A (4)-nek eleget tevő számpárok számát a fentiekhez hasonlóan meghatározva kapjuk, hogy
N(AB¯)=(n-52).
Tehát az A- és B-tulajdonságú számnégyesek száma
N(AB)=N(A)-N(AB¯)=(n-34)-(n-52)==(n-3)(n-4)(n-5)(n-6)4!-(n-5)(n-6)2!==(n-5)(n-6)4!(n2-7n+12-12)=n4(n-53).

 

Megjegyzések. 1. Eredményünk tartalmi szempontból (mind geometriai, mind a végzett számító gondolkodás szempontjából) természetesen csak az n≧8 esetekre érvényes. n=8 esetén N=2, az egyik megoldás a páratlan, a másik a páros sorszámú csúcsok kiválasztása. Formailag azonban már n=5 esetén helyes eredményt ad a képlet.
2. Valamivel gyorsabban érünk célhoz a következő ötlet alapján. Jelöljük a kiválasztandó csúcsnégyes által meghatározott négyszög csúcsait (pozitív körüljárás szerint) rendre P-vel, Q-val, R-rel és S-sel. Válasszuk ki először a P csúcsot az n-szög csúcsai közül (erre n-féle lehetőségünk van), majd ezután számozzuk meg a sokszög csúcsait P-ből indulva pozitív körüljárás szerint. A fenti gondolatmenettel könnyen bizonyítható, hogy a további három csúcs választására (n-53) lehetőségünk van, ezáltal n(n-53) négyszöget kapunk. Így azonban minden egyes négyszöget 4-szer állítunk elő ‐ ennyiféleképpen jelölhetjük meg a csúcsait pozitív körüljárás szerint a P, Q, R, S betűkkel ‐, tehát a különböző négyszögek száma n4(n-53).
 

II. megoldás. Az n-szög csúcsai (n4) konvex négyszöget határoznak meg, ezek között azonban olyanok is vannak, melyeknek 3, 2, ill. 1 oldaluk az n-szögnek is oldala. (Mind a 4 oldal csak n=4 esetén lehetne n-szögoldal, de ettől eltekintünk, csak n≧8 esetére foglalkozunk a kérdéssel.) Megállapítjuk a mondott egyezési esetek számát és kivonással képezzük a keresett N számot.
a) Négyszögünknek 3 oldala akkor közös az n-szöggel, ha 4 egymás utáni csúcsot választunk ki. Ez azt jelenti, hogy csak az elsőt választjuk ‐ ezt n-féleképpen tehetjük ‐, a többi 3 erre következik.
b) Ha 2 közös oldaluk van, ez lehet az n-szög 2 szomszédos ‐ vagyis 3 egymás utáni csúcs által alkotott ‐ oldala, vagy 2 távolabb fekvő oldal. Az első módon a 3 egymás utáni csúcsot ismét n-féleképpen választhatjuk meg, a negyedik négyszögcsúcs azonban már nem csatlakozhat ezekhez, ezért (n-5) db n-szögcsúcs közül választható; az ilyen lehetőségek száma tehát n(n-5). A második módon két, az n-szögön szomszédos csúcspárunk lesz. Az első pár első csúcsát ismét n-féleképpen, a második párét (n-5)-féleképpen választhatjuk (ha ugyanis az első pár pl. An-1, An, akkor a második pár első csúcsa A2,A3,...,An4 lehet). Az így gondolt n(n-5)összekapcsolásban azonban minden keresett kiválasztást 2-szer kapunk meg, az ilyen négyszögek száma tehát n(n-5)/2. c) Végül ha 1 közös oldala van négyszögünknek az n-szöggel, akkor az ennek megválasztása után maradó (n-4) csúcs közül a hátra levő 2 négyszög csúcsot (n-42)-féleképpen választhatjuk, ezek azonban n-5 esetben szomszédosak egymással, tehát az ide tartozó négyszögek száma:
n{(n-42)-(n-5)}=n(n-42)-n(n-5).
Mindezek szerint
N=(n4)-{n+(1+12-1)n(n-5)-n(n-42)}
ami kellő alakítás után egyezik az I. megoldás eredményével.
*Mi a valószínűsége annak, hogy egy lottóhúzás öt száma között van legalább két szomszédos (amelyek különbsége 1)? ‐ A megoldást lásd: Lovász László: Az 1970. évi Kürschák József matematikai tanulóverseny feladatainak megoldása. K. M. L. 42 (1971) 193 ‐ 198, ezen belül 195 ‐ 197.