BME matekverseny 2020

1. feladat

Bizonyítsuk be, hogy $\frac{2}{2^{2n}}\sum_{k=0}^n \left(\begin{matrix}2n \\ 2k \end{matrix}\right)13^k$ egy egész szám melynek hármas maradéka $1$ minden $n=1,2,\ldots$ esetén! (7 pont)

2. feladat

Legyen $p:\mathbb R^n\to \mathbb R$ egy többváltozós valós polinom továbbá $h(x_1,\ldots,x_n)=$ $x^2_1+\ldots +x^2_n-1$. Bizonyítsuk: ha $h$ minden nullhelye (azaz minden olyan ${\mathbf x}\in \mathbb R^n$ pont, ahol $h({\mathbf x})=0$) egyben $p$-nek is nullhelye, akkor $p$ előáll olyan $p= qh$ szorzatként, ahol $q$ is polinom! (7 pont)

3. feladat

A fehér színű valós síkon feketével megjelöljük az egész koordinátájú pontokat. Egy $P$ pontból egy $Q$ pont akkor nem látható, ha azt egy fekete pont eltakarja; azaz, ha a $\overline{PQ}$ nyílt szakasz tartalmaz fekete pontot. Döntsük el a következő kérdésekre a választ!

• Van-e olyan két fekete pontot összekötő egyenes, melynek egyetlen fekete pontjából sem látható az origó?


• Van-e tetszőleges $k>0$ mérethez olyan $k\times k$-s négyzet, melynek egyetlen fekete pontjából sem látható az origó?

(Egy kérdés megválaszolása 7, mindkét kérdés megválaszolása 11 pontot ér.)

4. feladat

Legyenek $f_1,\ldots,f_{2n-1}:[a,b] \to \mathbb R$ olyan folytonos konkáv függvények, melyek értéke a végpontokban nulla. A függvények sorszámozása legyen úgy, hogy max$(f_1) \leq \ldots\leq$ max$(f_{2n-1})$. Mutassuk meg, hogy a $$ \sum_{k=1}^n {\rm max}(f_k) \leq {\rm max}\left(\sum_{k=1}^{2n-1}f_k \right) $$ egyenlőtlenség biztosan teljesül! (Egy csak az $n=2$ esetre vonatkozó bizonyítás 7 pontot, az $n\geq 2$ tetszőleges esetre vonatkozó 2-vel többet, azaz 9 pontot ér.)

5. feladat

A síkon fölveszünk néhány szakaszt úgy, hogy azok mindegyikének végpontja két, előre adott párhuzamos egyenesen legyen (az egyik az egyiken, a másik a másikon). Tekintsük azt a $G$ gráfot, melynek pontjai a fölvett szakaszok, élei pedig azok a szakaszpárok, melyek "keresztezik egymást" (azaz melyek végpontjai nem esnek egybe, de van közös pontjuk). Bizonyítsuk be, hogy ha $G$-ben nincs háromszög, akkor $G$ egy páros gráf, és általában ha $G$-ben nincs teljes $k+1$-es, akkor $G$ legföljebb $k$ színnel biztosan színezhető. (Az általános eset bizonyítása 11 pontot, csak külön a speciális eset bizonyítása 7 pontot ér.)

6. feladat

Két ország közötti vita egyeztetésére mindkét fél $n>2$ diplomatát küldött. Protokoll szabályozza, hogy melyik diplomatának pontosan hány diplomatával kell kezet fognia a másik országból. Ez a szám mindkét küldöttség legalacsonyabb tagjának számára 1, a magasságban a küldöttség következő tagjának 2 és így tovább; egyedül a küldöttségek legmagasabb tagjai esetén van egy kis eltérés, mert nekik $n$ helyett $n-1$ kézfogást kell letudni. Adjunk explicit képletet a protokoll szabályainak lehetséges teljesítési módjának számára! (9 pont szerezhető, ha a lehetséges kombinációk $c_n$ számára vonatkozó képlet "teljesen explicit"; például könnyedén le lehet olvasni belőle $\lim_n \sqrt[n]{c_n}$ értékét. Kevésbé explicit - pl.: egy $n$ tagú összeget tartalmazó - kifejezés arányosan kevesebbet ér.)

7. feladat

Legyen $K$ egy nulla karakterisztikájú test és $F$ annak egy $d\lt \infty$ fokú bővítése. Tekintsük $F$-et mint vektorteret $K$ fölött, és legyen $U, V \subset F$ ebben az értelemben két $(d-1)$-dimenziós altér. Mutassuk meg: létezik olyan $r\in F$ elem, melyre $r U=V$. (10 pont)

8. feladat

Legyen $K$ egy konvex síkidom (azaz egy konvex, kompakt, nem üres belsejű halmaza $\mathbb R^2$-nek). Mutassuk meg: létezik olyan $\hat{T}$ háromszög, hogy $T\subset K\subset \hat{T}$ ahol $T$ az a kisebb háromszög, melynek csúcsai $\hat{T}$ oldalainak felezőpontjai. Találjunk az így bebizonyított tételünkhöz egy értelmes, tetszőleges $d\geq 2$ dimenzióra vonatkozó általánosítást is (melyben a háromszöget egy megfelelő sokdmineziós politópra cseréljük) és ellenőrizzük, hogy az állítás így is érvényben marad! (10 pont a $d=2$ dimenziós esetért és +1 pont az általánosításért.)

9. feladat

Legyen az $A_1,\ldots A_m$ valós, szimmetrikus $n\times n$-es mátrixok olyan gyűjteménye, melyekre $\sum_{k=1}^m A_k^2=I$. Következik-e a $\sum_{k=1}^m A_k X A_k=X$ egyenlőségből, hogy az $X$ (valós, $n\times n$-es) mátrix mindegyik $A_k$-val kommutál? (Teljes válasz 11 pont; de ha a kérdést legalább abban a speciális esetben eldöntjük, amikor $X$ egy ortogonális projekció, az már 7 pontot ér.)

10. feladat

Adjunk olyan alsó, $n$-től függő korlátot $m$-re, mely mellett az $n$ ismeretlenes, $m$ egyenletből álló $$ \sum_{k=1}^n x_k^{r_j} = s_j \;\;\;(j=1,\ldots,m) $$ egyenletrendszernek tetszőleges $s_1,\ldots,s_m \gt 0$ valamint $r_1\gt\ldots\gt r_m\gt 0$ valós paraméterek mellett legföljebb egyetlen $x_1\geq\ldots\geq x_n\gt 0$ megoldása lehet! (A $2n$ mint korlát bizonyítása 10 pont, bármi ami ennél nem csak egy konstanssal jobb, 13 pontot ér.)