Il mese scorso, nella mailing list “Problem of the Week” di Stan Wagon, è apparso un problema che non sono riuscito a risolvere (shame on me). La vergogna è che quando ho visto la soluzione mi sono detto che avrei dovuto arrivarci, perché usava la stessa logica che avevo trovato in un altro problema. Visto che qui non si butta via nulla, vi propongo il problema, direttamente con la soluzione perché non è giusto far penare anche voi. Ecco il problema:

Alice ha un insieme di $n+1$ stringhe binarie di lunghezza $n \; ( \ge 2 )$. Bob sa che Alice ha queste stringhe, ma non sa nulla su come sono fatte. Il suo scopo è indicare una stringa, sempre di lunghezza $n$, che Alice non possiede, e per farlo può fare delle domande del tipo “qual è il bit $j$ della stringa $k$?”. Qual è il numero minimo di domande che Bob deve fare per essere certo di trovare la sua stringa?

Per i curiosi, il problema è stato proposto da Noga Alon, Oliver Boisquet, Kasper Green Larsen, Shay Moran, e Shlomo Moran nel numero di dicembre 2024 dell’American Mathematical Monthly. Se volete provare a risolvere il problema, non proseguite la lettura.

Il titolo del post dovrebbe farvi subito pensare al procedimento diagonale di Cantor: se Alice avesse solo $n$ stringhe non ci sarebbero infatti difficoltà. Bob farebbe le $n$ domande “qual è il bit $i$ della stringa $i$?”, e costruirebbe la sua stringa prendendo il bit opposto a quello che ha avuto come risposta. In questo modo sarebbe sicuro che il primo bit della sua stringa è diverso da quello della stringa 1 di Alice, il secondo bit è diverso da quello della stinga 2, e così via. Peccato che Alice abbia una stringa in più, e se Bob è sfortunato quella stringa è proprio quella che lui ha costruito. Anche testare tutti i bit di quella stringa serve a poco: se sono tutti uguali bisogna ricominciare da capo. Insomma la strada che sembrava promettente si è rivelata una specie di circolo vizioso. Come procedere, dunque? Ecco un secondo aiuto, quello che se mi fosse venuto in mente mi avrebbe permesso di arrivare alla soluzione: considerate un piccolo sottoinsieme delle stringhe di Alice e trovate un modo per sceglierne una specifica da cui partire per la diagonalizzazione. Avete capito come?

Il trucco per riuscire a trovare una stringa “nuova” con $n+2$ domande consiste nello scegliere opportunamente il suo primo bit. Le prime tre domande di Bob saranno dunque “qual è il primo bit della stringa 1, quello della stringa 2 e quello della stringa 3”. Di questi tre bit, almeno due devono essere uguali tra loro: senza perdita di generalità possiamo supporre che ci siano almeno due bit 0. (Se ci fossero due bit 1, il ragionamento è ovviamente simmetrico). Bob allora costruirà la sua stringa partendo con 1. La sua quarta domanda sarà “qual è il secondo bit della stringa $k$?”, scegliendo quella eventuale il cui primo bit è 1 (se tutte e tre le stringhe cominciavano con 0 salterà la domanda), e metterà l’altro valore binario come secondo bit. Da qui continua con il metodo diagonale, chiedendo il bit $k$ della stringa $k+1$ e scrivendo l’altro valore. In tutto farà quindi $n+2$ domande. Come dimostrare che non si può fare di meglio? Beh, innanzitutto avendo Alice $n+1$ stringhe Bob dovrà fare almeno $n+1$ domande. Ma per il principio dei cassetti dovrà chiedere almeno due volte il bit nella stessa posizione di due stringhe distinte. Se Alice dice che questi bit sono distinti allora Bob non può sapere che bit mettere in quella posizione, perché rischia di trovare la stringa di Alice con quel bit lì.

Essendo i matematici gente che ama le generalizzazioni, un problema correlato è quello “chiedere tutto subito” in cui Bob deve fare tutte le domande in anticipo, e quindi non può sfruttare le risposte di Alice per scegliere quale domanda successiva fare (la quarta domanda nella soluzione che ho riportato qui sopra). In questo caso non ci sarei arrivato nemmeno con l’aiuto di cui sopra: però in effetti la soluzione è molto simile, e permette di trovare una stringa “nuova” con al più $n+4$ domande. Eppure la strategia è molto simile. Riuscite a trovarla?

In questo caso Bob comincia a chiedere i primi due bit delle stringhe 1, 2, 3: in tutto sei domande, poi continua come prima chiedendo il bit 3 della stringa 4, il bit 4 della stringa 5 e così via. Una volta avute tutte le risposte da Alice, Bob comincia a fare i suoi conti: ci sono quattro possibilità per la coppia di bit (00, 01, 10, 11), Alice può averne usate al massimo tre e Bob sceglie pertanto la quarta, usando per gli altri bit l’opposto di quanto indicato da Alice. È anche possibile dimostare che $n+4$ domande è il valore minimo, ma non ho abbastanza spazio in questo post :-) e quindi vi rimando a questo sito con la dimostrazione completa.

Morale di tutto qusto post? Il principio dei cassetti ha giocato un ruolo fondamentale nel trovare una soluzione, sia nel caso semplice che in quello con le domande fatte a priori: la cosa è almeno per me un po’ inaspettata.