A 2002. évi Schweitzer Miklós Emlékverseny feladatai
2002. november 8-18.

1.

Tetszoleges $\alpha$ rendszámra jelöljük $H(\alpha )$-val azon $f:\alpha \to \{ -1,\, 0,\, 1\}$ függvények halmazát, amelyek csak véges sok helyen vesznek fel 0-tól különbözo értéket. Rendezzük $H(\alpha )$-t az utolsó eltérés szerint, azaz $f,g\in H(\alpha )$ esetén legyen $f\prec g$ akkor, ha $f(\beta )<g(\beta )$ teljesül a legnagyobb $\beta <\alpha$ rendszámra, amelyre $f(\beta )\ne g(\beta ).$ Bizonyítsuk be, hogy a $(H(\alpha ), \prec )$ rendezett halmaz rendtípusa szétszórt (azaz nem tartalmaz a racionális számok szokásosan rendezett halmazával izomorf részhalmazt), továbbá minden szétszórt rendtípus beágyazható valamelyik $(H(\alpha ), \prec )$-ba.

2.

Legyen $G$ egyszeru, $k$-élösszefüggo, $n$ csúcsú gráf, $u$ és $v$ pedig legyenek $G$ különbözo csúcsai. Bizonyítsuk be, hogy létezik $G$-ben $u$ és $v$ között $k$ élidegen út, melyek bármelyike legfeljebb $${\frac{20n}{k}}$$ élt tartalmaz.

3.

Az $\bold{A}=\{$igen$,$ nem$\}$ halmazon értelmezett $f:\bold{A}^n \to \bold{A}$ függvényt döntési függvénynek mondjuk, ha

(a)

mindegyik argumentumát megváltoztatva a függvényérték is megváltozik; valamint

(b)

tetszolegesen választott argumentuma helyébe a függvényértéket helyettesítve a függvényérték nem változik meg.

Egy $h:\bold{A}^n\to\bold{A}$ függvényt hatalmi függvénynek nevezünk, ha van olyan $i$ index, hogy a függvény értéke mindig az $i$-edik argumentummal egyezik meg.

Azt az $m:\bold{A}^3\to\bold{A}$ függvényt, amelynek értéke mindig az, ami az argumentumok között legalább kétszer fellép, nevezzük demokratikus függvénynek.

Mutassuk meg, hogy minden döntési függvény eloállítható hatalmi és demokratikus függvényekbol összetett függvényként.

4.

Adott $n$ természetes számhoz tekintsük azon $A\subseteq \mathbb Z_n$ halmazokat, amelyekre az $xy=uv$ egyenletnek nincs más megoldása az $x,y,u,v\in A$ maradékosztályokból, mint az $x=u,\ y=v$ és az $x=v,\ y=u$ triviális megoldások. Legyen $g(n)$ az ilyen $A$ halmazok elemszámának maximuma. Bizonyítsuk be, hogy

$$\limsup_{n\to\infty}\frac{g(n)}{\sqrt{n}}=1\ .$$

5.

Jelöljük a $H\subseteq [0,1]$ halmaz Lebesgue-féle külso mértékét $\lambda (H)$-val. Az
$A\subseteq [0,1]\times [0,1]$ halmaz vízszintes és függoleges szekcióit $A^y$-nal és $A_x$-szel jelöljük, tehát $A^y =\{ x\in [0,1]: (x,y)\in A\}$ és $A_x =\{ y\in [0,1]: (x,y)\in A\}$ minden $x,\, y\in [0,1]$-re.

(a)

Van-e a $[0,1]\times [0,1]$ négyzetnek olyan $A\cup B$ felbontása, amelyre $A^y$ véges sok, $1/2$-nél kisebb összhosszúságú szakasz egyesítése, és $\lambda (B_x )\le 1/2$ minden $x,\, y\in [0,1]$-re?

(b)

Van-e a $[0,1]\times [0,1]$ négyzetnek olyan $A\cup B$ felbontása, amelyre $A^y$ véges sok, legfeljebb $1/2$ összhosszúságú szakasz egyesítése, és $\lambda (B_x ) < 1/2$ minden $x,\, y\in [0,1]$-re?

