Kezdőoldal » Tudományok » Alkalmazott tudományok » Tudsz-e egy kombinatorikus...

Tudsz-e egy kombinatorikus megfejtést erre?

Figyelt kérdés

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!



2013. dec. 31. 18:20
1 2
 1/15 anonim ***** válasza:

É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.

2013. dec. 31. 20:48
Hasznos számodra ez a válasz?
 2/15 A kérdező kommentje:

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...

2013. dec. 31. 21:37
 3/15 A kérdező kommentje:

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...

2013. dec. 31. 21:39
 4/15 anonim ***** válasza:
Nehezen tudom elhinni, hogy te felsőszintű matematikával vagy kapcsolatban...
2013. dec. 31. 22:14
Hasznos számodra ez a válasz?
 5/15 A kérdező kommentje:

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.

2014. jan. 1. 10:59
 6/15 A kérdező kommentje:

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.

2014. jan. 1. 11:46
 7/15 anonim ***** válasza:

Szerintem innen az 1. bizonyítás kell neked:


[link]

2014. jan. 1. 12:09
Hasznos számodra ez a válasz?
 8/15 A kérdező kommentje:

Ez jó!

Köszi!

2014. jan. 1. 12:25
 9/15 anonim ***** válasza:

"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.

2014. jan. 1. 13:17
Hasznos számodra ez a válasz?
 10/15 anonim ***** válasza:

Sajnos sem az angolom, sem a matekom nem elég jó, hogy megértsem, de n>=18 esetén szerintem nem jó:

[link]

A táblázatban: n pont, képlet szerint, változás

alatta a szorzatok+1 összegezve.

2014. jan. 1. 14:57
Hasznos számodra ez a válasz?
1 2

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!