Problema binario

[batmangiallo]

Ciao, problema di probabilità che dubito sia difficile ma che non ho idea di come approcciare. Qualcuno mi dia una mano!

Considera le sequenze di 7 lettere scrivibili solo con le lettere A e/o B. Al massimo, quante sequenze si possono selezionare se si vuole che, comunque considerate due tra queste, esse differiscano per le lettere che compaiono in almeno 3 posizioni?

[fph]

C'è un problema di geometria che ti può tornare utile aver visto: dimostra che se metto 200 punti in un quadrato di lato 1 allora ce ne sono due a distanza al più 0.1 l'uno dall'altro.

Idea per risolverlo:

Testo nascosto:

Se non fosse possibile, allora potresti tracciare attorno ad ogni punto un cerchio di raggio 0.05, e questi cerchi devono essere disgiunti e tutti contenuti all'interno di un quadrato di lato 1.1. Ma allora avresti piazzato 200 cerchi di area totale $200\pi(0.05)^2 = 1.5708$ all'interno di un quadrato di lato $1.21$, che è impossibile.

Portandoti da casa questo problema che apparentemente non c'entra nulla, ti viene un'idea per partire?

Già che ci siamo, altro commento interessante su quel problema:

Testo nascosto:

Nota che il numero 200 è scelto in modo che si riescano a fare i conti in fretta, ma anche che un'altra idea più "debole" non funzioni: divido il quadrato in una griglia di 14^2=196 quadratini di lato 1/14; allora ci sono sicuramente due punti che cadono nello stesso quadratino, e quindi hanno distanza al più $\frac{\sqrt2}{14} = 0.101$ l'uno dall'altro. Acc, questo bound è troppo grosso di uno sputo...

[batmangiallo]

Penso che l'idea possa essere quella di creare un'associazione biunivoca tra i punti di una figura geometrica e le sequenze di A e B in modo da ricondurmi al problema che hai proposto, ma non saprei bene come fare a dir la verità; in qualche modo bisognerebbe far corrispondere le distanze tra i punti con la diversa lettera in una posizione

[fph]

L'associazione diretta con una figura geometrica purtroppo non c'è (a meno di andare in contesti più astratti), ma il concetto di "distanza" tra punti e quello che ci fai è proprio quello che interessa a te! Come riusi l'idea di passare da punti a cerchi?

[batmangiallo]

Non mi viene un'idea bella, ma ad esempio se immagino un quadrato di lato 7 e che se due punti distano 1 hanno una lettera diversa in una posizione, allora basta contare quanti cerchi di raggio 2 disgiunti posso inscrivere nel quadrato e moltiplicare per 2 in modo da contare anche le sequenze simmetriche. Manca ancora qualcosa mi sa però...