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


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

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

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

\addtolength{\textwidth}{5cm}
\addtolength{\textheight}{6cm}
\setlength{\hoffset}{-2.5cm}
\setlength{\voffset}{-3cm}


\frenchspacing

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


\begin{enumerate}

\item Határozzuk meg a $\lambda$ paraméter függvényében az alábbi mátrix
rangját: 

\[ \left (
\begin{array}{llll}
\lambda&1&1&1\\
1&\lambda&1&\lambda\\
1&1&\lambda&\lambda^2
\end{array}
\right ) \]

\mo
Látható, hogy $\lambda = 1$ esetén a mátrix rangja 1.
Sorainak száma miatt a rang biztosan $\le 3$. Igazolni fogjuk, 
hogy $1$-től különböző $\lambda$ esetén a rang $3$.
Vonjuk ki a negyedik oszlopból a másodikat. Ha $\lambda \ne 1$, 
akkor $\lambda^2-1\ne 0$, ezért leoszthatjuk ennyivel az utolsó 
oszlopot. Elhagyva az első oszlopot a kapott mátrix:
\[ \left (
\begin{array}{lll}
1&1&0\\
\lambda&1&0\\
1&\lambda&1
\end{array}
\right ) \]
Ennek determinánsa $1-\lambda$, ami kikötésünk szerint nem lehet $0$.
Mutattunk tehát $\lambda \ne 1$ esetén egy $3\times 3$-as nem nulla 
aldeterminánst, így ez esetben a rang $3$.

\item Bizonyítsuk be, hogy ortogonális mátrix determinánsa $+1$ vagy $-1$.

\mo
Legyen $A$ ortogonális mátrix. Ekkor $A\cdot A^T = E$. Ennek az egyenlőségnek 
tekintsük a determinánsát. $\det E = 1$, a bal oldalon pedig alkalmazzuk a 
determinánsok szorzástételét. Azt kapjuk, hogy 
$\det A \cdot \det A^T = 1$. Tekintve, hogy $\det A^T = \det A$, ezért 
$\left( \det A \right)^2 = 1$, amiből már következik az állítás. 

\item Írjuk fel annak a lineáris transzformációnak a mátrixát a szokásos
bázisban, amely a háromdimenziós teret az $\left (
\begin{array}{c}1\\1\\1\end{array} \right )$ vektor körül jobbkézszabály
szerint $120^{\circ}$-kal elforgarja.

\mo
Ez a leképezés az $x$, $y$ és $z$ tengelyt ciklikusan egymásba viszi 
(méghozzá ebben a sorrendben). Ezt például onnan lehet látni, hogy 
a koordinátatengely irányú egységvektorok végpontjai egy szabályos 
háromszöget alkotnak, amely síkja merőleges a forgatás tengelyére 
(azaz a forgatás önmagába viszi) és amelyet az a szimmetria 
miatt éppen középpontjában döfi át. Tehát transzformációnk ebben a 
síkban éppen a középpont körüli $120^{\circ}$-os forgatás, ami a 
csúcsokat valóban ciklikusan egymásba viszi.
Ezek szerint a mátrixa:
\[ \left(
\begin{array}{lll}
0&1&0\\
0&0&1\\
1&0&0
\end{array}
\right) \]

\item Egy 15 tagú klub elnököt, titkárt, jegyzőt és pénztárost választ. A 
népszerű (befolyásos) Kovács úrnak mindenképpen szeretnének valamilyen 
tisztséget adni. Hányféle lehet a vezetőség?

\mo
Kovács úr tisztsége $4$ féle lehet, a maradék $3$ poszt közül az 
elsőre $14$, a másodikra $13$, a harmadikra $12$ jelölt van. Ez
összesen $4 \cdot 14 \cdot 13 \cdot 12 = 8736$ lehetőség.

\item Egy hatelemű halmaz kételemű részhalmazai legyenek egy gráf pontjai. 
Két pont akkor legyen összekötve éllel, ha nekik megfelelő részhalmazok 
diszjunktak (metszetük üres). Igazoljuk, hogy nem síkbarajzolható ez a gráf.

\mo
Egyik lehetőség, hogy észrevesszük, hogy minden pont foka 
$\binom{4}{2}=6$, amiről ismert, hogy lehetetlen síkgráf esetén.
(A fokszám azért annyi, mert a rögzített csúcs az eredeti halmaz két
eleméből álló halmaz, a maradék négy elemből pedig pontosan ennyi 
kételemű halmaz választható ki.)

Igaz az is, hogy amennyiben elhagyunk egy pontot az alaphalmazból, 
(azaz ötelemű alaphalmazon tekintjük a hasonló konstrukciójú gráfot,)
akkor a Petersen gráfot kapjuk. Az nem síkbarajzolható, tehát az őt 
részgráfként tartalmazó eredeti gráfunk sem lehet az.

Némi rajzolgatás után meg lehet találni benne a $K_{3,3}$ egy soros 
bővítését is.

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

\mo
18

\end{enumerate}

Minden feladat 10 pontot ér, 100 \%-os teljesítményhez 60 pontot kell
elérni. Részeredményekért is jár pont, bizonyítás nélküli eredményközlésért
azonban nem. Ponthatárok: 0--23: 1; 24--32: 2; 33--42: 3; 43--51: 4; 52--60+: 5.


\end{document}
