Најважније из лекције
- Принцип збира: Број елемената уније дисјунктних скупова једнак је збиру броја елемената тих скупова.
- Принцип укључења-искључења: Ако скупови нису дисјунктни, њихов пресек се одузима: \( |A \cup B| = |A| + |B| - |A \cap B| \).
- Принцип производа: Користи се за пребројавање редоследа више независних избора. Укупан број комбинација је производ броја могућности за сваки појединачни избор (\( m \cdot n \)). Треба пазити на ограничења (нпр. нула на првом месту броја).
- Број двочланих подскупова: Број парова (партија, дужи, руковања) од \( n \) елемената рачуна се као \( \frac{n(n-1)}{2} \).
Сваки скуп чије елементе можемо пребројати називамо коначним скупом. Број елемената скупа \( A \) означава се са \( |A| \). Празан скуп је такође коначан и важи \( |\varnothing| = 0 \).
Принцип збира: Ако су \( A \) и \( B \) дисјунктни скупови (немају заједничких елемената, тј. \( A \cap B = \varnothing \)), број елемената њихове уније једнак је збиру броја елемената појединачних скупова:
\[ |A \cup B| = |A| + |B| \]
Ово правило се лако проширује на три или више дисјунктних скупова:
\[ |A \cup B \cup C| = |A| + |B| + |C| \]
Ако у једној кутији имамо 5 црвених куглица (скуп \( A \)), а у другој 3 плаве куглице (скуп \( B \)), укупан број куглица када их спојимо је \( |A \cup B| = 5 + 3 = 8 \).
Када скупови нису дисјунктни (имају заједничке елементе у пресеку), приликом сабирања њихових елемената, елементи пресека се броје два пута. Зато се број елемената у пресеку мора одузети.
За два скупа \( A \) и \( B \):
\[ |A \cup B| = |A| + |B| - |A \cap B| \]
За три скупа \( A, B \) и \( C \): \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| \]
За три скупа \( A, B \) и \( C \): \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| \]
У једном одељењу 18 ученика тренира фудбал, 14 тренира кошарку, а 5 ученика тренира оба спорта. Сваки ученик тренира бар један од ова два спорта. Колико ученика има у одељењу?
Нека је \( F \) скуп фудбалера, а \( K \) скуп кошаркаша. Познато је:
\( |F| = 18 \), \( |K| = 14 \), \( |F \cap K| = 5 \).
Применом принципа укључења-искључења:
\[ |F \cup K| = |F| + |K| - |F \cap K| = 18 + 14 - 5 = 27 \]
Одговор: У одељењу има 27 ученика.
Принцип производа: Ако један избор можемо направити на \( m \) начина, а након тога други избор можемо направити на \( n \) начина, укупан број начина да направимо оба избора редом је \( m \cdot n \).
У језику скупова, за коначне скупове \( A \) и \( B \) важи:
\[ |A \times B| = |A| \cdot |B| \]
Овај принцип се користи за одређивање броја коначних низова (нпр. прављење бројева од датих цифара, лозинки од слова, регистарских таблица).
Колико се двоцифрених бројева може написати помоћу цифара 1, 2, 3 и 4 тако да се цифре могу понављати?
За прву цифру имамо 4 могућности. За другу цифру такође имамо 4 могућности.
Укупан број бројева је \( 4 \cdot 4 = 16 \).
За прву цифру имамо 4 могућности. За другу цифру такође имамо 4 могућности.
Укупан број бројева је \( 4 \cdot 4 = 16 \).
Колико се троцифрених бројева може написати помоћу цифара 1, 2, 3 и 4 тако да се цифре не понављају?
- Прва цифра: 4 могућности (било која од понуђених).
- Друга цифра: 3 могућности (све осим оне искоришћене на првом месту).
- Трећа цифра: 2 могућности (све осим оне две претходно искоришћене).
При формирању вишецифрених бројева увек треба пазити на нулу (0). Нула не може бити на првом месту (нпр. 034 није троцифрен број). Такође, ако се тражи паран број, последња цифра мора бити парна.
Када желимо да одредимо колико се двочланих група (парова) може формирати од \( n \) елемената (на пример, колико дужи образује \( n \) тачака, или колико партија се одигра ако свако игра са сваким), користимо специфичну формулу.
Број двочланих подскупова скупа од \( n \) елемената рачуна се по формули:
\[ \frac{n(n - 1)}{2} \]
Ако имамо 5 тачака у равни, свака тачка може да се споји са преостале 4 тачке. Број дужи би био \( 5 \cdot 4 = 20 \), али пошто дуж \( AB \) и дуж \( BA \) представљају исту дуж, тај број морамо поделити са 2. Укупан број дужи је \( \frac{5 \cdot 4}{2} = 10 \).
Задаци за вежбање
Лаки: На колико начина се могу изабрати председник и заменик председника у одељењу које броји 25 ученика, ако један ученик не може обављати обе функције?
Користимо принцип производа.
За избор председника имамо 25 могућности.
Након тога, за избор заменика председника остаје 24 могућности.
Укупан број начина: \( 25 \cdot 24 = 600 \).
За избор председника имамо 25 могућности.
Након тога, за избор заменика председника остаје 24 могућности.
Укупан број начина: \( 25 \cdot 24 = 600 \).
Средњи: У групи од 40 туриста, 25 говори енглески језик, 15 говори немачки језик, док 7 туриста говори оба језика. Колико туриста не говори ниједан од ова два језика?
Прво рачунамо колико туриста говори бар један језик помоћу принципа укључења-искључења. Нека је \( E \) скуп оних који говоре енглески, а \( N \) немачки.
\( |E \cup N| = |E| + |N| - |E \cap N| \)
\( |E \cup N| = 25 + 15 - 7 = 33 \)
Дакле, 33 туристе говоре бар један језик.
Број туриста који не говоре ниједан језик је разлика укупног броја туриста и оних који говоре бар неки језик: \( 40 - 33 = 7 \).
Одговор: 7 туриста не говори ниједан од ова два језика.
\( |E \cup N| = |E| + |N| - |E \cap N| \)
\( |E \cup N| = 25 + 15 - 7 = 33 \)
Дакле, 33 туристе говоре бар један језик.
Број туриста који не говоре ниједан језик је разлика укупног броја туриста и оних који говоре бар неки језик: \( 40 - 33 = 7 \).
Одговор: 7 туриста не говори ниједан од ова два језика.
Тешки: Колико има четвороцифрених парних бројева записаних цифрама 0, 1, 2, 3, 4 и 5? (Цифре се могу понављати)
Број цифара на располагању је 6 (0, 1, 2, 3, 4, 5). Број мора бити паран и не сме почети нулом.
\( 5 \cdot 6 \cdot 6 \cdot 3 = 540 \)
Одговор: Има 540 таквих бројева.
- Прво место (хиљаде): 5 могућности (1, 2, 3, 4, 5 - нула не сме).
- Друго место (стотине): 6 могућности (све цифре су дозвољене).
- Треће место (десетице): 6 могућности.
- Четврто место (јединице): 3 могућности (да би број био паран, мора се завршавати на 0, 2 или 4).
\( 5 \cdot 6 \cdot 6 \cdot 3 = 540 \)
Одговор: Има 540 таквих бројева.
Тешки: На шаховском турниру учествује 8 такмичара. Сваки такмичар игра по једну партију са сваким од осталих такмичара. Колико укупно партија ће бити одиграно на турниру?
Ово је проблем тражења броја двочланих подскупова скупа од \( n = 8 \) елемената.
Користимо формулу: \( \frac{n(n-1)}{2} \)
\( \frac{8 \cdot (8-1)}{2} = \frac{8 \cdot 7}{2} = \frac{56}{2} = 28 \)
Одговор: Биће одиграно 28 партија.
\( \frac{8 \cdot (8-1)}{2} = \frac{8 \cdot 7}{2} = \frac{56}{2} = 28 \)
Одговор: Биће одиграно 28 партија.
