Sia A un sottoinsieme di tutte le stringhe binarie di n lettere (cioè con le lettere scelte nell'alfabeto {0;1}) tale che, comunque prese due stringhe in A e scritte una sotto l'altra, queste sono diverse in almeno 3 posizioni.
Dimostrare che $ \displaystyle |A| \le \frac{2^n}{n+1} $.
(problema dal libro del signor Engel)
Sovrastima sulle stringhe binarie abbastanza diverse
Metto in bianco una soluzione:
Mi sembra il modo più semplice di risolverlo. E invece quanto sono grandi al massimo, per ogni n, gli insiemi di stringhe binarie lunghe n che si differenziano in almeno 2 posizioni?Sia A un insieme che verifica la proprietà in questione. Per ogni 1<= j <=n sia Aj l'insieme delle stringhe ottenute prendendo le stringhe di A e invertendo il j-esimo carattere (cioè se era 0 diventa 1 e viceversa). Si verifica subito che A, A1, ..., An sono disgiunti e della stessa cardinalità di A. Dunque la cardinalità della loro unione è (n+1)|A| e questa è un sottoinsieme di tutte le stringhe di lunghezza n da cui la sovrastima.