Scuola di Babele

[axpgn]

Una scuola internazionale ha $250$ allievi, ognuno dei quali parla molte lingue diverse.
Per ogni coppia di allievi, poniamo $A$ e $B$, c'è una lingua che $A$ parla e $B$ non capisce e un'altra che $B$ parla e $A$ non capisce.

Qual è il numero minimo di lingue diverse parlate in quella scuola?


Cordialmente, Alex

[Mathita]

Con mezzi poco consoni, 10? Per come ho impostato io il problema, devo trovare il più piccolo intero positivo $n$ tale che $nCk\ge 250$ [strike]per ogni[/strike] per almeno un $k\in{1,...,n}$... Vergognosamente al pc.

[hydro1]

Supponiamo che gli studenti non parlino tutti lo stesso numero di lingue, e che la condizione sia verificata. Voglio dimostrare che posso insegnare agli studenti che sanno meno lingue delle lingue che qualcuno degli altri parla finchè tutti non parlano lo stesso numero di lingue, mantenendo verificata la condizione.

Sia $S$ l'insieme degli studenti che parlano $N$ lingue, con $N$ minore del numero di lingue parlato da ogni studente fuori da $S$. Adesso prendo una lingua $L$ che è parlata da qualcuno fuori da $S$, che sicuramente esiste, e la insegno a tutti gli studenti di $S$. Adesso succede che l'insieme $S$ si è rimpicciolito, ma la condizione di partenza è ancora soddisfatta. Infatti, prendiamo uno studente $s_1\in S$ che con $L$ ha imparato una lingua nuova, e confrontiamolo con uno studente $s_2\notin S$. Siccome le lingue parlate da $s_1$, prima di imparare $L$, non erano un sottoinsieme di quelle parlate da $s_2$, certamente non lo possono essere quando ci aggiungo $L$. Viceversa, per questioni di cardinalità le lingue parlate da $s_2$ non possono essere un sottoinsieme di quelle parlate da $s_1$, anche dopo che ha imparato $L$. Prendiamo invece $s_3\in S$ che già sapeva $L$. Adesso $s_1$ parla $N+1$ lingue, quindi queste non possono essere un sottoinsieme di quelle parlate da $s_3$. Se invece quelle parlate da $s_3$ fossero un sottoinsieme di quelle parlate da $s_1$ dopo che ha imparato $L$, togliendo $L$ ad entrambi otterrei che le lingue che parlava $s_1$ prima di imparare $L$ sono un sottoinsieme di quelle parlate da $s_3$, il che è assurdo. Ergo, la condizione è ancora verificata. Ma adesso posso rifare il giochino, e lo posso rifare finchè tutti gli studenti parlano lo stesso numero di lingue $k$.

Ora tutti gli studenti parlano $k$ lingue, e se $m$ è il numero totale di lingue parlate, devo solo capire quando \(\binom{m}{k}\ge 250\). Ma si sa che i coefficienti binomiali sono massimi al centro, quindi devo solo capire quando \(\binom{m}{m/2}\ge 250\), il che accade per $m\ge 10$.

[axpgn]

Il risultato è giusto ma ci sono alcune cose che non mi sono chiare ...

@Mathita
Che ragionamento hai fatto?

@hydro

"hydro":Siccome le lingue parlate da $ s_1 $, prima di imparare $ L $, non erano un sottoinsieme di quelle parlate da $ s_2 $,

Perché no?

Cordialmente, Alex

[hydro1]

Dire che $s_1$ parla almeno una lingua che $s_2$ non parla è come dire che le lingue parlate da $s_1$ non sono un sottoinsieme di quelle parlate da $s_2$. O c'è una distinzione tra parlare una lingua e capirla nel tuo problema?

[axpgn]

"hydro":Dire che $s_1$ parla almeno una lingua che $s_2$ non parla ...

Non mi pare che tu abbia detto questo ma più semplicemente che gli elementi di $S$ parlano un minor numero di lingue rispetto agli studenti che non appartengono a $S$, non fai nessun riferimento a quali lingue parlano né se siano uguali e in che misura.
Io ho interpretato così.

Ho notato che hai modificato il messaggio precedente ma non ho idea di quale sia la variazione; potresti indicarla? Grazie.

[Mathita]

@axpgn

