Скупови
Задатак 1 Написати принцип укључења–искључења за четири скупа \(A\), \(B\), \(C\) и \(D\). Затим одредити колико бројева од 1 до 210 је дељиво бар једним од бројева 2, 3, 5 и 7, а колико није дељиво ниједним од њих.
За четири скупа сабирамо кардиналности скупова, одузимамо кардиналности свих пресека по два, додајемо пресеке по три и одузимамо пресек сва четири: \[ \begin{aligned} |A \cup B \cup C \cup D| = {} & |A| + |B| + |C| + |D| \\ & - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap C| - |B \cap D| - |C \cap D| \\ & + |A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D| \\ & - |A \cap B \cap C \cap D|. \end{aligned} \] Нека је \(A_k\) скуп бројева од 1 до 210 дељивих са \(k\); тада је \(|A_k| = 210 / k\) кад \(k\) дели 210. Појединачно: \(105 + 70 + 42 + 30 = 247\). Пресеци по два су \(A_6, A_{10}, A_{14}, A_{15}, A_{21}, A_{35}\): \(35 + 21 + 15 + 14 + 10 + 6 = 101\). Пресеци по три су \(A_{30}, A_{42}, A_{70}, A_{105}\): \(7 + 5 + 3 + 2 = 17\). Пресек сва четири је \(A_{210}\), са једним елементом. Дакле \[ |A_2 \cup A_3 \cup A_5 \cup A_7| = 247 - 101 + 17 - 1 = 162, \] а ниједним од бројева 2, 3, 5, 7 није дељиво \(210 - 162 = 48\) бројева.
Задатак 2 Колико подскупова скупа од 10 елемената има више од 3 елемента?
Скуп од 10 елемената има \(2^{10} = 1024\) подскупа. Лакше је пребројати оне са највише 3 елемента: један празан скуп, 10 једночланих, \(\frac{10 \cdot 9}{2} = 45\) двочланих (сваки пар смо у производу \(10 \cdot 9\) бројали двапут) и \(\frac{10 \cdot 9 \cdot 8}{6} = 120\) трочланих (сваку тројку смо бројали \(3 \cdot 2 \cdot 1 = 6\) пута). Подскупова са више од 3 елемента има \(1024 - 1 - 10 - 45 - 120 = 848\).
Задатак 3 Нека је \(A = \{a, b, c\}\) и \(B = \{0, 1\}\).
(а) Набројати елементе скупа \(A \times B\) и одредити \(|A \times B|\), \(|B \times A|\) и \(|A \times A \times B|\).
(б) Колико има бинарних релација од скупа \(A\) до скупа \(B\), тј. подскупова скупа \(A \times B\)?
(в) Колико уређених парова \((x, y) \in A \times A\) има различите компоненте, \(x \neq y\)?
(а) \(A \times B = \{(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)\}\), па је \(|A \times B| = |B \times A| = 3 \cdot 2 = 6\) (али \(A \times B \neq B \times A\)) и \(|A \times A \times B| = 3 \cdot 3 \cdot 2 = 18\).
(б) Релација је подскуп скупа \(A \times B\) од 6 елемената, па их има \(2^6 = 64\).
(в) Скуп \(A \times A\) има \(9\) парова, од којих 3 имају једнаке компоненте, \((a, a)\), \((b, b)\) и \((c, c)\); остаје \(9 - 3 = 6\) парова.
Задатак 4 PIN код се састоји од 4 цифре (од 0 до 9).
(а) Колико има различитих PIN кодова?
(б) Колико има PIN кодова у којима су све цифре различите?
(в) Колико има PIN кодова у којима се бар једна цифра понавља?
(а) PIN код је уређена четворка цифара, тј. елемент скупа \(C^4\), где је \(C = \{0, 1, \dots, 9\}\): има их \(10^4 = 10\,000\).
(б) Прву цифру бирамо на 10 начина, другу на 9 (мора бити различита од прве), трећу на 8 и четврту на 7: \(10 \cdot 9 \cdot 8 \cdot 7 = 5040\).
(в) Пребројавамо комплемент: \(10\,000 - 5040 = 4960\).
Задатак 5 Нека је \(|A| = 3\) и \(|B| = 5\). Колико има функција \(f: A \to B\), колико од њих су инјекције, а колико има бијекција скупа \(B\) на самог себе?
Функција сваком од 3 елемента скупа \(A\) придружује један од 5 елемената скупа \(B\), па их има \(5^3 = 125\). Код инјекције слике морају бити различите: \(5 \cdot 4 \cdot 3 = 60\). Бијекција скупа \(B\) на самог себе има \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\) (то су пермутације скупа од 5 елемената).
Задатак 6 Колико најмање студената треба да буде у групи да бисмо били сигурни да су бар двојица рођена у истом месецу? А да би бар тројица била рођена у истом месецу?
Месеци има 12, па у групи од 12 студената сви могу бити рођени у различитим месецима, а у групи од 13 то више није могуће (Дирихлеов принцип): потребно је бар 13 студената. Да би бар тројица била рођена у истом месецу, потребно је \(2 \cdot 12 + 1 = 25\) студената, јер у групи од 24 може бити тачно по двоје рођених у сваком месецу.
from itertools import product
unija = {n for n in range(1, 211) if any(n % k == 0 for k in (2, 3, 5, 7))}
print(len(unija), 210 - len(unija)) # 162 48
broj = sum(1 for izbor in product([0, 1], repeat=10) if sum(izbor) > 3)
print(broj) # 848У другом делу сваки подскуп је низ од 10 нула и јединица, а број јединица у низу је број елемената подскупа.