Bevezetés a számításelméletbe
11. gyakorlat, 2002. november 24.
Számosságok, leszámlálás
- (Múltkori feladatsorból) Bizonyítsuk be, hogy az alábbi halmazok megszámlálható (
) számosságúak.
- A sík egész koordinátájú pontjai;
- A sík racionális koordinátájú pontjai;
- A racionális számokból alkotott
-es mátrixok;
- Az egész koordinátájú háromszögek halmaza (egybevágó háromszögeket egyformáknak tekintünk);
- Azon bitsorozatok halmaza, amelyben véges sok 1-es fordul elő (de a sorozatok végtelen hosszúak).
- Igazoljuk, hogy az alábbi halmazok kontinuum (
) számosságúak.
- A végtelen hosszú bitsorozatok;
- A végtelen hosszú csak
,
és
szimbólumokat tartalmazó sorozatok halmaza;
- A háromdimenziós tér pontjainak halmaza;
- Valós számsorozatok halmaza;
- Az egész területű síkbeli háromszögek halmaza.
- Tíz gyerek hányféleképpen állítható úgy sorba, hogy Jancsi és Juliska egymás mellett álljanak?
- 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
- a három csapatnak van külön neve is;
- a csapatoknak nincs nevük.
- Hányféleképpen lehet szétosztani
címkézett üveggolyót egy testvérpár között?
- HF Hányféle nyaklánc készíthető 100 különböző gyöngyből?
- 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.)
- HF Hány olyan sorrendje van az
számoknak, amelyekben a páros és páratlan számok felváltva követik egymást?
- HF Milyen számosságúak az alábbi halmazok?
- Természetes számok véges részhalmazainak halmaza;
- Természetes számok részhalmazainak halmaza;
- Valós együtthatójú polinomok halmaza;
- Racionális együtthatójú polinomok halmaza;
- Egy háromszög belső pontjainak halmaza;
- Az olyan 0,1 és 2 számokat tartalmazó sorozatok, melyekben bármely három egymást követő elem összege osztható hárommal;
- Az olyan 0,1 és 2 számokat tartalmazó sorozatok, melyekben bármely három egymást követő elem összege osztható kettővel;
- Azon
sorozatok halmaza, melyben a szomszédos elemek
hányadosa 2 vagy
.
- 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
bemenetre a szám első
tizesedesjegyét számítja ki). Igazoljuk, hogy léteznek nem kiszámítható számok.
- 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
számra eldönti, hogy a tulajdonság
-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.)
Fogaras Daniel
2002-12-02