Dopo aver letto la risposta di hydro, non sono sicuro di aver fatto un ragionamento corretto. Sia $L={l_1,l_2,...,l_n}$ l'insieme delle lingue parlate dagli studenti, e sia $n$ la sua cardinalità. $nCk$ indica il numero di sottoinsiemi distinti di $L$ composti da $k$ lingue, o equivalentemente, il numero di studenti che parlano $k$ lingue: in altri termini, identifico uno studente con l'insieme delle lingue che parla. Siccome gli studenti sono $250$, richiedo che $nCk\ge 250$ e $n$ sia il più piccolo possibile. Ho ragionato senza pormi il problema della sensatezza di ciò che stavo facendo.

[hydro1]

"axpgn":

[quote="hydro"]Dire che $s_1$ parla almeno una lingua che $s_2$ non parla ...

Non mi pare che tu abbia detto questo ma più semplicemente che gli elementi di $S$ parlano un minor numero di lingue rispetto agli studenti che non appartengono a $S$, non fai nessun riferimento a quali lingue parlano né se siano uguali e in che misura.
Io ho interpretato così.

Ho notato che hai modificato il messaggio precedente ma non ho idea di quale sia la variazione; potresti indicarla? Grazie.

[axpgn]

@hydro
Ok, l'avevi dato per sottinteso e io non lo avevo capito

Invece per quanto riguarda l'idea di Mathita, penso che vada bene perché non si tratta di trovare una soluzione specifica ma "solamente" che tra le possibili combinazioni ne esista almeno una che permetta la realizzazione di quanto richiesto, e con $10$ lingue questa possibilità esiste mentre con $9$ non lo è.

[axpgn]

Sostanzialmente la mia soluzione è analoga a quella di Mathita ...

Supponiamo che nella Scuola si parlino $n=4$ lingue diverse, tutti i sottoinsiemi di questo insieme di linguaggi rappresentano tutte le modalità con cui uno studente può esprimersi (da zero a quattro); dato che però sono solamente $16$ molti studenti parleranno esattamente le stesse lingue; lo stesso accade con $n=5,6,7$.
Con $n=8$ abbiamo $256$ modalità diverse purtroppo però succede che colui che parla $8$ lingue parla con tutti gli altri e allora eliminiamo questo caso. E altrettanto dobbiamo fare con chi parla $7, 6, 5$ lingue.
Il massimo l'abbiamo con $4$ ma in questo caso abbiamo solo $70$ modalità diverse: troppo poche.
E con $n=9$ saliamo a $126$, sempre poche.
È con $n=10$ che otteniamo il nostro obiettivo perché in questo caso c'è la possibilità che ciascuno studente parli $5$ lingue diverse ed in modo tale che nessuno parli esattamente le stesse lingue di qualcun altro.

Cordialmente, Alex

[Mathita]

@axpgn @hydro

La soluzione di axpgn mi torna: è simile alla mia ma con una spiegazione migliore. Mi farebbe piacere conoscere la tua opinione, hydro, perché ho un tarlo nella testa che mi garantisce che tu abbia trovato un bug che fa saltare tutto.

Grazie a entrambi.

[hydro1]

@Mathita

Non capisco bene la logica: come faccio ad escludere che si parlino 9 lingue? perché i sottoinsiemi di un insieme con 9 elementi sono $2^9=512$, quindi a priori c’è posto per tutti. Anche se le lingue sono 8, $2^8=256$, capisco che nessuno ne possa parlare 8 ma se tolgo l’insieme vuoto e quello con tutti e 8 gli elementi mi rimangono comunque 254 sottoinsiemi, come faccio a concludere che non ne posso pescare 250 che rispettano la condizione?

[axpgn]

Basta contarli

Sicuramente ci sarà un dimostrazione combinatoria (che adesso però non mi è ancora ben definita ) ma per esempio poniamo che ci sia uno studente che parla otto lingue, ce ne possono essere $256$ che non la parlano; tra questi $256$ ci sono anche gli altri otto che parlano anch'essi otto lingue diverse: se non li consideriamo scendiamo sotto i $250$, d'altra parte se ne consideriamo anche solo uno tra questi, ne escludiamo altri (che parlano meno lingue) è il totale scende comunque sotto i $250$.

Cordialmente, Alex

[Mathita]

Sebbene per me sia sufficiente la spiegazione di axpgn (è contestualizzata alla stanza in cui ci troviamo ed è comprensibile a uno studente delle scuole superiori), sto cercando una soluzione alternativa puramente combinatorica.

