Gondolkodási módszerek, halmazok, logika, kombinatorika, gráfok
Gondolkodási módszerek, halmazok, logika, kombinatorika, gráfok
Ez a domain a pontos fogalmazást és a leszámlálást méri: halmazműveletek, Venn-diagram, állítások tagadása, permutációk és kombinációk, valamint gráfok fokszáma, összefüggősége és Euler-útja. A feladatokban gyakran kell szöveget formalizálni, majd a modellt számolni.
Alapszabályok
- |A∪B| = |A| + |B| − |A∩B|; a komplementer számolása sokszor egyszerűbb.
- De Morgan: nem(A és B) = nem A vagy nem B; a „minden” tagadása „van olyan, amely nem”.
- Ismétlés nélküli permutáció n!, ismétléses permutáció n!/(k1!k2!…). Kiválasztásnál a sorrend számít-e, és megengedett-e az ismétlés?
- Gráfban a fokszámok összege kétszeres élszám; Euler-út akkor van, ha összefüggő és 0 vagy 2 páratlan fokú csúcs van.
Kidolgozott példa
Egy 30 fős osztályban 18-an szeretik a matematikát, 14-en a fizikát, 7-en mindkettőt. Hányan nem szeretik egyiket sem? Az unió 18 + 14 − 7 = 25, tehát 30 − 25 = 5 tanuló. Ellenőrzés Venn-diagrammal: csak matek 11, csak fizika 7, mindkettő 7, így 11+7+7=25. Ha a kérdés az, hányan szeretik legalább az egyiket, a válasz 25; ha pontosan az egyiket, az 18.
Csapdák
A „vagy” a matematikában megengedő, nem kizáró; a „legalább egy” komplementere a „egy sem”. Kombinatorikában a legtöbb hiba a sorrend és az ismétlés eldöntéséből jön. Gráfnál az elszigetelt csúcs rontja az összefüggőséget, és az Euler-kör nem tévesztendő össze az Euler-úttal.