Bevezetés a számításelméletbe
11. gyakorlat, 2002. november 24.
 
 
Számosságok, leszámlálás

 

1. (Múltkori feladatsorból) Bizonyítsuk be, hogy az alábbi halmazok megszámlálható ($\aleph_0$) számosságúak.
   1. A sík egész koordinátájú pontjai;
   2. A sík racionális koordinátájú pontjai;
   3. A racionális számokból alkotott $2\times 2$-es mátrixok;
   4. Az egész koordinátájú háromszögek halmaza (egybevágó háromszögeket egyformáknak tekintünk);
   5. Azon bitsorozatok halmaza, amelyben véges sok 1-es fordul elő (de a sorozatok végtelen hosszúak).

2. Igazoljuk, hogy az alábbi halmazok kontinuum ($\aleph_1$) számosságúak.
   1. A végtelen hosszú bitsorozatok;
   2. A végtelen hosszú csak $a$, $b$ és $c$ szimbólumokat tartalmazó sorozatok halmaza;
   3. A háromdimenziós tér pontjainak halmaza;
   4. Valós számsorozatok halmaza;
   5. Az egész területű síkbeli háromszögek halmaza.

3. Tíz gyerek hányféleképpen állítható úgy sorba, hogy Jancsi és Juliska egymás mellett álljanak?

4. Tizenkét vívóból hányféleképpen lehet kialakítani három darab négy fős csapatot, ahol a csapatok nem feltétlenül diszjunktak és
   1. a három csapatnak van külön neve is;
   2. a csapatoknak nincs nevük.

5. Hányféleképpen lehet szétosztani $n$ címkézett üveggolyót egy testvérpár között?

6. HF Hányféle nyaklánc készíthető 100 különböző gyöngyből?

7. HF Nyolc ember szeretne teniszezni három teniszpályán úgy, hogy az egyik pályán párost, a két másikon egyénit játszanak. Hányféleképpen tehetik ezt meg, ha a pályákat különbözőeknek tekintjük, de ugyanazon pálya két térfelét nem különböztetjük meg? (Természetesen az embereket is különbözoeknek tekintjük, és az is számít, hogy a négy páros meccset játszó játékos között ki kinek a partnere.)

8. HF 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. HF Milyen számosságúak az alábbi halmazok?
   1. Természetes számok véges részhalmazainak halmaza;
   2. Természetes számok részhalmazainak halmaza;
   3. Valós együtthatójú polinomok halmaza;
   4. Racionális együtthatójú polinomok halmaza;
   5. Egy háromszög belső pontjainak halmaza;
   6. Az olyan 0,1 és 2 számokat tartalmazó sorozatok, melyekben bármely három egymást követő elem összege osztható hárommal;
   7. Az olyan 0,1 és 2 számokat tartalmazó sorozatok, melyekben bármely három egymást követő elem összege osztható kettővel;
   8. Azon $(1, a_1, a_2, \dots)$ sorozatok halmaza, melyben a szomszédos elemek hányadosa 2 vagy $\frac{1}{2}$.

10. HF (érdekesség) Egy valós számot kiszámíthatónak nevezünk, ha van olyan Pascal nyelven írt program, amely a szám tizedesjegyeit meghatározza (pontosabban az $n$ bemenetre a szám első $n$ tizesedesjegyét számítja ki). Igazoljuk, hogy léteznek nem kiszámítható számok.

11. HF (érdekesség) A természetes számokon értelmezett tulajdonságot kiszámíthatónak nevezzük, ha létezik hozzá olyan program, amely tetszőleges $n$ számra eldönti, hogy a tulajdonság $n$-re teljesül-e. Például a ``hárommal való oszthatóság'' egy kiszámítható tulajdonság. Bizonyítsuk be, hogy létezik nem kiszámítható tulajdonság. (Segítség: a tulajdonság nem más, mint a számoknak egy részhalmaza, melyen a tulajdonság igaz.)