Per come ho scritto la mia soluzione, essa va interpretata così: 10 è il numero minimo di lingue, purché ciascuno studente ne parli esattamente 5. La contestazione di hydro è più che legittima: non ho dimostrato formalmente che non esistono altre configurazioni che abbassino ulteriormente il numero di lingue. Avendo usato il pc, ho perso di vista ciò che stavo facendo.

Da quello che ho capito, l'obiettivo è quello di dimostrare la seguente disuguaglianza: sia n il numero di lingue parlate dagli studenti, sia $s_k$ il numero di studenti della scuola che parlano $k$ lingue, dovrei dimostrare che

$\sum_{k=1}^n s_k\leq nCn/2$

Non ci sono ancora riuscito... Voi avete qualche idea?

[axpgn]

Dunque ... non sono riuscito a trovare qualcosa che mi dica quale sia il numero massimo di sottoinsiemi la cui intersezione non sia maggiore del numero di elementi del sottoinsieme meno uno (spero di aver definito bene la "cosa" )

Peraltro penso di poter affinare quanto ho detto in questo modo:

Sicuramente il numero cercato ha un minimo che è pari alla cardinalità del numero di sottoinsiemi di "mezzo" (es. $|L|=9$ allora il nostro numero è $N>=((9),(4))=126$) dato che sicuramente tutti questi sottoinsiemi differiscono almeno in un elemento.
Ne consegue che per aumentare $N$ dobbiamo aggiungere qualche sottoinsieme più grande o più piccolo od anche più di uno se ne togliamo qualcuno dal "gruppone medio".
Però se ne aggiungiamo uno più grande, questi contiene come sottoinsiemi uno o più di un sottoinsieme del "gruppone medio" quindi, aggiungendone uno grande, diminuiamo $N$ invece di aumentarlo.
Se ne aggiungiamo uno più piccolo, questi è contenuto in uno o più di quelli del "gruppone medio" e solamente $|L|$ di questi sottoinsiemi non "sottraggono" elementi al "gruppone medio" (perché già eliminati precedentemente i sottoinsiemi relativi ad essi - d'altronde il numero complessivo dei sottoinsiemi "minori" è minore di quello dei sottoinsiemi "maggiori") ovvero anche in questo caso aggiungere un sottoinsieme più piccolo fa diminuire $N$.
Quindi $N=((9),(4))=((9),(5))=126$

Chi formalizza?


Cordialmente, Alex

[Mathita]

Forse ho trovato una soluzione che richiede un teorema (che non conoscevo)

Il problema più grande che riscontro con questo tipo di problemi è la loro completa formalizzazione: in genere ogni quesito che pone axpgn mi manda ai matti, da questo punto di vista.

Sia $L={l_1,...,l_n}$ l'insieme composto da n elementi (lingue). Sia $\mathcal{S}={S_1,S_2,...,S_m} $ una famiglia di insiemi $S_i$ tali che:

$S_i\in\mathcal{P}(L);$

$S_i \notsubseteq S_j \wedge S_j\not subseteq S_i$ per ogni i diverso da j.

($\mathcal{S}$ è la scuola di Babele, $S_i$ sono gli studenti, $m=250$ nel nostro caso). In termini di teoria degli insiemi parzialmente ordinati, la famiglia $\mathcal{S}$ è un'anticatena di cardinalità (lunghezza) $m$ di $\mathcal{P}(L)$. Per il CELEBERRIMO teorema di Sperner, si ha che $m\le nC\floor{n/2} $. Rispondere al quesito di axpgn equivale a determinare il più piccolo intero positivo $n$ tale che $250\le nC\floor{n/2}$

[axpgn]

"Mathita":... in genere ogni quesito che pone axpgn mi manda ai matti, ...

Me ne scuso profondamente ma non posso promettere di non farlo più, è più forte di me

Mi sa che hai centrato l'obiettivo, quel teorema era quello che cercavo


Cordialmente, Alex

[Mathita]

[ot]Non devi scusarti axpgn! I tuoi quesiti mi insegnano sempre qualcosa di nuovo!

Gli interventi di hydro sono stati provvidenziali: sono serviti a farmi capire che ho ragionato superficialmente, perciò sento il dovere di ringraziarlo.[/ot]