 Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL? 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