Kezdőlap


Feladat:	F.2742	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Benkő D. , Csirik J. , Mezei J. , Peták A. , Podoski Károly. , Sustik M.
Füzet:	1990/október, 297 - 299. oldal		PDF \| MathML
Témakör(ök):	Kombinációk, Egyéb sokszögek geometriája, Feladat
Hivatkozás(ok):	Feladatok: 1989/április: F.2742

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 válasz nyilván függ attól, hogy milyen 100-szögből indulunk ki. Az ábrán látható 100-szög csúcsai közül bármely hat közül valamelyik három egy egyenesen van, így nincs egy konvex 33-szög sem a csúcsaiból alkotott 33-szögek között.

Másrészt konvex 100-szögek esetén a kiválasztható jó 33-szögek száma nyilván nem függ a konvex sokszög alakjától, hiszen annyiféle jó 33-szöget kapunk, ahányféleképpen a száz csúcsból kiválaszthatunk 33-at úgy, hogy ne legyen közöttük két szomszédos. (Minden jó 33-szög csúcsaira igaz, hogy nincs közöttük két szomszédos, és ha 33 csúcs olyan, hogy nincs közöttük két szomszédos, akkor pontosan egy jó 33-szöget ad. Ez abból következik, hogy egy konvex 100-szögből indultunk, így a kiválasztott 33 csúcs konvex burka egy 33-szög, amelynek csúcsait e 33 pont alkotja abban a sorrendben, ahogyan az eredeti 100-szögben szerepeltek.)
Számozzuk meg a 100-szög csúcsait úgy, hogy

A_{1} A_{2} ... A_{100} A_{1}

legyen a kiinduló sokszög. Ebből

(\binom{100}{33})

-féleképpen választhatunk ki 33 csúcsot, és minden ilyen kiválasztáshoz hozzárendelhetünk egy 100 hosszúságú 0‐1 sorozatot úgy, hogy a sorozat

i

-edik tagja 0, ha

A_{i}

-t nem választottuk ki, és 1, ha kiválasztottuk. (Így pl. az

{A_{1} A_{4} A_{7}, ..., A_{3 e + 1}, ... A_{97}}

kiválasztáshoz az 100 100...100 1000 sorozat tartozik.) Ez a hozzárendelés nyilván kölcsönösen egyértelmű a kiválasztott 33 csúcsú részhalmazok és a 0‐1 sorozatok között.
A kiválasztott 33 csúcs részhalmaza akkor alkot jó 33-szöget, ha nincs két szomszédos csúcsa; a 0‐1 sorozat tehát pontosan akkor jó, ha

a)

nincs két szomszédos 1-es benne,

b)

33 db 1-es van benne és

c)

az első és az utolsó tagja közül legalább az egyik 0.

Két csoportba osztjuk az ilyen jó sorozatokat, és külön‐külön számoljuk meg őket.
Az első csoportba azokat tesszük, amelyek első eleme 0 (tehát

A_{1}

nem szerepel a kiválasztott csúcsok között). Az ilyen sorozatokban minden 1-es előtt áll (legalább) egy nulla. Hagyjunk el minden egyes elől egy nullát. Így olyan 67 hosszúságú 0‐1 sorozatot kapunk, amelyben 33 darab egyes szerepel. Minden 67 hosszúságú, 33 darab 1-est és 34 darab 0-t tartalmazó sorozatot pontosan egyszer kapunk meg (abból a 100 hosszúságú, 33 darab egyest és 67 nullást tartalmazó sorozatból, amelyet úgy kapunk vissza, hogy a 67 hosszúságú 0‐1 sorozat minden egyese elé egy 0-t írunk: az így kapott sorozat ugyanis jó sorozat és 0-val kezdődik). Ebbe a csoportba tehát annyi jó sorozat tartozik, ahány 67 hosszúságú 0‐1 sorozat van, amelyikben pontosan 33 darab egyes van, vagyis

(\binom{67}{33})

A második csoportba azokat a jó sorozatokat tesszük, amelyek 1-essel kezdődnek. Ezeknek második és utolsó tagja biztosan 0. Hagyjuk el az első 1-est, az utolsó 0-t és minden további egyes elől egy nullát (hiszen minden további egyes előtt nulla áll). Így egy olyan 66 hosszúságú 0‐1 sorozatot kapunk, amelyben 32 darab egyes szerepel. Minden 66 hosszúságú 0‐1 sorozatot, amelyben 32 darab egyes szerepel, megkapunk éspedig pontosan egyszer: abból a jó sorozatból, amely 1-essel kezdődik s utána a 66 hosszú sorozatot írjuk, de az első kivételével minden egyese elé egy nullát toldunk, a végére pedig egy 0-t írunk. (Az így kapott 100 tagú sorozat nyilván jó sorozat és 1-essel kezdődik.) Az olyan 66 hosszúságú 0‐1 sorozatok száma, amelyekben 32 darab egyes van,

(\binom{66}{32})

, így pontosan ennyi a jó sorozatok száma ebben a csoportban.
Az összes jó sorozat, vagyis az összes jó 33-szög száma konvex 100-szög esetén tehát

(\binom{67}{33}) + (\binom{66}{32})

, (ez egy húszjegyű szám.)
Ha a 100-szög nem konvex, akkor a kapott 33-szögeken kívül minden további vagy nem konvex, vagy van közös oldala a 100-szöggel. Ráadásul a kapott

(\binom{67}{33}) + (\binom{66}{32})

darab 33-szög sem mind konvex. Így láthatjuk, hogy nem konvex 100-szög esetén ‐ a sokszög alakjától függően ‐ kevesebb jó 33-szög van, s még az is előfordulhat, hogy egy sincs.

Megjegyzés. Nem kapott teljes pontszámot az, aki valamilyen módon nem utalt rá, hogy a

(\binom{67}{33}) + (\binom{66}{32})

csak konvex 100-szögre érvényes eredmény, és az sem, aki nem indokolta meg, hogy 33 csúcs legfeljebb egyféle sorrendben adhatja egy konvex 33-szög csúcsait.