Logikai feladat! Valaki?

Legrosszabb esetben is 2^20, ami milliós nagyságrend, szóval annyira nem "baromi sok".

A kérdés volt már, nem is olyan régen:

https://www.gyakorikerdesek.hu/kozoktatas-tanfolyamok__hazif..

a) rész:

5 vagy 15 benne van és egyetlen páros sincs.

H' = {1,3,7,9,11,13,17,19} 8 elemű.

Ha 5 és 15 is benne van, akkor 2^8 ilyen részhalmaz van (H' bármely elemét vagy berakom vagy nem)

Ha csak az egyik van benne, akkor 2^8-1, mert minden jó, kivéve, ha 0 elemet választok H'-ből.

Összesen: 2^8+(2^8-1)+(2^8-1)=3*2^8-2=766

Ugyanaz, mint a fent linkelt megoldásban, hurrá.

b) rész:

Nézzük az ellenkezőjét, amikor nincs benne 5-ös.

Ekkor 16 féle számból választunk minimum 2-őt.

A 16 elemű halmaz összes részhalmazainak száma 2^16

0 elemű részhalmazok száma 1

1 elemű részhalmazok száma 16.

Tehát 2^16-1-16 legalább 2 elemű részhalmaz van.

A H halmaz összes részhalmazainak száma 2^20

Tehát a keresett részhalmazok száma:

2^20-(2^16-17) = 2^20-2^16+17 = 983057

Végét elrontottam:

"A H halmaz összes részhalmazainak száma 2^20"

Itt a minimum 2 eleműek kellenek, vagyis 2^20-1-20

Tehát a keresett részhalmazok száma:

(2^20-21)-(2^16-17) = 2^20-2^16-4 = 983036