\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage[latin2]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[mathscr]{eucal}
%\usepackage{mathbbm}
\usepackage{color}
\usepackage{epic}
\usepackage{amssymb}


\newcommand{\Conj}[1]{\overline{#1}}
\newcommand{\Halm}[1]{\mathbf{#1}}

\newcommand{\V}{\underline}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Ker}{\mathrm{ker}}
\newcommand{\Dim}{\mathrm{dim}}
\newcommand{\Lek}[1]{{\cal #1}}
\newcommand{\im}{\mathop{\mathrm{Im}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}

\newcommand{\mo}{{\bf Megoldás:}\\}

\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{7cm}
\setlength{\hoffset}{-3cm}
\setlength{\voffset}{-3.5cm}


\frenchspacing

\begin{document}
\begin{center}
{\LARGE \bf Bevezetés a számításelméletbe (kieg.)}\\
{\bf Második zárthelyi, megoldások}\\
\end{center}
{\Large

\begin{enumerate}

\item Oldjuk meg az alábbi egyenletet a komplex számok körében: $z^2=i|z|$.

\mo
Írjuk fel $z$-t trigonometrikus alakban: 
$z = r (\cos \varphi +i \sin \varphi)$.
A négyzetre emelés így könnyen elvégezhető és $|z|=r$. Az egyenletünk ezért: 
\[ r^2 (\cos 2\varphi +i \sin 2\varphi) = ir\]
$r=0$, azaz $z=0$ láthatóan megoldás. $r \ne 0$ esetben leoszthatunk $r$-rel.
Írjuk át $i$-t is trigonometrikus alakba:
\[ r (\cos 2\varphi +i \sin 2\varphi) = \cos\frac{\pi}{2} +i \sin\frac{\pi}{4}\]
Innen --- kihasználva, hogy két nem $0$ komplex szám pontosan akkor egyenlő, 
ha abszolútértékük és argumentumuk is megegyezik --- következik $r=1$ és 
$2\varphi =\frac{\pi}{2}+2k\pi$, $k\in\Halm N$, ebből $\varphi = \frac{\pi}{4}$, 
vagy $\varphi = \frac{\pi}{4}+\pi$. Tehát az egyenletet a $0$, a 
$\cos\frac{\pi}{4} +i \sin\frac{\pi}{4} = \frac{1}{\sqrt 2}+i\frac{1}{\sqrt 2}$ 
és a $\cos\frac{5}{4}\pi +i \sin \frac{5}{4}\pi = 
-\frac{1}{\sqrt 2}-i\frac{1}{\sqrt 2}$ elégíti ki.


\item Öt ismerős házaspár mindkét tagjának két-két különböző képeslapot
szeretnénk küldeni úgy, hogy családon belül se legyen ismétlődés. (Összesen
tehát húsz lapot küldünk ki.) Hányféleképpen tehetjük meg ezt, ha $k$ féle
képeslap van és mindegyikből elegendően sok áll rendelkezésre?

\mo
Először válasszunk minden családnak $4$-$4$ lapot. Ezt családonként 
$\binom{k}{4}$, tehát összesen $\binom{k}{4}^5$ féleképpen tehetjük meg.
Másodszor minden családon belül osszuk el a férj és feleség között a 
lapokat: négy lap közül kettőt kell kijelölnünk példaul a férfi számára, 
erre mind az $5$ családban $\binom{4}{2}$ lehetőségünk van. Összesen ez
$\binom{k}{4}^5\binom{4}{2}^5$.

\item Hogy néz ki az a lehető legkevesebb csúcsot tartalmazó egyszerű gráf,
amelyben minden csúcs fokszáma 3 és a legrövidebb kör pontosan 4 hosszú?

\mo
Próbáljuk meg felrajzolni a gráfot. Kezdjük a négy hosszú körrel. Ennek minden 
csúcsából kiindul egy-egy él. Ezek közül a szomszédos csúcsból indulók nem 
érkezhetnek ugyanazon csúcsba, ezért fel kell még vennünk legalább két pontot
(a kör négy pontján kívül). Ezen pontok egyikébe beköthetjük a négyszög 
két szemközti csúcsát, másikba a másik két szemköztit. Ha még ezen két új 
pontot is összekötjük, akkor a feltételeknek megfelelő 6 pontú gráfot kaptunk 
és a konstrukció menete mutatja, hogy ez minimális. Észrevehetjük, hogy a 
kapott gráf éppen a $K_{3,3}$. Egy másik lehetséges megoldás:
négypontú nem lehet a gráf, mivel akkor csak úgy lesz minden pont harmadfokú, 
ha teljes a gráf, de ekkor bőven van benne háromszög. Öt ponton nem lehet 
csupa harmadfokú pont, hiszen így a fokszámösszeg $15$ lenne, ami biztosan 
nem az élszám kétszerese. Hat ponton pedig a $K_{3,3}$ megfelelő gráf.

\item Írjuk fel az $\Halm R^3$ szokásos bázisában a mátrixát annak a
lineáris transzformációnak, amely a következőképpen hat: először a Z irányú
egységvektor körül (jobb\-kéz\-sza\-bály szerint) $\varphi$ szöggel forgat, majd
az XZ koordinátasíkra tükröz.

\mo
A $\varphi$ szögű forgatás hasonlóan hat, mint az XY síkban középpont 
körüli forgatás, a Z irányú koordinátát változatlanul hagyja.
Ezért a mátrixa $A= \left(
\begin{array}{rrr}
\cos\varphi & -\sin\varphi & 0 \\
\sin\varphi & \cos\varphi & 0 \\
0 & 0 & 1\\
\end{array}
\right )$ Az XZ síkra tükrözés a vektorok Y koordinátáját változtatja 
az ellentetjére, azaz $B= \left(
\begin{array}{rrr}
1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1\\
\end{array}
\right )$ Az összetett leképezés ezért $B \cdot A=\left(
\begin{array}{rrr}
\cos\varphi & -\sin\varphi & 0 \\
-\sin\varphi & -\cos\varphi & 0 \\
0 & 0 & 1\\
\end{array}
\right )$

\item Bizonyítsuk be, hogy egy $A: V \rightarrow V$ lineáris
transzformációra az alábbi feltételek ekvivalensek:
\begin{enumerate}
\item Minden vektor előáll képként.
\item Tetszőleges két különböző vektor képe is különböző.
\end{enumerate}

\mo
Igazoljuk elsőként, hogy a második feltétel jelentése: 
$\Ker A = \{ \V 0 \}$. Ha $\exists \V v \in \Ker A$, amelyre 
$\V v \ne \V 0$, akkor $A\V v = A\V 0$ miatt nem teljesül a második 
feltétel. Amennyiben $\Ker A = \{ \V 0 \}$, akkor tetszőleges két 
vektor képe különböző, hiszen $A\V v = A\V w$ esetén $A$ linearitása 
miatt $A(\V v -\V w) = \V 0$, azaz $(\V v -\V w)\in\Ker A$, ezért 
$\V v -\V w = \V0$, $\V v =\V w$. Feladatunk, hogy igazoljuk: 
$\Ker A = \{ \V 0 \} $ ekvivalens $\im A = V$-vel (utóbbi láthatóan az 
első feltétel átfogalmazása). Írjuk fel a dimenziótételt:
$\Dim \im A+\Dim \Ker A = \Dim V$. $\im A = V$ ekvivalens 
$\Dim\im A = \Dim V$-vel és a dimenziótétel szerint ez egyenértékű 
$\Dim\Ker A = 0$-val. Utóbbi azonban $\Ker A = \{ \V 0 \} $ egy 
átfogalmazása, tehát állításunkat ezzel beláttuk.

\item Van-e Euler, illetve Hamilton útja, illetve köre az alábbi gráfnak?

\begin{center}
\input{./zh2euham.epic}
\end{center}

\mo
A gráf a Petersen gráf egy lerajzolása. Erről órán igazoltuk, hogy nincs 
Hamilton köre. Hamilton út könnyen található benne. Mivel $10$ darab páratlan 
fokú csúcsa van, ezért nincs Euler út ($0$, vagy $2$), sem kör ($0$ 
páratlan csúcs mellett van csak).

\item Határozzuk meg az alábbi PERT diagramra a folyamat befejezésének
legkorábbi idejét és a kritikus uta(ka)t:

\begin{center}
\input{./zh2pert.epic}
\end{center}

\mo
Az egyes munkafázisok elkezdési idői: S: 0, B: 3, A: 5, D: 7, C: 9,
E: 16, F: 20, H: 24, I:26, G: 28, T:28. Kritikus utak SBCEFHT, SBCEFHGT, 
SCEFHT és SCEFHGT.

\item Mennyi a maximális $s \rightarrow t$ folyam az alábbi gráfban:
\begin{center}
\input{./zh2foly.epic}
\end{center}

\mo
A maximális folyamérték 21.

\end{enumerate}


\end{document}
