[L03/04] Il ballo

[Gerald Lambeau]

Non mi ricordo se è già passato, però è bello: ad un ballo ci sono $n$ ragazzi e $n$ ragazze. Ogni ragazzo vorrebbe poter ballare con una ragazza (e viceversa), ma nessuno dei presenti vuole ballare con qualcuno che non conosce (la conoscenza è reciproca).
Determinare il numero minimo $m$, in funzione di $n$, tale che è sempre possibile accontentare tutti se ci sono $m$ coppie ragazzo-ragazza che si conoscono (nel senso, i membri di ogni coppia si conoscono, non le coppie tra di loro, che ha poco senso; inoltre, un ragazzo o una ragazza possono appartenere a più di una delle $m$ coppie, ma ognuno ballerà con esattamente una persona, cioè per ogni ragazzo e per ogni ragazza dovrete scegliere esattamente una delle coppie in cui compare e se per una persona scegliete una coppia, dovrete scegliere quella anche per l'altro/a componente della coppia).

[Vinciii]

Credo di non aver capito bene la traccia

[Vinciii]

Ci provo (ma potrei aver sbagliato tutto, non ne sono molto sicuro)

Testo nascosto:

$m$ deve essere maggiore di $n^2-n$, infatti con $n^2-n$ coppie potrebbe capitare che ogni ragazzo conosce esattamente $n-1$ ragazze e quindi potrebbe esserci una ragazza che nessuno conosce. D'altra parte $n^2-n+1$ funziona in quanto, per il pigeonhole c'è almeno un ragazzo che conosce tutte le ragazze (e viceversa), e se per assurdo ci fossero due ragazze che conoscono entrambe solo lo stesso ragazzo allora $m$ potrebbe essere al massimo $n(n-2)+2$ quando tutte le altre ragazze conoscono tutti i ragazzi e loro conoscono solo quello là, ma $n(n-2)+2=n^2-2n+2<n^2-n+1$ per $n>1$ e quindi non si verifica mai questo caso. Quindi la mia risposta è $n^2-n+1$. Potrei anche aver detto solo scemenze, fatemi sapere xD

[Gerald Lambeau]

Le cose che dici sono giuste, ma non dici perché "almeno un ragazzo che conosce tutte le ragazze (e viceversa)"+"non ci sono due ragazze che conoscono solo lo stesso ragazzo" porti alla soluzione.

[Vinciii]

Hai ragione, non sono bravo a scrivere formalmente ma ci provo

Testo nascosto:

Affinchè sia possibile collegare tutti c'è bisogno che tutti conoscano almeno una persona (ed è vero perchè ho fatto vedere che c'è almeno un ragazzo che conosce tutte le altre ragazze e viceversa) e che ogni qual volta che due persone conoscono una stessa persona, dato che solo una di loro potrà farci coppia, una delle due deve avere sempre almeno un'altra scelta. Basta questo?

[Gerald Lambeau]

No. Siano $A, B, C$ tre ragazze e $D, E$ due ragazzi (gli altri ora li ignoriamo). Se a $A, C$ piacesse $D$ e a $B, C$ piacesse $E$ abbiamo che $C$ ha sempre un'altra scelta, ma ciò implicherebbe "rubare" il ragazzo alla rimanente povera terza esclusa.
Con le ipotesi e quello che ti sei trovato può darsi che si possa aggiustare, ma non ne sono molto convinto: al crescere di $n$ le situazioni possibili diventano molto brutte.

[Roob]

Come avete fatto vedere $m\geq n(n-1)+1$.
Dimostriamo per induzione che effettivamente $m=n(n-1)+1$.

Passo base: $n=1$.
In questo caso $1(1-1)+1=1$, l'unica conoscenza possibile è quella tra l'unico ragazzo e l'unica ragazza, che possono ballare insieme.

Passo induttivo: $n>1$.
Notiamo che esiste almeno un ragazzo che conosce al più $n-1$ ragazze. Se infatti tutti ne conoscessero $n$, il numero di conoscenze sarebbe uguale a $n^2$, che è maggiore di $n(n-1)+1=n^2-n+1$ per ogni $n> 2$. Facciamo ballare il ragazzo con meno conoscenze (in particolare meno di $n$) con una qualsiasi delle ragazze che conosce. Ci troviamo in una situazione con $n-1$ ragazzi e $n-1$ ragazze, in cui il numero di conoscenze è maggiore o uguale a $n(n-1)-(n-1)+1>(n-1)(n-2)+1$ (basta raccogliere e dividere per $n-1$, che è sempre diverso da 0). Ma per ipotesi induttiva $(n-1)(n-2)+1$ conoscenze bastavano per poter ballare tutti, per cui la tesi è dimostrata.

Va bene?

[Gerald Lambeau]

Quasi. Quando togli il ragazzo e la ragazza che hai scelto, poi sottrai solo il numero di archi che escono dal ragazzo, invece devi togliere dal conto anche quelli che escono dalla ragazza. Anche nel caso peggiore, però, questo non è un problema.
PS: è ovvio che se ci si fa con $n^2-n+1$ ci si fa anche con più, poi se tutte le ragazze conoscessero tutti i ragazzi sarebbe veramente stupido l'accoppiamento, quindi quello non è un problema. Ad ogni modo questa è solo una nota a margine.

Un hint su come l'ho fatto io:

Testo nascosto:

sfruttare l'ambientazione del problema .

[[ProfMateMatto]]

Alla fine basta che tutti si divertano
Comunque se c'è qualche problema con i punti esclamativi vedete pure il mio post