Skip to content

Instantly share code, notes, and snippets.

@korg91
Created January 12, 2017 16:10
Show Gist options
  • Save korg91/8abf82102a450b9ad51a7eb03e63789a to your computer and use it in GitHub Desktop.
Save korg91/8abf82102a450b9ad51a7eb03e63789a to your computer and use it in GitHub Desktop.
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment