\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}

\setlength{\hoffset}{-3 cm}
\setlength{\voffset}{-4 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\newcommand{\Komp}{\overline}


\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
1. Gyakorlat
}
\end{center}

\large
\begin{enumerate}
\item Van hat pár fekete és hat pár kék zoknink teljes
összevisszaságban egy fiókban. Sötét van. Hány zoknit kell
kihúznunk, hogy bizotsan legyen közöttük a) pár b) kék pár? És ha
cipőkről van szó?

\item Igazoljuk, hogy egy 100 fős társaságban mindig van legalább 9, aki 
ugyanabban a hónapban született? Melyik az a legkisebb létszám, amely 
mellett még igaz a fenti állítás?

\item Hány tizes számrendszerben pontosan 6 jegyű, tízzel nem osztható szám van?

\item Hány különböző autó-rendszám készíthető (három betűből és három számból)?

\item Hányféleképpen festhetjük egy n-emeletes ház szintjeit fehérre,
drappra és barnára, ha a szomszédos szintek nem élehetnek azonos színűek?

\item $(1+x)^n$ kifejtésében mennyi $x^k$ együtthatója? ($k=0,1,\dots,
n$)

\item Bizonyítsuk be a binomiális tételt: $(a+b)^n=\sum_{k=0}^n \binom
nk a^k b^{n-k}$

\item Hányféleképpen állíthatunk sorba $42$ fiút és $42$ lányt, ha
fiúk és lányok felváltva kell, hogy kövessék egymást? És ha csak 41
lány van?

\item Hányféleképpen állíthatunk sorba $k$ db egyest és $n-k$ db kettest?

\item Hatszor dobunk egy kockával. Hány olyan dobássorozat lehet,
amelyben dobtunk hatost?

\item Hányféleképpen tölthető ki egy totószelvény, úgy hogy legalább 
két döntetlenre akarunk tippelni?

\item Tíz urnába hányféleképpen helyezhető el 5
megkülönböztethetelen golyó?

\item (*) Tíz rabló el akar rejteni egy láda kincset. Úgy akarják
lakatokkal lezárni a ládát, hogy semelyik három ne tudja kinyitni, de
bármelyik négy már igen. Hány lakat kell, és hogyan osszuk szét a kulcsokat?

\item Van-e olyan (legalább két pontú egyszerű) gráf, amiben minden pont foka
különböző?

\item Bizonyítsuk be, hogy tetszőleges gráfban a páratlan fokú pontok
száma páros.

\item Legfeljebb hány éle van egy $n$ pontú egyszerű gráfnak?

\item Van-e olyen egyszerű gráf, amelyben a pontok foka rendre
\begin{enumerate}
\item $1,2,2,3,3,3$
\item $1,1,2,2,3,4,4$
\item $5,5,5,6,6,6,7,7,7$
\item $1,1,3,3,3,3,5,6,8,9$
\end{enumerate}

\item Van-e olyan 5, illetve 6 pontú (egyszerű) gráf, amelyre $G$
izomorf $\Komp G$-vel.

\item Hány olyan (nem izomorf) egyszerű gráf van, amelynek 60 csúcsa
és 1768 éle van?

\item Bizonyítsuk be, hogy $G$ és $\Komp G$ közül valamelyik
összefüggő.

\item Bizonyítsuk be, hogy ha egy $2n$ csúcsú egyszerű gráf minden
pontjának foka legalább $n$, akkor a gráf összefüggő.

\item Rajzoljuk fel az összes 3, 4 ill. 5 pontú fát! (Az izomorfakat
csak egyszer!)

\item Hány három pontú egyszerű irányított gráf van? (Oda-vissza élek
megengedettek.)

\item Hány olyan páronként nem izomorf 8 pontú fa van, amelyben
pontosan két harmadfokú pont található?

\item Legyen $\Delta$ egy fában a maximális fokszám. Bizonyítsuk be,
hogy a fa legalább $\Delta$ elsőfokú pontot tartalmaz!

\end{enumerate}
 
\end{document}
