Sovrastima sulle stringhe binarie abbastanza diverse

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Sovrastima sulle stringhe binarie abbastanza diverse

Messaggio da edriv » 31 ott 2006, 15:44

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)

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 03 nov 2006, 10:49

Metto in bianco una soluzione:
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.
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?

Rispondi