\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\addtolength\textwidth{3.0cm}
\addtolength\hoffset{-1.8cm}
\addtolength\textheight{4.0cm}
\setlength\topmargin{-1.5cm}

\begin{document}

{\centering {\LARGE Bevezetés a számításelméletbe I.}
\\\vspace*{1mm}
1. gyakorlat, 2005. szeptember 12.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace*{15mm}

\textbf{\LARGE Vegyes feladatok}\par}

\vspace*{10mm}

\begin{enumerate}

\item Helyezzünk el minél több azonos tisztet a sakktáblán úgy, hogy
semelyik kettő se üsse egymást. (Ez figuránként külön feladat.)

\item Két pohár közül az egyikben víz, a másikban ugyanannyi bor van.
Áttöltünk valamennyi vizet a boros pohárba, majd az abban lévő folyadékból
visszatöltünk ugyanennyit a vizet tartalmazóba. Miből lesz több: vízből az
eredetileg boros pohárban, vagy borból az eredetileg vizesben?

\item 13 pénzérme közül az egyik hamis, súlya eltér a többi súlyától.
Válasszuk ki a hamisat egy súlykészlet nélküli kétkarú mérleg segítségével
három méréssel.

\item Legalább hány embert kell kiválasztani ahhoz, hogy biztosan legyen
közöttük kettő, akinek ugyanannyi foga van?  És ahhoz, hogy biztosan legyen
közöttük kettő, akinek ugyanolyan a fogazata?

\item A végtelen négyzethálós papíron kijelöltünk száz mezőt. Igazoljuk,
hogy ezek közül ki lehet választani 25-öt, melyeknek páronként nincs közös
pontjuk.

\item Bizonyítsuk be, hogy egy hatfős társaságban van három ember, akik vagy
mind ismerik egymást, vagy pedig egyikük sem ismeri a másik kettő egyikét
sem. (Az ismeretség kölcsönös.)

\item A tér egy pontját rácspontnak nevezzük, ha mindhárom koordinátája
egész szám. Mutassuk meg, hogy bármely 9 rácspont közül van kettő, amelyek
által meghatározott szakasz felezőpontja is rácspont.

%\item A síkon véges sok pont helyezkedik el úgy, hogy bármely kettőre
%illeszkedő egyenesen van még legalább egy pont. Bizonyítsuk be, hogy e
%pontok egyetlen egyenesen vannak.

\item Egy dobozban 51 piros, 62 zöld és 30 sárga golyó van. Hányat kell
(csukott szemmel) kihúzni ahhoz, hogy biztosan legyen köztük\\
a) legalább két különböző?\\
b) legalább három piros?\\
c) legalább két azonos?

\item Egy sakktábla két átellenes sarkát lecsippentettük. Lefedhető-e az így
maradt tábla 31 darab $2\times1$-es dominóval?

%\item Adott a síkon végtelen sok pont. Bizonyítsuk be, hogy végtelen sok
%különböző távolság lép fel köztük.

%\item A mesebeli Csalafalván 100 házaspár él. Mindegyik férj tudja az
%összes asszonyról, hogy hűtlen-e, kivéve a saját feleségéről. Egy nap
%kiderül, hogy van hűtlen asszony a faluban. A férjek elhatározzák, hogy nem
%beszélnek egymással erről a kínos dologról, de az, aki saját felesége
%hűtlenségére rájön, másnap reggel 6-kor megkondítja a templom harangját,
%egyben jelezve, hogy megbüntette hűtlen asszonyát. Az első 99 reggelen a
%harangok nem szólaltak meg. Mi történt a századik
%reggelen?\hfill{}({$\star$})

%\item Strucctojás: egy adott magasságból leejtve vagy összetörik, vagy
%sértetlen marad. A strucctojások egyformák. Ha sértetlen maradt, akkor
%alacsonyabbról ledobva is sértetlen marad. Ha összetört, akkor egy másik
%strucctojást magasabbról ledobva az is össze fog törni. A feladat: Két
%tojás segítségével mondjuk meg egy 36 emeletes házban a strucctojás
%határmagasságát (melyik az az emelet, ahonnan még le lehet dobni úgy, hogy
%egészben maradjon, de magasabbról már nem). A tojásokat össze is törhetjük,
%de a második összetörése után már választ kell adnunk. Minimalizálandó a
%kísérletek száma a legrosszabb esetre.\hfill{}({$\star$})

\item Fogalmazzuk meg a következő állítás tagadását úgy, hogy ne szerepeljen
benne tagadószó: „Minden asszony életében van egy pillanat, hogy (=amikor)
szeretne olyat tenni, amit nem szabad.”

%\item Kör alakú mély tóban úszkál egy hittérítő. A tó partján megjelenik egy
%úszni nem tudó kannibál, aki a parton négyszer olyan gyorsan tud futni, mint
%ahogy a hittérítő úszik. Viszont a szárazföldön a hittérítő sokkal jobb
%futó, mint a kannibál. El tud-e menekülni a hittérítő az őt üldöző kannibál
%elől? (Ha igen, hogyan; ha nem, miért nem?)\hfill{}({$\star$})

%\item \textit{n} rabló talál por alakú aranyat. Ezen szeretnének mérleg és
%egyéb segédeszköz nélkül osztozkodni. Fontos, hogy egyikük se érezhesse úgy,
%hogy önhibáján kívül kevesebbet kapott a kincs \textit{n}-edrészénél. Két
%rablóra ismert a módszer: egyik oszt, másik választ. Vajon mi a helyzet
%$n>2$ esetén?\hfill{}({$\star$})

\end{enumerate}

\vspace*{10mm}

Számítástudományi és Információelméleti Tanszék:\\
\hspace*{1cm}I.B.132\\
\hspace*{1cm}\texttt{http://www.cs.bme.hu/}

Feladatsoraim:\\
\hspace*{1cm}\texttt{http://www.cs.bme.hu/\~{}egmont/bsz/}

BSz Fan Club:\\
\hspace*{1cm}\texttt{http://www.cs.bme.hu/\~{}zoli/bszfc/}

\end{document}
