Valaki segítene 2 kombinatorikai feladatban?
1, Öt barát makaó nevű kártyajátékot játszik. Kezdéskor a 32 lapos magyar kártyából minden játékosnak kiosztanak 4 lapot. Hányféleképpen lehetséges ez?
2, Egy kerek asztal köré leül 10 ember. Az asztal fölött mindenki mindenkivel kezet fogott. Hány olyan kézfogáspár van, melyek keresztezik egymást?
Nagyon örülnék, ha valaki úgy eltudná magyarázni, hogy aki elolvassa, az azonnal megértse. Köszönöm !
1)
Azt biztos tudod, hogy ha van N darab dolog, akkor abból K darabot (N alatt K) féleképpen lehet kiválasztani. (Az N alatt a K-t valójában függőlegesen kellene a zárójellel írni, de azt itt nem lehet.)
Az első barát kaphat (32 alatt 4) féleképpen lapot, a következő már csak a maradék 28 lapból (28 alatt 4) féleképpen, stb. Vagyis az összes lehetőség:
(32 alatt 4)·(28 alatt 4)·(24 alatt 4)·(20 alatt 4)·(16 alatt 4)
2)
Valószínű van egyszerűbb megoldás is, de most érd be ezzel:
Legyen kicsit általánosabb: Nem 10, hanem N darab ember van az asztalnál.
Én vagyok az egyik. Nézzük az én kézfogásaimat. Kezet fogok veled, aki valahol szemben vagy velem. A kör mentén egyik oldalon kettőnk között van k ember, a másik oldalon pedig N-2-k ember (azért minusz kettő, mert mi nem vagyunk benne).
Az egyik oldalon lévő k ember egymás között ha kezet fog, akkor nem keresztez minket. A másik oldaliak szintén, mindaddig, amíg egymás között fognak kezet. De ha az egyik oldalról valaki kezet fog egy másik oldalival, máris keresztezik a kettőnk kézfogását.
Vagyis ezt a kézfogásomat k·(N-2-k) kézfogás keresztezi.
Az én összes kézfogásomat ennyi keresztezi:
k=0 .. N-2 Σ k·(N-2-k)
Mindenki összes keresztező kézfogása ennek N/4-szerese. Osztani kell 4-gyel, mert:
- egyrészt amikor én fogok veled kezet illetve te fogsz velem kezet, az ugyanaz
- másrészt amikor A kezet fog B-vel, és ezt keresztezi C-D, az ugyanaz, mint amikor C kezet fog D-vel, és ezt keresztezi A-B
Szóval a végeredmény: A szumma k=0 és N-2 között megy:
1/4·N·Σ k·(N-2-k)
Megjegyzés: A szummát ki lehet fejezni zárt képlettel is, ebből ez a szebb végeredmény jön ki:
N·(N-1)·(N-2)·(N-3)/24
Ez egyébként éppen (N alatt 4). Biztos van valami sokkal egyszerűbb megoldás is, ami rögtön ezt adja, de most már késő van ahhoz, hogy rájöjjek, hogyan :)
N=10 esetén mindez 210
Megvan az egyszerű megoldás:
Bármelyik 4 ember között van 6 kézfogás, és ezek között egyetlen egy pár olyan, amik keresztezik egymást: azok, amik a négyszög átlóit alkotják. Vagyis mindegyik 4 emberhez tartozik 1 keresztező kézfogáspár. 4 embert pedig (N alatt 4) féleképpen lehet kiválasztani.
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!