Matematicamente.it

Se il messaggio fosse lungo $16$ bit e ne mancassero $n$, potrei recuperarli sempre con $4$ messaggi, nel modo seguente: prima mando il messaggio con $8$ zeri seguiti da $8$ uni. In questo modo scopro quanti bit mancano in ogni metà del messaggio. Con questa informazione, mando poi il messaggio con $4$ zeri seguiti da $4$ uni e poi di nuovo $4$ zeri seguiti da $4$ uni. Siccome so quanti bit mancano nelle due metà, ricavo quanti bit mancano in ogni quarto. Adesso mando il messaggio $0011001100110011$, così scopro quanti bit mancano in ogni ottavo di messaggio. Infine mando il messaggio $0101010101010101$ e scopro esattamente quali sono i bit mancanti.

Come faccio con $16$ bit mancanti tra $512$? Mando il messaggio fatto così: $16$ zeri seguiti da $16$ uni ripetuti $16$ volte. Così scopro in ogni blocco da $16$ quanti bit mancano. Adesso mi riporto al caso precedente: mando un messaggio che ha tutti $0$ tranne nei blocchi in cui so esserci delle mancanze, lì ci piazzo $8$ zeri seguiti da $8$ uni. Poi proseguo come sopra. In totale sono $5$ messaggi.

Con 4 sequenze di test, un gruppo compatto di 16 bit che spariscono non e' rilevabile.
Le 4 sequenze trasmesse codificano i numeri da 0 a 15 a ripetizione (*), cioe':
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .......

E' ovvio che se sparisce un blocco da 16, la sequenza appare semplicemente troncata di 16 bit, quindi non si riesce a capire in che posizione sono spariti.
Quindi il minimo sono 5 sequenze di test che codificano i numeri da 0 a 31.

(*)
Se le sequenze sono scritte in verticale una di fianco all'altra, compaiono i numeri binari leggibili direttamente

Codice:

0000  0
0001  1
0010  2
0011  3
0100  4
0101  5
0110  6
0111  7
1000  8
etc...


Non mi è chiaro il tuo ragionamento, non capisco perché tu dia per scontato che ci siano ripetizioni o regolarità in qualsiasi sequenza che venga inviata (ce ne sono $2^512$)

Infatti io parlavo delle K sequenze di test.
Nel thread, hydro ha messo la risposta corretta.
Tu gli hai risposto "benissimo", e poi 'come si dimostra che è il minimo possibile?'
Io stavo rispondendo a questa domanda, quindi sto ancora parlando delle sequenze di test.
Si dimostra che 5 e' il minimo perche' con 4 sequenze non rilevi un blocco di 16 bit mancante in alcune posizioni.
A maggior ragione 3, 2, o 1 sequenza non sono sufficienti. Ce ne vogliono 5.
Poi, per far capire meglio questo concetto, facevo vedere che le 4 sequenze (o le 5) si possono scrivere una vicino all'altra e in questo modo si possono leggere trasversalmente i numeri binari da 0 a 15, o da 0 a 31.
Con questa visualizzazione si capisce ancora meglio perche' 4 sequenze non bastano.

Quello che mi chiedo è come sia possibile dimostrare che 5 sequenze sono il minimo possibile, NON che quelle 5 sequenze specifiche trovate da hydro siano il minimo possibile

Non credo che ci sia una qualche formula da cui esce il numero minimo.

Pero' sembra che 5 non sia il minimo K per rilevare i 16 caratteri mancanti.

La sequenza periodica il cui periodo e' fatto da:
0102301024501023010246
e' lunga 22 e quindi rileva blocchi compatti mancanti lunghi fino a 21.
Per fare quella sequenza servono le cifre da 0 a 6, quindi si puo' codificare con 3 sequenze binarie, e quindi il K minimo scende a 3.

Bisogna considerare i test da fare per verificare se una sequenza e' valida, cioe' e' una sequenza che permette di scoprire uno o piu' caratteri che sono stati eliminati in una posizione qualsiasi.
L'ultima sequenza che ho proposto non va bene, e quindi si torna a quella semplice 0 1 2 3... 31 siccome la distanza minima tra due caratteri e' 32.