Számosságok és leszámlálások



1.
Játsszunk ,,Én mondok egy halmazt--Te megmondod a számosságát'' játékot.

(a)
A természetes számok véges részhalmazai.
(b)
A természetes számok részhalmazai.
(c)
Azok az $1, a_1, a_2, \ldots$ sorozatok, melyekben a szomszédos elemek hányadosa 1/2 vagy 2.
(d)
Azok az x-ből és y-ból álló sorozatok, melyekben csak véges sok y fordul elő.
(e)
Az egész számokból álló (véges) mátrixok (vagyis $n \times n$-es táblázatok).
(f)
Azon síkbeli háromszögek, melyeknek minden koordinátája egész szám.
(g)
Azon síkbeli háromszögek, melyeknek a területe egész szám.
(h)
A síkon egy háromszög belső pontjai.
(i)
A racionális számokból álló végtelen sorozatok.
(j)
A természetes számok összes permutációja (azon sorozatok, melyekben minden elem csak egyszer fordul elő).
(k)
A folytonos valós függvények.


2.
Most átnyargalunk a formalizmusra. Bebizonyítandók a következők:

(a)
$\omega^c=c$
(b)
$\omega^\omega=c^\omega=c$
(c)
$2^c=\omega^c=c^c$


3.
Ha A végtelen halmaz és |A|>|B|, akkor $\vert A\backslash B\vert=\vert A\vert$.


4.
Adjunk bijekciót (oda-vissza egyértelmű leképezést) az alábbi halmazok között.

0,1
és (0,1)
(a)
(0,1) és $(-\infty,\infty)$
(b)
$(0,\infty)$ és $(-\infty,\infty)$
(c)
{valós számok} és {irracionális számok}


5.
Egy valós számot nevezzünk kiszámíthatónak, ha van hozzá olyan Pascal nyelven írt program, amellyel a tizesesjegyeit meghatározhatjuk (pl. az n bemenetre a program megadja a szám n-edik tizedesjegyét). Mutassuk meg, hogy létezik nem kiszámítható szám. (A feladat éppen arról szól, hogy egy ilyet ,,megadni'' vagy ,,látni'' képtelenség.)


6.
Tekintsük az összes olyan, origóból induló és véges sok lépés után ugyanott végetérő sétát, amelynek minden lépése az x vagy az y tengellyel párhuzamos (pozitív vagy negatív irányú) egységszakasz. Mi a számossága ezen séták halmazának?


7.
Igazoljuk az alábbi azonosságot: $\sum_{k=1}^n k {n \choose k} = n2^{n-1}$.


8.
Hány olyan sorrendje van az $1, 2, \dots, n$ számoknak, amelyekben a páros és páratlan számok felváltva követik egymást?


9.
Egy 12 fős társaságot egy szálloda két háromágyas és három kétágyas szobájában kell elszállásolni. Hány különböző szobabeosztás lehetséges, ha az azonos számú ágyat tartalmazó szobákat nem különböztetjük meg egymástól?


10.
Tizenöt vívóból hányféleképpen alkothatunk három (nem feltétlenül diszjunkt) négyfős csapatot?

Vissza