6.

Legyen $K\subseteq \mathbbR$ kompakt. Igazoljuk, hogy az alábbi két állítás ekvivalens:

(a)

$K$ minden $x$ pontjához található olyan $F_x\subseteq \mathbb R$ nem megszámlálható halmaz, hogy

dist$$(F_x,F_y)\ge\vert x-y\vert$$

teljesül minden $x,y\in K$ esetén;

(b)

$K$ nulla mértéku.

7.

Legyen a komplex értéku $F(z)$ függvény reguláris a komplex sík $\{ 0<\vert z\vert<R\}$ kipontozott körlapján. Szintvonalon értsük a ${\rm Re} \, F(z)$ függvény valamely szinthalmazának komponensét, tehát olyan maximális összefüggo halmazt, amelyen ${\rm Re} \, F(z)$ állandó. Jelöljük $A(r)$-rel azon szintvonalak unióját, melyek teljes egészükben a $\{ 0<\vert z\vert<r\}$ kipontozott körlapon helyezkednek el. Mutassuk meg, hogy ha $A(r)$ komponenseinek száma $r$-tol független korlát alatt marad, akkor $F(z)$-nek 0-ban legfeljebb pólus szingularitása lehet.

8.

Bizonyítsuk be, hogy létezik olyan $c$ abszolút konstans, hogy minden $n$-pontú, általános helyzetu, síkbeli $H$ ponthalmaz elemeit kiszínezhetjük $c\cdot\log n$ színnel úgy, hogy a sík bármely körlemeze, mely $H$-nak legalább egy pontját tartalmazza, $H$ valamelyik színosztályából pontosan egy pontot fed.

9.

Legyen $M$ összefüggo, kompakt, $C^\infty$-differenciálható sokaság, és jelölje $C^\infty(M)$ az $M$-en értelmezett sima valós függvények vektorterét. Legyen $V\le C^\infty(M)$ olyan altér, amely invariáns az $M$ sokaság $C^\infty$-diffeomorfizmusaira nézve, azaz $f\circ h\in V$, valahányszor $f\in V$ és $h:M\to M$ tetszoleges $C^\infty$-diffeomorfizmus. Bizonyítsuk be, hogy ha $V$ különbözik a $\{0\}$ és $C^\infty(M)$ alterektol, akkor pontosan a konstans függvényekbol áll.

10.

Legyenek $X_1,X_2,\ldots$ független, azonos eloszlású valószínuségi változók, melyek közös eloszlása végtelen sok különbözo értékre koncentrált diszkrét eloszlás. Legyen $a_n$ annak a valószínusége, hogy $X_1,\ldots,X_{n+1}$ mind különbözo értéket vesz fel, feltéve, hogy $X_1,\ldots,X_n$ különbözo értékeket vettek fel ($n\ge 1$). Mutassuk meg, hogy

(a)

$n\to\infty$ esetén $a_n$ szigorúan monoton csökkenve tart 0-hoz; valamint

(b)

a pozitív egész számok tetszoleges $1\le f(1)<f(2)<\ldots$ részsorozatára $X_1,X_2,\ldots$ közös eloszlása megválasztható úgy, hogy a

$$\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1$$

összefüggés teljesüljön.

A feladatok beadásának határideje: 2002. november 18, 12h (CET). Ha a versenyzo olyan ismeretre támaszkodik, ami nem szerepel az egyetemi törzsanyagban, akkor kérjük, hogy pontosan hivatkozzon a forrásra. További információ a versenykiírásban, ill. a http://www.cs.elte.hu/~schw02 weboldalon található.

2002. november 19-én, kedden délután 4 órai kezdettel a Rényi Alfréd Matematikai Kutatóintézet nagytermében megbeszéljük a verseny feladatait. Az intézet címe: 1053 Budapest, Reáltanoda u. 13-15. Minden érdeklodot szívesen látunk.

Sikeres munkát kíván

a versenybizottság