\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\pagestyle{empty}
\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-1.5cm}
\addtolength\textwidth{3.8cm}
\addtolength\hoffset{0cm}
\addtolength\textheight{5.0cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe I.}
\\\vspace*{1mm}
9. gyakorlat, 2005. november 14.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{12mm}
\textbf{\LARGE Számosságok}
\end{center}

\vspace*{8mm}

\begin{enumerate}
\setcounter{enumi}{89}

\item Adjuk meg a következő halmazok számosságát:
\begin{enumerate}
\item A természetes számok véges részhalmazai.
\item A természetes számok részhalmazai.
\item Azok az $1, a_1, a_2, \ldots$ sorozatok, melyekben a szomszédos elemek
       hányadosa $1/2$ vagy $2$.
\item Azok az $x$-ből és $y$-ból álló sorozatok, melyekben csak véges sok
       $y$ fordul elő.
\item Az egész számokból álló (véges méretű) mátrixok.
\item Azon síkbeli háromszögek, melyeknek minden koordinátája egész szám.
\item Azon síkbeli háromszögek, melyeknek a területe egész szám.
\item A síkon egy háromszög belső pontjai.
\item A racionális számokból álló végtelen sorozatok.
%\item A természetes  számok összes permutációja (azon sorozatok, melyekben
%       minden elem csak egyszer fordul elő).
%\item A folytonos valós függvények.
\end{enumerate}

%\item Most átnyargalunk a formalizmusra. Bebizonyítandók a következők:
%\begin{enumerate}
%\item $\omega^c=c$
%\item $\omega^\omega=c^\omega=c$
%\item $2^c=\omega^c=c^c$
%\end{enumerate}

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

\item Hány olyan ($x$,$y$) pontpár van a síkon, melyre
\begin{enumerate}
\item $x$ és $y$ is racionális,
\item $x$ és $x+y$ is racionális,
\item $x$ és $xy$ is racionális,
\item $x+y$ és $xy$ is racionális?
\end{enumerate}

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

\item 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?

\item 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?

\item Adjunk bijekciót (oda-vissza egyértelmű leképezést) az alábbi halmazok
között.
\begin{enumerate}
\item $[0,1]$ és $(0,1)$
\item $(0,1)$ és $(-\infty,\infty)$
\item $(0,\infty)$ és $(-\infty,\infty)$
%\item \textsl{\{valós számok\}} és \textsl{\{irracionális számok\}}
\end{enumerate}

\item 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?

\item 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?

\item Egy valós számot nevezzünk \textit{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.)

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

%
% Jövőre mindenképp berakni!!! (Átfogalmazva normálisabbra...)
%
% Határozzuk meg azon végtelen hosszú, $a$ és $b$ betűkből álló sorozatok
% halmazának számosságát, melyekben minden kezdőszeletben legalább annyi $a$
% betű szerepel, mint $b$!
%

\end{enumerate}

\end{document}
