Iraniano

[edriv]

Sia s una funzione da $ ~ \{0,1\}^{201} $ a $ ~ \{0,1\} $.

Definiamo $ ~ f:\{0,1\}^{\mathbb{Z}} \rightarrow \{0,1\}^{\mathbb{Z}} $ in questo modo.
Se $ ~ \ldots a_{-1}a_0a_1 \ldots $ è una stringa infinita di 0 e 1, la sua immagine è $ ~ \ldots b_{-1}b_0b_1 \ldots $, dove $ ~ b_i = s(a_{i-100}\ldots a_{i-1}a_ia_{i+1} \ldots a_{i+100}) $.

Dimostrare che, se f è iniettiva, allora è biunivoca.

[edriv]

Dai su che è un bel problema

Qualche hint:
prima di dimostrare che f è suriettiva (ovvero raggiunge ogni stringa infinita), dimostrate che raggiunge ogni stringa finita.
Ovvero, fissata una stringa s di n caratteri, l'immagine contiene una stringa infinita che contiene s come sottostringa.
In effetti, se questo fosse falso, l'immagine non conterrebbe quasi nessun elemento, mentre potete dimostrare che li contiene quasi tutti!

Poi cercate in qualche modo furbo di costruire una qualsiasi stringa infinita a partire da quelle finite...

[elendil]

Perdona la mia ignoranza: mi diresti per favore che significa $ ~ \{0,1\}^{201} $?
Grazie in anticipo

[edriv]

Ho usato la notazione secondo cui, se A e B sono due insiemi:
$ A^B $ è l'insieme di tutte le funzioni da B ad A.

Ad esempio, $ \mathbb{R}^3 $ sarebbe l'insieme delle funzioni da 3 ad R, dove 3 è un generico insieme di tre elementi. Cos'è una funzione da {a,b,c} ad R? Per costruirne una devo associare un reale ad a, un reale a b e un reale a c. In pratica, è una terna ordinata di reali. Quindi $ \mathbb{R}^3 $ sarebbe l'insieme di terne ordinate di reali.

Altro esempio: quanti elementi ha $ A^B $, se A ha a elementi e B ha b elementi?
Per costruire una funzione da B ad A devo:
prendere il primo elemento di B ed associargli un elemento di A (questo lo posso fare in a modi)
prendere il secondo elemento di B ed associargli un elemento di A (questo lo posso fare in a modi)
...
prendere il b-esimo elemento di B ed associargli un elemento di A (questo lo posso fare in a modi)
In totale, a*a*a*...*a (b volte) possibili funzioni, ovvero a^b.
$ ~ |A^B| = |A|^{|B|} $.

Quindi $ \{0,1\}^{201} $ sono le possibili successioni di 201 uni e zeri.