Bevezetés a számításelméletbe I.

13. gyakorlat, 2006. december 13.

                                    Koblinger Egmont <egmont@cs.bme.hu>

Számosságok

146. Adjuk meg a következő halmazok számosságát:

(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}, … sorozatok, melyekben a szomszédos elemek hányadosa 1/2 vagy 2.

(d) Azok az x-ből és y-ból álló végtelen hosszú sorozatok, melyekben csak véges sok y fordul elő.

(e) Azok az x-ből és y-ból álló végtelen hosszú sorozatok, melyeknek minden kezdőszeletében legalább annyi x betű szerepel, mint y.

(f) Az egész számokból álló (véges méretű) mátrixok.

(g) Azon síkbeli háromszögek, melyeknek minden koordinátája egész szám.

(h) Azon síkbeli háromszögek, melyeknek a területe egész szám.

(i) A síkon egy háromszög belső pontjai.

(j) A racionális számokból álló végtelen sorozatok.

(k) A természetes számok összes permutációja (azon sorozatok, melyekben minden elem csak

egyszer fordul elő).

147. Hány olyan (x,y) pontpár van a síkon, melyre (a) x és y is racionális,

(b) x és x + y is racionális,

(c) x és xy is racionális,

(d) x + y és xy is racionális?

148. Mi az olyan z komplex számok halmazának számossága, amikre teljesül, hogy z · \overline{z} egész szám?

149. Mi a számossága annak a számhalmaznak, melynek elemei azok a számok, melyek felírhatók a+b\sqrt{k} alakban úgy, hogy k pozitív egész, a és b pedig racionális számok?

150. Tekintsük a síkon azon négyzetek halmazát, melyeknek legalább az egyik csúcsa egész koordinátájú. Mennyi ennek a halmaznak a számossága?

151. Adjunk bijekciót az alábbi halmazok között.

(a) [0, 1] és (0, 1)

(b) (0, 1) és (−∞, ∞)

(c) (0, ∞) és (−∞, ∞)

(d) {valós számok} és {irracionális számok}

152. 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?

153. Egy tengeralattjáró egyenes vonalú egyenletes mozgást végez, és percenként egyszer felbukkan egész koordinátájú pontokban. Írható-e előre program a tengeralattjáró megsemmisítésére?

154. Egy valós számot nevezzünk kiszámíthatónak, ha van hozzá olyan C nyelven írt program, amellyel a tizedesjegyeit 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.)

155. Hány egyenessel lehet lefedni a síkot?

156. Legfeljebb hány 8-as helyezhető el a síkon úgy, hogy ne messék egymást?

157. Hány T betű helyezhető el a (0, 1) szakaszon?