\documentclass[10pt]{article}


%%%%%%%% magyaritashoz
\usepackage{t1enc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing

%%%%%%% grafikus csomag abrakhoz
\usepackage{graphicx,amssymb}

%%%%%%%%%% definiciok

\newcommand{\mo}[1]{\textit{Megoldás:} #1}

%\newcommand{\mo}[1]{}

%%%%%%%%%%%% oldalmeret

\setlength{\textheight}{25cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-1cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

%%%%%%% ne legyen fejsor, labsor (oldalszam)
\pagestyle{empty}


%%%%%%% cim
\begin{document}
\centerline{\Large \textbf{Számítástudomány alapjai gyakorlat (1)}}
\vspace*{.5cm}


%%%%%%%%%%%% feladatok
\begin{enumerate}
\item Hányféleképp festhetjük egy  $n$-szintes ház szintjeit fehérre,
  drappra és barnára, ha szomszédos szintek nem lehetnek egyszínűek?


\item Hányféle anagramma készíthető a MATEMATIKA betűiből?

\mo{$\frac{10!}{2!\cdot 3!\cdot 2!}=151 200$}

\item Egy  $8$ fiúból és $5$ lányból álló társaságból hányféleképp
  választhatunk ki $6$ főt úgy, hogy legalább $2$ lány legyen köztük?

\mo{\[{13 \choose 6}-{8\choose 6}-{5\choose 1}{8\choose 5}={5\choose 2}{8\choose 4}+{5\choose 3}{8\choose 3}+{5\choose 4}{8\choose 2}+{5\choose 5}{8\choose 1}=1408\]}

% \item Az $1,2,\ldots, 100$ számok közül hányféleképp lehet
%   kiválasztani hármat úgy, hogy az összegük osztható legyen $3$-mal?


\item[HF.]  Egy $n\times n$-es sakktábla bal felső sarkából kell egy királyt
  a jobb alsó sarokba eljuttatni úgy, hogy csak lefelé és jobbra
  szabad lépni. Hány különböző úton mehet a király?

  
\item Bizonyítsuk be, hogy 
  \[\sum_{i=0}^n {n\choose i}{r\choose k-i} ={n+r\choose k}.\]


\item 17 doboz mindegyikében piros, kék, sárga és zöld golyók
  vannak. Bizonyítsuk be, hogy található két olyan doboz, amelyekben
  együttvéve mind a négyféle golyóból páros sok van.

\mo{A színek paritása szerint címkézzük fel a dobozokat. Skatulya elv miatt van két egyforma címke.}

\item Bizonyítsuk be, hogy az $1,2,\ldots, 2n$ számok közül akárhogy
  is választunk ki $n+1$-et, lesz közöttük
\begin{enumerate}
\item két relatív prím,

\item kettő, hogy az egyik osztja a másikat.
\end{enumerate}

\item Izomorfak-e az  ábra   gráfjai?
  \begin{center}
    \includegraphics{muab1}
\end{center}

\item Legyen $d_1, d_2, \ldots, d_n$  olyan  pozitív  egészek  sorozata,
    melyek összege $2n-2$. Mutassuk meg, hogy van olyan $n$-pontú fa,
    melynek épp ezek a fokszámai!

\item Van-e Hamilton--köre ill. --útja az ábrán látható gráfnak?
\begin{center}
  \includegraphics[height=3cm]{muab9}
\end{center}

\item Határozzuk meg az ábrán látható gráfok által szemléltetett
  tevékenységekhez szükséges időt! Mely feladatok kritikusak?
\begin{figure}[ht]
\begin{center}
  \input{2muab13.pstex_t}
\end{center}
\end{figure}




\item Legyen $\Delta (G)$ egy gráfban a maximális fokszám. Bizonyítsuk be, hogy
$\Delta (G)\tau (G)\ge |E(G)|$.

\item Tegyük fel, hogy a $G=(A,B;E)$ páros gráfban minden $X\subseteq
  A$-ra teljesül, hogy $|N(X)|\ge |X|+1$. Bizonyítsuk be, hogy minden
  $e$ élhez van olyan $A$-t lefedő párosítás, ami tartalmazza $e$-t.

\item Legyen $V(G)=\{v_1,\ldots, v_{106}\}$. $v_i$ és $v_j$ között
  akkor és csak akkor van él, ha $|i-j|\leq 7$. Mennyi $G$ kromatikus
  száma, $\chi(G)$?

{\bf Az alábbi problémáknak határozzuk meg a bonyolultságát!}

\item \begin{description}
\item{\bf Input:} $G$ gráf és $S\subseteq V(G)$
\item{\bf Kérdés:} Létezik-e olyan $G$-beli kör, ami $S$ minden pontján
átmegy? 
\end{description}

\item   Döntsük   el,   hogy   megoldhatóak-e    az    alábbi
       kongruenciák, és a megoldhatókat oldjuk \dotfill meg:
\begin{enumerate}
\item  $3x \equiv  5\ (\bmod 7 )$, \mo{$x=4$}
\item $14x \equiv  8\ (\bmod 21 )$, \mo{nincs mo}
\item $11x \equiv 12\ (\bmod 18 )$, \mo{$x\equiv 6 (\bmod 18)$}
\item $9x \equiv 24\ (\bmod 96 )$, \mo{$x\equiv 24 (\bmod 32)$}
\end{enumerate}

\item Csoport-e?
  \begin{enumerate}
 % \item $(\mathbb{Z}_2,\cdot)$; \mo{$0$-nak nincs inverze}
  \item $(\mathbb{Q}-\{0\},\circ)$, ahol $x\circ y=x/y$; \mo{nem asszoc}
  \item $(\mathbb{R}-\{-1\},\circ)$, ahol $x\circ y=x+y+xy$; \mo{OK}
 % \item a sík egybevágósági trafói az \textit{egymásután végzés}
    műveletre; \mo{OK}
  \item egy $k$ elemű halmaz részhalmazai a következő műveletre:
    $X\triangle Y=(X-Y)\cup (Y-X)$; \mo{OK egység $\emptyset$, inverz
      önmaga}
  \item $(\mathbb{Z},\circ)$, ahol $k\circ m=k+m$ ha $k$ páros és
    $k\circ m=k-m$ ha $k$ páratlan; \mo{asszoc, egység $0$, inverz
      $-k$ ha páros, $k$ ha páratlan}
  \end{enumerate}
\end{enumerate}

\[ \left(\begin{array}{|c|c|c|}
\hline
  1&2&3\\ \hline
2&2&2\\ \hline
\end{array}\right)\]

\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 