Bevezetés a számításelméletbe I. - Vizsgafeladatok
2000. január 5.


1. Az $a$ paraméter mely valós értékeire van megoldása az alábbi egyenletrendszernek?

\begin{displaymath}2x - y + z + t = 1 \end{displaymath}
\begin{displaymath}x + 2y - z + 4t = 2 \end{displaymath}
\begin{displaymath}x + 7y - 4z + 11t = a \end{displaymath}

2. A valós számok feletti $V$ vektortérnek egy bázisát alkotják a $b_1, \ldots, b_n$ vektorok. Legyen $v_1 = \alpha b_1 + b_2 + b_3 + \ldots +b_n$, $v_2 = b_1 + \alpha b_2 + b_3 + \ldots + b_n$, $\ldots$, $v_n = b_1 + b_2 + b_3 + \ldots + b_{n-1} + \alpha b_n$. Az $\alpha$ paraméter milyen értékeire lesz $v_1, v_2, \ldots, v_n$ szintén bázisa a $V$ vektortérnek?

3. Legyen $A$ valós (nem feltétlenül négyzetes) mátrix. Igazoljuk, hogy ha a $\lambda \ne 0$ valós szám sajátértéke az $A^T A$ mátrixnak, akkor sajátértéke az $A A^T$ mátrixnak is. ($A^T$ szokás szerint az $A$ mátrix transzponáltját jelöli.)

4. Határozzuk meg az összes olyan $z$ komplex számot, melyre $\bar{z} = z^n$, ahol $n$ rögzített pozitív egész szám.

5. Mi a számossága az olyan $x$ valós számok halmazának, melyekhez található olyan $n$ pozitív egész szám, amire $x^n$ racionális?

6. Megadható-e a Petersen-gráfnak két olyan egymással nem izomorf feszítőfája, melyekre igaz, hogy mindkét fában csak kétféle fokszám fordul elő?

7. Egy síkságon öt ház és öt kút áll. Minden háztól minden kúthoz külön ösvényt kell építenünk. Az építendő ösvények némelyike keresztezheti egymást, de egy-egy kereszteződésben legfeljebb két ösvény találkozhat. Mutassuk meg, hogy ekkor kilencnél kevesebb kereszteződéssel biztosan nem megoldható a feladat. (Hidak, alagutak nem építhetők, minden ösvényt a felszínen kell vezetni.)

8. Hány olyan hét számjegyből álló telefonszám adható meg, melynek első számjegye az 1, 2, 3, 4 számok valamelyike, és az első számjegy legalább még egyszer előfordul a telefonszámban?



Bevezetés a számításelméletbe I. - Vizsgafeladatok
2000. január 12.




1. Oldjuk meg az alábbi egyenletrendszert!

\begin{displaymath}2x-y+3z=3\end{displaymath}
\begin{displaymath}3x+y-5z=0\end{displaymath}
\begin{displaymath}4x-y+z=3\end{displaymath}

2. Legyenek $f_1(x), f_2(x), \dots, f_n(x)$ legfeljebb $(n-2)$-edfokú polinomok, $a_1, a_2, \dots, a_n$ pedig valós számok. Bizonyítsuk be, hogy az alábbi determináns értéke mindenképpen nulla.


\begin{displaymath}\left\vert\begin{array}{cccc}f_1(a_1)&f_1(a_2)&\dots&f_1(a_n)... ...dots\\ f_n(a_1)&f_n(a_2)& \dots&f_n(a_n)\end{array}\right \vert\end{displaymath}


3. Adjuk meg annak a $\phi$ lineáris leképezésnek a magterét, amelynek mátrixa

\begin{displaymath}\left (\begin{array}{ccc}2&3&4\\ 1&3&5\\ 1&6&11\\ 3&6&9\end{array}\right )\end{displaymath}

4. Oldjuk meg az alábbi egyenletet a komplex számok körében!

\begin{displaymath}(1+j)z+z^2=2j\end{displaymath}

