Kezdőlap


Feladat:	A.679	Korcsoport: 18-	Nehézségi fok: nehéz
Kitűző(k):	Gerhard Woeginger
Füzet:	2016/október, 415. oldal		PDF \| MathML
Témakör(ök):	Nehéz feladat, Számhalmazok, Számsorozatok, Különleges függvények

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen $n = 2^{128}$ , $M = {1,2,3,4}$ , és jelölje $M^{n}$ az $M$ elemeiből készíthető, $n$ hosszú sorozatok halmazát. Döntsük el, léteznek-e olyan $f_{1}, ..., f_{n}$ és $g_{1}, ..., g_{n} : M^{n} \to M^{n}$ függvények, amelyekre tetszőleges

\begin{matrix} (x_{1}, ..., x_{n}), (y_{1}, ..., y_{n}) \in M^{n} \end{matrix}

sorozatok esetén a következő állítások közül legalább az egyik teljesül:

$•$	$f_{i} (y_{1}, ..., y_{n}) = x_{i}$ valamelyik $1 \leq i \leq n$ indexre;

$•$	$g_{j} (x_{1}, ..., x_{n}) = y_{j}$ valamelyik $1 \leq j \leq n$ indexre.