I bit scomparsi

[axpgn]

Un agente segreto invia messaggi al centro di comando.
Ogni messaggio è una stringa di 512 caratteri, tutti zeri e uni.
Sfortunatamente il suo trasmettitore funziona male e si mangia $16$ caratteri ad ogni messaggio.
I $16$ caratteri mancanti si trovano sempre nelle stesse posizioni in ogni messaggio.
Come risultato il centro di comando riceve una sequenza di $496$ bit.
Nè l'agente nè il centro sanno dove si trovano i $16$ bit mangiati ad ogni messaggio e neppure possono sostituire il trasmettitore.
Comunque, precedentemente, si sono accordati per l'invio preliminare di $K$ messaggi di test.

Qual è il più piccolo $K$ possibile necessario per individuare le posizioni dei $16$ bit mancanti?


Cordialmente, Alex

[hydro]

Testo nascosto, fai click qui per vederlo

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.

[axpgn]

Perfetto!

Adesso però rimane aperta una questione: come si dimostra che è il minimo possibile?

[Quinzio]

Perfetto!

Adesso però rimane aperta una questione: come si dimostra che è il minimo possibile?

Testo nascosto, fai click qui per vederlo

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...


[axpgn]

Testo nascosto, fai click qui per vederlo

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$)

[Quinzio]

Testo nascosto, fai click qui per vederlo

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$)

Testo nascosto, fai click qui per vederlo

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.

[axpgn]

Probabilmente non mi sono fatto capire ...

Testo nascosto, fai click qui per vederlo

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

[Quinzio]

Probabilmente non mi sono fatto capire ...

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

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.

[axpgn]

Non ho capito ...

[Quinzio]

Non ho capito ...

Testo nascosto, fai click qui per vederlo

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.