5. Mi az olyan $z$ komplex számok halmazának számossága, amikre teljesül, hogy $z\cdot{\overline z}$ egész szám?

6. Hány pontja van a $T$ fának, ha éleinek száma pontosan tizenötöde a komplementerében levő élek számának? (Emlékeztetünk rá, hogy egy $G$ egyszerű gráf $\overline G$ komplementere az a gráf, melynek csúcshalmaza $G$-ével azonos, és éleit pontosan azok a csúcspárok alkotják, amelyek nem alkotnak élet $G$-ben.)

7. Legyen egy konvex test minden lapja négyszög vagy nyolcszög. Tegyük fel továbbá, hogy minden csúcsnál pontosan három lap találkozik. Mennyi ekkor a négyszög- és a nyolcszöglapok számának különbsége?

8. Hányféleképpen ültethető le egy harmincfős társaság $5$ darab, egyenként hatfős kerek asztalhoz, ha két ültetést akkor és csak akkor tekintünk azonosnak, ha a két ültetésben minden résztvevőnek ugyanaz mind a baloldali, mind a jobboldali szomszédja?



Bevezetés a számításelméletbe I. - Vizsgafeladatok
2000. január 26.




1. állapítsuk meg, mennyi a rangja az alábbi mátrixnak!

\begin{displaymath}\left(\begin{array}{rrrr}2&1&3&-1\\ 3&-1&2&0\\ 1&3&4&-2\\ 4&-3&1&1\end{array}\right)\end{displaymath}


2. Tegyük fel, hogy $v_1, v_2, \dots, v_n$ egy lineáris tér valamely bázisa. Igaz-e, hogy bázist alkotnak az alábbi vektorok is?

\begin{displaymath}v_1-2v_2+v_3, \ v_2-2v_3+v_4, \ \dots,\ v_{i-1}-2v_i+v_{i+1},\ \dots,\end{displaymath}
\begin{displaymath}v_{n-2}-2v_{n-1}+v_n, \ v_{n-1}-2v_n+v_1,\ v_n-2v_1+v_2\end{displaymath}


3. Legyen $f$ egy $V$ vektortéren értelmezett bilineáris függvény, amelyre teljesül, hogy minden a nullvektortól különböző $v\in V$-re $f(v,v)\ne 0$. Tegyük fel, hogy a $v_1, v_2, \dots, v_k$ vektorok olyanok, hogy rájuk $f(v_i,v_j)=0$ teljesül minden olyan $i,j$ értékpárra, amire $i\ne j$. Bizonyítsuk be, hogy ekkor $v_1, v_2, \dots, v_k$ lineárisan független vektorok.

4. Hozzuk kanonikus alakra az alábbi kifejezést!

\begin{displaymath}{(1+\sqrt{3}j)^{1998}\over {(1+j)^{2000}}}\end{displaymath}

5. Hányféleképpen írhatunk pozitív egész számokat a sík rácspontjaira, azaz egész koordinátájú pontjaira? (Egy-egy szám tetszőlegesen sok rácspontra ráírható.)

6. Hány olyan fa adható meg $n$ cimkézett ponton, melyben a pontpárok távolságai közül a legnagyobb hárommal egyenlő? (Két pont távolságán a köztük levő legrövidebb úton található élek számát értjük.)

7. Milyen $k$ pozitív egészekre adható meg olyan $2000$ élű és $2000$ csúcsú összefüggő gráf, amire igaz a következő: $G$-ben a $2000$ él közül adható egynek 2 egységnyi, $1999$-nek 1 egységnyi súly úgy, hogy a $G$-ből kiválasztható különböző minimális súlyú feszítőfák száma éppen $k$ legyen? (A feszítőfák megkülönböztetésekor a gráf csúcsait cimkézettnek tekintjük.)

8. Hány különböző módon cimkézhetjük meg egy kocka nyolc csúcsát az ábécé első nyolc betűjével? Két cimkézést akkor és csak akkor különböztetünk meg, ha az egyik cimkézéssel kapott kocka a háromdimenziós térben nem mozgatható át a másikba.