[L03/04] Il ballo

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L03/04] Il ballo

Messaggioda Gerald Lambeau » 27/07/2017, 14:35

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).
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L03/04] Il ballo

Messaggioda Vinciii » 27/07/2017, 15:43

Credo di non aver capito bene la traccia
Vinciii
 
Messaggi: 67
Iscritto il: 17/02/2015, 14:14

Re: [L03/04] Il ballo

Messaggioda Vinciii » 27/07/2017, 16:34

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
Vinciii
 
Messaggi: 67
Iscritto il: 17/02/2015, 14:14

Re: [L03/04] Il ballo

Messaggioda Gerald Lambeau » 27/07/2017, 16:37

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.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L03/04] Il ballo

Messaggioda Vinciii » 27/07/2017, 16:51

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?
Vinciii
 
Messaggi: 67
Iscritto il: 17/02/2015, 14:14

Re: [L03/04] Il ballo

Messaggioda Gerald Lambeau » 27/07/2017, 16:58

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.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L03/04] Il ballo

Messaggioda Roob » 28/07/2017, 12:07

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?
Roob
 
Messaggi: 29
Iscritto il: 23/11/2016, 16:52

Re: [L03/04] Il ballo

Messaggioda Gerald Lambeau » 28/07/2017, 12:19

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 ;) .
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L03/04] Il ballo

Messaggioda [ProfMateMatto] » 28/07/2017, 16:13

Alla fine basta che tutti si divertano :mrgreen:
Comunque se c'è qualche problema con i punti esclamativi vedete pure il mio post
[ProfMateMatto]
 
Messaggi: 14
Iscritto il: 21/07/2017, 18:02


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite