Tudsz-e egy kombinatorikus megfejtést erre?
Van egy feladat, amit megoldottam, de jó hosszan.
A végeredménye azt sugallja, hogy van vmi okos megoldás is:
Egy kör kerületén van n db pont. Mindegyiket mindegyikkel összekötöm egy szakasszal. Legfeljebb hány tartományra osztják ezek a szakaszok a kört?
Mármost ez jött ki:
1 + (n alatt a 2) + (n alatt a 4)
(az első öt eset amúgy 2 hatványa)
Kellene egy "okos" (kombinatorikus) megoldás!
Én a következőképp csinálnám:
vizsgáljuk meg, hogy bizonyos esetekben hány részre osztják a kört az egyenesek;
1 egyenes 2-re.
2 egyenes, ha párhuzamos, akkor 3-ra, ha metszik egymást, akkor 4-re.
3 egyenes estén:
-ha párhuzamosak, akkor 4-re
-ha pontosan 2 metszi egymást, akkor 5-re
-ha 1 metsz 2-t, akkor 6-ra
-ha mindhárom egyenes pontosan 1-szer metszi a másik kettőt, akkor 7-re.
-azzal az esettel most nem foglalkozunk, amikor 1 pontban metszi egymást a 3 egyenes, mivel az nem visz maximum felosztásszámhoz.
Ha ezt tovább folytatnánk, akkor láthatnánk, hogy annyival több síkrészt kapunk, amennyi az egyenesek metszéspontjának száma (amennyiben 1 metszéspontnál pontosan 2 egyenes találkozik). Bocs, de a bizonyítás sosem volt az erősségem, így ezt most nem bizonyítanám.
Tehát:
-ha az n csúcsot szomszédosan összekötjük, akkor n darab körszeletet (és így síkrészt) kapunk.
-ha nem a szomszédos csúcsokat kötjük össze, akkor n+metszésszám darab síkrészt kapunk,
így összesen 2n+metszésszám darab síkrészünk lesz.
A kérdés, hogy mennyi a maximum metszésszám?
Ha ennek a számításával jutok valamire, akkor megírom.
Basszus, ezt mondom, hogy ez megvan!!!
Így végigcsináltam, levezettem, ki is jött, ne fáradj vele.
Nem megoldani kell, hanem vmi közvetlen, ügyes kombinatorikus ötletet keresek...
Arról nem is beszélve, hogy el sem olvastad a feladatot!!!
Az egy másik feladat, hogy általában egyenesek hány részre osztják a kört.
Itt onnan indulunk, hogy pontokat adunk meg a kör kerületén...
Ezt most mire is alapozod?
(Amúgy ELTE matek szakot végeztem, tanítok is felső szintű matekot, de nem érdekes...)
Mondok egy kicsit hasonló (ismert) példát:
Ugyanígy a kör kerületén levő n db pontot páronként összekötjük. Legfeljebb hány metszéspont keletkezhet a kör belsejében?
Itt is lehet indukciós lépésekkel, az első néhány esetből megsejtve a formulát igazolni.
4 --> 1
5 --> 5
6 --> 15
stb.
Ez elég macerás, de végigtolható.
Van azonban egy kombinatorikus ötlet, amivel azonnal megkapható a zárt formula.
Ez megvan?
Ha nem lenne meg:
Annyi metszéspont van belül, ahányféleképpen 4 pontot kiválaszthatunk az n-ből.
Így a metszéspontok száma (n alatt a 4).
Na ilyesmire gondolok az adott feladatban is, valami ügyes konstrukcióra.
Van még az is pl. hogy
(n+1) alatt a (k+1) = n alatt a k + n alatt a (k+1)
ennek is van egy nem algebrai, hanem szép ötleten alapuló kombinatorikus bizonyítása
Zárójelben: háromszor is (1999, 2001, 2002 )megnyertem az Élet és Tudomány feladatmegoldó versenyét (Gondolkodás iskolája), pedig ott nem akárkik indultak ám.
Ja és van még egy kedvencem:
A Pascal-háromszög n-edik sorában a számok négyzetösszege éppen (2n) alatt az n.
Ez sztem bitang nehéz algebrailag, de egy jó ötlettel kombinatorikusan indokolható.
Gondolom, ismered ennek a megoldását, ez jó illusztrálja, mire gondolok.
Ez jó!
Köszi!
"Arról nem is beszélve, hogy el sem olvastad a feladatot!!!
Az egy másik feladat, hogy általában egyenesek hány részre osztják a kört.
Itt onnan indulunk, hogy pontokat adunk meg a kör kerületén..."
Hát, erre alapoztam.
Sajnos sem az angolom, sem a matekom nem elég jó, hogy megértsem, de n>=18 esetén szerintem nem jó:
A táblázatban: n pont, képlet szerint, változás
alatta a szorzatok+1 összegezve.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!