Problem A. 679. (October 2016)
A. 679. Let \(\displaystyle n = 2^{128}\), \(\displaystyle M = \{1, 2, 3, 4\}\), and let \(\displaystyle M^n\) denote the set of sequences of length \(\displaystyle n\) and consisting of elements of \(\displaystyle M\). Decide whether there exist functions \(\displaystyle f_1,\ldots,f_n\) and \(\displaystyle g_1,\ldots,g_n\colon M^n\to M\) such that for every pair of sequences
\(\displaystyle (x_1,\ldots,x_n),(y_1,\ldots,y_n)\in M^n, \)
at least one of the following statements holds:
\(\displaystyle \bullet\) \(\displaystyle f_i(y_1,\ldots,y_n) = x_i\) for some index \(\displaystyle i\) with \(\displaystyle 1\le i\le n\);
\(\displaystyle \bullet\) \(\displaystyle g_j(x_1,\ldots,x_n) = y_j\) for some index \(\displaystyle j\) with \(\displaystyle 1\le j\le n\).
Proposed by: Gerhard Woeginger, Eindhoven
(5 pont)
Deadline expired on November 10, 2016.
Solution. We show that such functions do exist. Let \(\displaystyle a_1,\ldots,a_n\) be an enumeration of all \(\displaystyle n=2^{128}=4^{64}\) functions \(\displaystyle M^3\to M\). A triple \(\displaystyle (y_1,y_2,y_3)\in M^3\) is bad for an \(\displaystyle n\)-tuple \(\displaystyle (x_1,\ldots,x_n)\in M^n\), if \(\displaystyle a_i(y_1,y_2,y_3)\ne x_i\) for all \(\displaystyle i=1,\ldots,n\).
We claim that every \(\displaystyle n\)-tuple \(\displaystyle (x_1,\ldots,x_n)\) in \(\displaystyle M^n\) has at most three bad triples: Suppose otherwise, and let \(\displaystyle (y_1,y_2,y_3)\), \(\displaystyle (y_1',y_2',y_3')\), \(\displaystyle (y_1'',y_2'',y_3'')\), \(\displaystyle (y_1''',y_2''',y_3''')\) be four bad triples. Consider some function \(\displaystyle a_k\) that assigns \(\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\), and \(\displaystyle a_k (y_1''',y_2''',y_3''')=4\). Since \(\displaystyle x_k \in \{1,2,3,4\}\), this yields a contradiction and proves the claim.
Next we pick for every \(\displaystyle n\)-tuple \(\displaystyle (x_1,\ldots,x_n)\) in \(\displaystyle M^n\) three distinct triples \(\displaystyle (y_1',y_2',y_3')\), \(\displaystyle (y_1'',y_2'',y_3'')\), \(\displaystyle (y_1''',y_2''',y_3''')\): These are the \(\displaystyle t \leq 3\) bad triples for \(\displaystyle (x_1,\ldots,x_n)\), together with \(\displaystyle 3 - t\) arbitrarily chosen other triples. We define \(\displaystyle b_1 (x_1,\ldots,x_n)=y_1'\), and \(\displaystyle b_2 (x_1,\ldots,x_n)=y_2''\), and \(\displaystyle b_3 (x_1,\ldots,x_n)=y_3'''\). Finally we specify the functions \(\displaystyle f_i\) and \(\displaystyle g_j\) :
\(\displaystyle \bullet\) For \(\displaystyle 1 \leq i \leq n\) and \(\displaystyle (y_1,\ldots,y_n) \in M^n\), set \(\displaystyle f_i(y_1,\ldots,y_n)=a_i(y_1,y_2,y_3)\).
\(\displaystyle \bullet\) For \(\displaystyle 1 \leq j \leq 3\) and \(\displaystyle (x_1,\ldots,x_n) \in M^n\), set \(\displaystyle g_j(x_1,\ldots,x_n)=b_j(x_1,\ldots,x_n)\).
The remaining functions \(\displaystyle g_j\) with \(\displaystyle 4 \leq j \leq n\) are irrelevant, and chosen arbitrarily. Now consider \(\displaystyle 2n\) arbitrary elements \(\displaystyle x_1,\ldots,x_n,y_1,\ldots,y_n\) in \(\displaystyle M\). If \(\displaystyle f_i(y_1,\ldots,y_n)\ne x_i\) holds for \(\displaystyle 1 \leq i \leq n\), then our construction yields that \(\displaystyle (y_1,y_2,y_3)\) is a bad triple for \(\displaystyle (x_1,\ldots,x_n)\). This implies \(\displaystyle g_j(x_1,\ldots,x_n)=y_j\) for \(\displaystyle j=1\) or for \(\displaystyle j=2\) or for \(\displaystyle j=3\), and hence we are done.
Statistics:
1 student sent a solution. 0 point: 1 student.
Problems in Mathematics of KöMaL, October 2016