Halmazos választós matek, HELP PLÍÍÍZ?

egyik megoldási mód ilyenkor, hogy megnézed, hogy max hányat tudsz úgy kiválasztani, hogy ne legyen két szomszédos, és akkor végignézed, hogy

- 1 számot hányféleképpen tudsz kiválasztani

- 2 számot hányféleképpen, ha nem lehet két szomszédos

- 3 számot hányféleképpen, ha nem lehet két szomszédos

stb..

Ezeket meg összeadod, és kész.

Tudnék még a feladatra mondani más módszert is, de igaziból ez a legegyszerűbb.

Ha a 8 helyett valami nagyobb szám van (valami n), akkor logikai szitával, vagy más néven szita formulával.

n darab számból 2^n féleképpen tudsz kiválasztani egy részhalmazt (minden számot vagy beválasztasz, vagy nem), ebből kell levonni azokat, amelyekben van két szomszédos.

A_12 jelölje azokat a részhalmazokat, amikben szerepel az 1 é 2 is.

A_23 azokat, amelyekben szerepel a 2 és a 3 is.

stb. így tovább, A_n1 jelölje azt, amiben az n és az 1 is szerepel.

Ezek csupa "rossz" részhalmazt tartalmaznak, és minden "rossz" részhalmaz benne lesz az egyik ilyenben, tehát a "rossz" részhalmazok halmaza pont az A_12,..A_n1 halmazok uniója, tehát ennek az uniónak az elemszámára vagyunk kíváncsiak.

Ehhez összeadjuk az A_ij-k elemszámát, de akkor minden olyan rossz részhalmazt kétszer számoltunk, ami kettőben is benne volt, így a két A_ij metszetéből keletkező halmazok elemszámát levonjuk, de így 3szor vontuk le azokat, amik 3ban is benne vannak, tehát őket most -1 szer számoltuk, tehát most az ilyeneket kell hozzáadni, stb.

Számszerűsítve: "rosszak" száma = n*2^(n-2) - (n alatt a 2)*2^(n-3) + (n alatt a 3)*2^(n-4) -... +(-1)^n*n

Nem túl szívderítő formula, de ez van.

a képletet szita-formulaként vagy logikai szitaként a wikin is megtalálod, ott tök jól le is van írva, szóval én nem írnám le.

8ra meg jobban jársz az elsőre elmondott módszerrel:

- ha csak 1 et választunk ki, az 8 eset

- ha kettőt, akkor az 8*5/2=20 (mert az elsőt 8 közül választhatod, akkor azt meg a szomszédait már nem választhatod, tehát a másodikat 8-3=5 közül választhatod, ami így együtt 8*5=40, de mindegyik párost kétszer számoltad aszerint, hogy melyik számot vetted elsőnek, így még osztasz kettővel), kijön, hogy 20 ilyen van.

- ha hármat, akkor egyszerűbb úgy számolni, hogy az elsőt valahogy választjuk, a maradék 2-t meg 5 közül lehet választani úgy, hogy a két szélső nem számít szomszédosnak (pl. ha a 7et választod elsőnek, akkor marad az 1,2,3,4,5 amikből kell még kiválasztani a másik kettőt, hogy ne legyen benne szomszédos, de az 1 és az 5 nem számít szomszédosnak, tehát őket együtt is lehet választani). Ezt még egyszerűbb felírod az összes esetet, vagy lejjebb írok rá egy általános módszert, amivel nagyobb számokra is megy, itt még könnyű összeszámolni, hogy ez 6. Tehát ez összesen 8*6, de minden hármast háromszor számoltunk (hogy mit vettünk ki először), így osztani kell 3mal, tehát ez összesen 8*3=24.

- 4nél látszik, hogy 2 féleképpen.

Összesítve 8+20+24+2=54

ha nem 8 lenne, hanem egy nagyobb szám, mondjuk 20, akkor azt, hogy hányféleképpen lehet mondjuk 6ot jól kiválasztani, azt úgy csinálod, hogy az elsőt bárhogy választod, marad 20-3=17 lehetőség, amiből ki kell választani 5öt, hogy ne legyen szomszédos, és a két szélső nem számít szomszédosnak. Az összes ilyen kiválasztás meg kölcsönösen megfeleltethető egy olyan kiválasztásnak, mikor 17-4=13-ból kell kiválasztani 5öt minden megkötés nélkül, tehát összesen ebből (13 alatt az 5) db van.

Hogy miért feleltethetőek meg egymásnak, az azért van, mert ha kiválasztasz a 17számból 5öt, hogy ne legyen két szomszédos, akkor növekvő sorrendbe állítod őket, a másodikból levonsz egyet, a harmadikból kettőt, a negyedikből hármat és az ötödikből négyet. Így mivel nem voltak szomszédos számok, ezért csupa különböző számot kapsz, ráadásul max 17-4=13 lesz a legnagyobb. Ez a megfeleltetés visszafelé is működik.