Az A. 923. feladat (2026. január)

A. 923. Egy kiállítást, amelyen \(\displaystyle 1000\) festményt mutattak be, \(\displaystyle 2026\)-an látogattak meg. Bizonyítsuk be, hogy a látogatók közül néhányat el lehet küldeni két terembe úgy, hogy mindkét terembe küldünk legalább egy embert, és nincs olyan festmény, amely az egyik teremben tetszett valakinek, de a másikban senkinek sem, továbbá nincs olyan festmény, amelynek festőjét az egyik teremben személyesen ismeri valaki, de a másikban senki sem.

(7 pont)

A beküldési határidő 2026. február 10-én LEJÁRT.

Minden egyes látogatóhoz készítsünk egy \(\displaystyle \mathbf{v}_j\in\mathbb{R}^{2000}\) \(\displaystyle 0-1\) vektort, amit úgy kapunk, hogy az első \(\displaystyle 1000\) helyen \(\displaystyle 1\)-et írunk az \(\displaystyle i.\) helyre, ha az \(\displaystyle i.\) festmény tetszett az adott látogatónak, amúgy \(\displaystyle 0\)-t, a második \(\displaystyle 1000\) helyen pedig \(\displaystyle 1\)-et írunk az \(\displaystyle 1000+i.\) helyre, ha az \(\displaystyle i\) festmény festőjét ismeri az adott látogató, amúgy \(\displaystyle 0\)-t.

Mivel \(\displaystyle 2026\) vektorunk van \(\displaystyle \mathbb{R}^{2000}\)-ben, ezek nem lehetnek lineárisan függetlenek, azaz lehet találni \(\displaystyle \lambda_1,\lambda_2,...,\lambda_{2026}\) valós számokat, melyek nem mind nullák, és

\(\displaystyle \lambda_1\mathbf{v}_1+\lambda_2\mathbf{v}_2+...+\lambda_{2026}\mathbf{v}_{2026}=0. \)

Legyen \(\displaystyle I^+=\{i:\lambda_i>0\}\) és \(\displaystyle I^-=\{i:\lambda_i<0\}\), ezek egyike biztosan nem üres, és mivel nemnegatívak a vektorok koordinátái, ezért a másik sem lehet üres. Azt állítjuk, hogy ez a két halmaz jól osztja ketté a látogatókat. Valóban, ha az egyik teremben tetszett valakinek egy festmény, akkor a másikban is kell, hogy tetsszen valakinek, különben az adott festményhez tartozó koordináta az első \(\displaystyle 1000\) koordináta között a lineáris kombinációban nem lehetne \(\displaystyle 0\), és persze ugyanez teljesül a második ezer koordináta esetén is.

Statisztika:

Az A. 923. feladat értékelése még nem fejeződött be.

A KöMaL 2026. januári matematika feladatai