 |
Az A. 679. feladat (2016. október) |
A. 679. Legyen \(\displaystyle n = 2^{128}\), \(\displaystyle M = \{1, 2, 3, 4\}\), és jelölje \(\displaystyle M^n\) az \(\displaystyle M\) elemeiből készíthető, \(\displaystyle n\) hosszú sorozatok halmazát. Döntsük el, léteznek-e olyan \(\displaystyle f_1,\ldots,f_n\) és \(\displaystyle g_1,\ldots,g_n\colon M^n\to M\) függvények, amelyekre tetszőleges
\(\displaystyle (x_1,\ldots,x_n),(y_1,\ldots,y_n)\in M^n \)
sorozatok esetén a következő állítások közül legalább az egyik teljesül:
\(\displaystyle \bullet\) \(\displaystyle f_i(y_1,\ldots,y_n) = x_i\) valamelyik \(\displaystyle 1\le i\le n\) indexre;
\(\displaystyle \bullet\) \(\displaystyle g_j(x_1,\ldots,x_n) = y_j\) valamelyik \(\displaystyle 1\le j\le n\) indexre.
Javasolta: Gerhard Woeginger (Eindhoven)
(5 pont)
A beküldési határidő 2016. november 10-én LEJÁRT.
Megoldás. Megmutatjuk, hogy léteznek ilyen függvények.
Összesen \(\displaystyle n=2^{128}=4^{64}\)-féle \(\displaystyle M^3\to M\) függvény létezik; legyenek ezek valamilyen sorrendben \(\displaystyle a_1,\ldots,a_n\). Egy \(\displaystyle (y_1,y_2,y_3)\in M^3\) hármast nevezzünk rossznak az \(\displaystyle (x_1,\ldots,x_n)\in M^n\) sorozathoz, ha \(\displaystyle a_i(y_1,y_2,y_3)\ne x_i\) minden \(\displaystyle i=1,\ldots,n\)-re.
Azt állítjuk, hogy barmely \(\displaystyle (x_1,\ldots,x_n)\in M^n\) sorozathoz legfeljebb három rossz hármas létezhet. Tegyük fel indirekte, hogy az \(\displaystyle (x_1,\ldots,x_n)\in M^n\) sorozathoz négy különböző rossz hármas is létezik: \(\displaystyle (y_1,y_2,y_3)\), \(\displaystyle (y_1',y_2',y_3')\), \(\displaystyle (y_1'',y_2'',y_3'')\) és \(\displaystyle (y_1''',y_2''',y_3''')\). Vegyük egy olyan \(\displaystyle a_k\) függvényt, amelyre \(\displaystyle a_k(y_1,y_2,y_3)=1\), \(\displaystyle a_k(y_1',y_2',y_3')=2\), \(\displaystyle a_k(y_1'',y_2'',y_3'')=3\), és \(\displaystyle a_k (y_1''',y_2''',y_3''')=4\). Mivel \(\displaystyle x_k \in \{1,2,3,4\}\), ez ellentmondás; nem létezhet négy rossz hármas.
Most minden \(\displaystyle (x_1,\ldots,x_n)\in M^n\) sorozathoz válasszunk három különböző hármast, a \(\displaystyle (y_1',y_2',y_3')\), \(\displaystyle (y_1'',y_2'',y_3'')\), \(\displaystyle (y_1''',y_2''',y_3''')\) hármasokat úgy, hogy ezek között szerepeljen minden, az \(\displaystyle (x_1,\ldots,x_n)\) sorozathoz rossz hármas. Legyen \(\displaystyle b_1 (x_1,\ldots,x_n)=y_1'\), \(\displaystyle b_2(x_1,\ldots,x_n)=y_2''\) és \(\displaystyle b_3(x_1,\ldots,x_n)=y_3'''\). Ezek utánb defináljuk az \(\displaystyle f_i\) és \(\displaystyle g_j\) fügvényeket:
\(\displaystyle \bullet\) Minden \(\displaystyle 1 \leq i \leq n\)-re és \(\displaystyle (y_1,\ldots,y_n) \in M^n\)-re legyen \(\displaystyle f_i(y_1,\ldots,y_n)=a_i(y_1,y_2,y_3)\).
\(\displaystyle \bullet\) Minden \(\displaystyle 1 \leq j \leq 3\)-ra és \(\displaystyle (x_1,\ldots,x_n) \in M^n\)-re legyen \(\displaystyle g_j(x_1,\ldots,x_n)=b_j(x_1,\ldots,x_n)\).
A \(\displaystyle g_j\) függvényeket \(\displaystyle 4 \leq j \leq n\) esetén tetszőlegesen választhatjuk.
Most tekintsünk két tetszőleges \(\displaystyle (x_1,\ldots,x_n),(y_1,\ldots,y_n)\in M^n\) sorozatot. Ha \(\displaystyle f_i(y_1,\ldots,y_n)\ne x_i\) teljesül minden \(\displaystyle 1 \leq i \leq n\)-re, akkor \(\displaystyle (y_1,y_2,y_3)\) egy rossz hármas az \(\displaystyle (x_1,\ldots,x_n)\) sorozathoz. Ekkor viszont a \(\displaystyle b_j\) függvények definíciója miatt \(\displaystyle g_j(x_1,\ldots,x_n)=b_j(x_1,\ldots,x_n)=y_j\) az \(\displaystyle j=1,2,3\) indexek valamelyikére.
Statisztika:
1 dolgozat érkezett. 0 pontot kapott: 1 versenyző.
A KöMaL 2016. októberi matematika feladatai