indovinello

indovinello

Supponiamo che la stringa originale $s$ abbia lunghezza $2^n$. Allora la stringa $t$ di lunghezza $n$ viene creata da $A$ così: $t_i$ è la somma (modulo due) delle cifre in $S_i$, dove $S_i$ è la sottostringa (non necessariamente segmento iniziale) di $s$ formata da $2^{n-1}$ elementi selezionati così: in ordine, $2^{n-i}$ elementi "presi" e $2^{n-i}$ elementi "lasciati via", alternandosi finché non finisce la stringa ($1 \leq i \leq n$).
Quindi ad esempio se $|s|=2^3$ allora $S_1 = \{s_1,s_2,s_3,s_4\}$, $S_2 = \{s_1,s_2,s_5,s_6\}$, $S_3 = \{s_1,s_3,s_5,s_7\}$.
La generalizzazione per lunghezze di forma arbitraria è immediata (basta riempire la stringa di zeri finché non si raggiunge il primo $m$ tale che $|s^\frown 0^m| = 2^n$ per qualche $n$). La dimostrazione che il metodo funziona è lasciata al lettore ;)

PS: lo so, la definizione degli $S_i$ fa schifo, ma non avevo voglia di mettermi a pensare a una definizione formale.