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


\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 Milyen térbeli alakzat az alábbi három sík metszete?
\[ 
\begin{array}{rcl}
7x+10z&=&0\\
4x+y+6z&=&1\\
-3x+y-4z&=&1
\end{array}
\]

\mo
A három sík metszete az egyenletrendszer megoldásaként adódik. Ehhez 
el\-járhatunk például az alábbi módon:
Vonjuk ki a az utolsó egyenletet a másodikból. Az így kapott második 
egyenlet és az első megegyezik, tehát két egyenlettel (sorral) dolgozunk 
tovább. Szorozzuk a második sort héttel, majd adjuk hozzá az első 
háromszorosát, így azt kaptuk, hogy
\[ 
\begin{array}{rcl}
7x+10z&=&0\\
7y+2z&=&7
\end{array}
\]
Ez egy egyenes egyenlete.

\item Milyen $p$ paraméter esetén lesz az alábbi mátrix determinánsa 
$12$-vel egyenlő?
\[ \left(
\begin{array}{llll}
p&1&1&1\\
1&2&3&4\\
1&4&9&16\\
1&8&27&64
\end{array}
\right) \]

\mo
A szokásos műveletekkel ki lehet számolni paraméteresen a determináns 
értékét, így láthatóan lineáris egyenletet kapunk $p$-re, amit meg 
tudunk oldani. Egy másik lehetőség, hogy észrevesszük, hogy mátrixunk 
hasonlít az $1$, $2$, $3$ és $4$ számokhoz tartozó Vandermonde-determinánshoz.
Amennyiben $p=1$, ez éppen az. Ekkor a determináns értéke az ismert 
képletet felhasználva: $(2-1)(3-1)(3-2)(4-1)(4-2)(4-2)=12$. Azaz $p=1$ 
megoldás, ellenőriznünk kell még, hogy nincs több.
A fenti érvelés miatt lineáris az egyenlet $p$-re, tehát ebben $p$ 
együtthatója nem szabad, hogy $0$ legyen. A kifejtési tétel miatt a $p$-hez
tartozó aldetermináns nem nullaságát kell ellenőriznünk.

\item Írjuk fel az $A$ lineáris leképezés mátrixát a ,,szokásos'' 
$\V e_{1}$, $\V e_{2}$ bázisban, ha adott $\V v$ és $\V u$ vektor, amelyekre 
$A(\V e_{1}+\V e_{2}) = \V v$ és $A(\V e_{1}- \V e_{2}) = \V u$.

\mo
Az $A$ mátrixa $\left[ A(\V e_{1}), A(\V e_{2}) \right]$. 
Feladatunk tehát, hogy kifejezzük $\V v$ és $\V u$ segítségével ezeket.
Adjuk össze a két ismert egyenletet, majd osszuk le kettővel. Így kihasználva 
$A$ linearitását azt kapjuk, hogy:
\[
\frac{\V v + \V u}{2} = 
\frac{1}{2} \left( A(\V e_{1}+\V e_{2}) + A(\V e_{1}- \V e_{2}) \right) = 
\]
\[
\frac{1}{2} \left( A(\V e_{1}) + A(\V e_{2}) + A(\V e_{1}) - A(\V e_{2}) \right) = 
\frac{1}{2} \left( 2A(\V e_{1}) \right) = A(\V e_{1})
\]
Ha az $\V u$-ra vonatkozó egyenletet kivonjuk a másikból, majd osztunk 
kettővel, akkor teljesen hasonlóan megkapjuk, hogy 
\[
\frac{\V v - \V u}{2} = A(\V e_{2})
\]
Ezek szerint $A$ leképezés mátrixa
\[ \left[ \frac{\V v + \V u}{2}, \frac{\V v - \V u}{2} \right]
\]

\item Igazoljuk, hogy ha $G$ gráfnak $6$ pontja van, akkor vagy 
$G$, vagy $\overline G$ (a komplementere) síkbarajzolható.

\mo Ha $G$ síkbarajzolható, akkor nincs mit bizonyítanunk, tegyük 
fel tehát, hogy nem az. Akkor $G$-ben kell legyen egy ,,tiltott részgráf''.
Nézzük elsőként azt az esetet, ha a $K_{3,3}$ egy soros bővítését 
tartalmazza részgráfként $G$. Mivel gráfunk $6$ pontú, ezért a 
$K_{3,3}$ valódi soros bővítése nem fér bele. A $\overline{K_{3,3}}$ 
két diszjunkt háromszög, nyilván síkbarajzolható. Ha $G$-ben a 
$K_{3,3}$ részhez tartozó élek mellett továbbiak is szerepelnek, 
akkor a komplementerben csak kevesebb él lesz, következésképpen 
síkbarajzolható marad.
Hasonló érveléssel oldható meg a másik eset is. Amennyiben $G$-ben 
a $K_5$ szerepel, $\overline G$ síkbarajzolható, mert
látható, hogy a komplementerben úgy van a legtöbb 
él, ha $G$ éppen a $K_5$ és egy izolált pont uniója. $\overline G$ még 
ekkor is síkbarajzolható.

\item Legalább hány élet kell hozzávenni a Petersen-gráfhoz, hogy a 
keletkező gráfban legyen Hamilton kör?

\mo
Egyszerű próbálgatással könnyű találni a Petersen-gráfban Hamilton 
utat. Ezt egy éllel kiegészítve Hamilton kört kapunk. (Kevesebbel nem 
oldható meg, hiszen láttuk, hogy a Petersen-gráfban nincsen Hamilton kör.)

Valójában a feladatot elírtam, Euler körrel akartam feladni, az érdekesebb.

\item Hány különböző Hamilton kört, illetve utat tartalmaz az $n$ pontú teljes 
gráf?

\mo A gráf pontjainak tetszőleges sorrendjéhez található pontosan egy 
Hamilton út, sőt a pontok mind az $n!$ sorrendje 
különböző Hamilton utat ad. A körök összeszámolásakor rögzítsünk egy
kezdőpontot, ezután a többi pontot tetszőleges sorrendben járhatjuk be, 
ezért $(n-1)!$ különböző Hamilton kört kapunk.

\end{enumerate}

Minden feladat 10 pontot ér. 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}


