\documentclass[12pt]{article} \usepackage{amsmath, amssymb} \usepackage[magyar]{babel} \usepackage[latin2]{inputenc} \newcommand{\cd}{\cdot} \def\N{\ensuremath{\mathbb N}} %natural numbers \def\T{\ensuremath{\mathbb T}} %torus \def\R{\ensuremath{\mathbb R}} %real numbers \def\Q{\ensuremath{\mathbb Q}} %rational numbers \def\C{\ensuremath{\mathbb C}} %complex numbers \def\Z{\ensuremath{\mathbb Z}} %integers \newcommand{\caq}{{\cal Q}} \newcommand{\can}{{\cal N}} \newcommand{\cooo}{C^{1}[0,1]} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\tlll}{{\widetilde{\lambda}}} \newcommand{\off}{{\overline{f}}} \newcommand{\tq}{{\widetilde{q}}} \newcommand{\veee}{{\varepsilon}} \newcommand{\cai}{{\cal I}} \newcommand{\caa}{{\cal A}} \newcommand{\xx}{\times} \newcommand{\cas}{{\cal S}} \newcommand{\caj}{{\cal J}} \newcommand{\cae}{{\cal E}} \newcommand{\cah}{{\cal H}} \newcommand{\cau}{{\cal U}} \newcommand{\cak}{{\cal K}} \newcommand{\car}{{\cal R}} \newcommand{\cam}{{\cal M}} \newcommand{\defeq}{{\buildrel {\rm def}\over =}} \newcommand{\cat}{{\cal T}} \newcommand{\capp}{{\cal P}} \newcommand{\tqjm}{{\widetilde{q}}_{j,m}} \newcommand{\tUU}{\widetilde{U}} \newcommand{\oN}{\overline{N}} \newcommand{\offf}{\overline{\phi}} \newcommand{\fff}{{\phi}} \newcommand{\fffojm}{{\phi}_{0,j,-}} \newcommand{\fffsojm}{{\phi}^{*}_{0,j,-}} \newcommand{\hfff}{\widehat{\phi}} \newcommand{\cab}{{\cal B}} \newcommand{\caf}{{\cal F}} \newcommand{\ds}{\displaystyle} \newcommand{\eee}{\epsilon} \newcommand{\eqq}{\equiv} \newcommand{\aaa}{\alpha} \newcommand{\bbb}{\beta} \newcommand{\fim}{f_{1,m}} \newcommand{\fiim}{f_{2,m}} \newcommand{\fiiim}{f_{3,m}} \newcommand{\pf}{\noindent{\sc Proof. }} \newcommand{\ddd}{\delta} \newcommand{\zzz}{\zeta} \newcommand{\oS}{{\overline{S}}} \newcommand{\ubb}{{\underline{\beta}}} \newcommand{\utt}{{\underline{\theta}}} \newcommand{\ttt}{\theta} \newcommand{\GGG}{\Gamma} \newcommand{\hGGG}{{\widehat{\Gamma}}} \newcommand{\trrr}{{\widetilde{\rho}}} \newcommand{\DDD}{\Delta} \newcommand{\FFF}{\Phi} \newcommand{\PPP}{\Psi} \newcommand{\tFFF}{{\widetilde{\Phi}}} \newcommand{\tPPP}{{\widetilde{\Psi}}} \newcommand{\LLL}{\Lambda} \renewcommand{\lll}{\lambda} \newcommand{\LOG}{\log} \renewcommand{\ggg}{\gamma} \newcommand{\OOO}{\Omega} \newcommand{\pq}{(\frac{p}{q})} \newcommand{\gr}{\nabla} \newcommand{\eimo}{E_{1,m_{0}}} \newcommand{\mo}{m_{0}} \newcommand{\uy}{{\bf {y}}} \newcommand{\ux}{{\bf {x}}} \newcommand{\up}{{\bf {p}}} \newcommand{\uh}{{\bf {h}}} \newcommand{\uv}{{\bf {v}}} \newcommand{\uw}{{\bf {w}}} \newcommand{\dd}{\partial} \newcommand{\harr}{\hookleftarrow} \newcommand{\pqq}{\frac{p}{q}} \newcommand{\ppp}{\psi} \newcommand{\kkk}{\kappa} \newcommand{\oo}{\infty} \newcommand{\sse}{\subset} \newcommand{\ess}{\emptyset} \newcommand{\sm}{\setminus} \newcommand{\cag}{{\cal G}} \newcommand{\I}{{\mathbf{1\!\!\!1}}} \newcommand{\bT}{{\mathbf{T}}} \newcommand{\bN}{{\mathbf{N}}} \setlength{\topmargin}{-2cm} \setlength{\textheight}{25cm} \pagestyle{empty} \begin{document} \sloppy \begin{center} {\bf A 2006. \'evi Schweitzer Mikl\'os Eml\'ekverseny feladatai} okt\'ober 27 - november 6. \end{center} \thispagestyle{empty} \begin{enumerate} \item Egy $X$ topologikus t\'er $d(X)$ s\H ur\H us\'ege az a legkisebb sz\'amoss\'ag, amire van $X$-nek ilyen sz\'amoss\'ag\'u s\H ur\H u altere. Bizony\'itand\'o, hogy ha $X$ tetsz\H oleges kompakt $T_2$ t\'er, akkor $X^3$ tartalmaz $d(X)$ sz\'amoss\'ag\'u diszkr\'et alteret. \item Legyen $T$ v\'eges fagr\'af, mely nem csak egy cs\'ucsb\'ol \'all. Legyen $s$ a legnagyobb olyan $X \subset T$ r\'eszfa cs\'ucssz\'ama, amire $X$ minden cs\'ucs\'anak van $X$-en k\'iv\"uli szomsz\'edja. Legyen $t$ a legkisebb olyan pozit\'iv eg\'esz, amire megadhat\'o $T$-beli csillagok $C_1,\dots,C_k$ rendszere, hogy $T$ minden \'el\'et ezek k\"oz\"ul pontosan $t$ tartalmazza, \'es $T$ minden cs\'ucs\'at ezek k\"oz\"ul maximum $2t-1$ tartalmazza. (Azaz a csillagok multiplicit\'assal szerepelhetnek.) Bizony\'itsuk be, hogy $s=t$. \item Jel\"olje $f(n)$ a legkisebb olyan pozit\'\i v eg\'esz sz\'amot, amelyre igaz a k\"ovetkez\H o \'all\'\i t\'as. Ha a s\'\i k $f(n)$ \'altal\'anos helyzet\H u pontja \'altal meghat\'arozott z\'art szakaszok mindegyik\'et megsz\'\i nezz\"uk n\'egy sz\'\i n valamelyik\'evel, akkor tal\'alhat\'o $n$ p\'aronk\'ent diszjunkt azonos sz\'\i n\H u szakasz. Bizony\'\i tand\'o, hogy $f(n)=6n-4$. \item Legyen $P$ v\'eges, legal\'abb k\'etelem\H u, \"osszef\"ugg\H o r\'eszben rendezett halmaz, \'es $p: P^3 \to P$ egy h\'aromv\'altoz\'os monoton f\"uggv\'eny, melyre a $p(x,x,y) = y$ azonoss\'ag teljes\"ul. Mutassuk meg, hogy van olyan nem\"ures val\'odi $I \subset P$, hogy tetsz\H oleges $x\in P, y \in I$ eset\'en $p(x,y,y) \in I$. [$P$ \"osszef\"ugg\H o, ha az \"osszehasonl\'ithat\'o elemp\'arokat \'elnek tekintve \"osz-szef\"ugg\H o gr\'afot kapunk. A $p$ monoton, ha $x_1 \leq y_1, x_2 \leq y_2, x_3 \leq y_3$ eset\'en $p(x_1,x_2,x_3) \leq p(y_1,y_2,y_3)$.] \item Legyen $F_q$ egy nem 2 karakterisztik\'aj\'u $q$ elem\H u v\'eges test, \'es legyen $V = F_q \times F_q$ az $F_q$ feletti 2-dimenzi\'os vektort\'er. Legyen $L \subset V$ olyan r\'eszhalmaz, ami minden ir\'anyban tartalmaz egyenest. ($L$-beli egyenesen olyan egyenest \'ert\"unk, melynek minden pontja $L$-ben van.) Egy $V$-beli pont rendje az a sz\'am, ah\'any $L$-beli egyenes illeszkedik a pontra. Bizony\'itsuk be, hogy $L$ legal\'abb $q$ olyan egyenest tartalmaz, amelynek van harmadrend\H u pontja. \item Legyen $G(x) = \max \left|A \right|$, ahol $A$ v\'egigfut az olyan eg\'esz sz\'amokb\'ol \'all\'o $A\subset [1,x]$ halmazokon, amelyekben nincs h\'aromtag\'u m\'ertani sorozat, azaz nincs olyan $x,y,z\in A$, hogy $x