[L05] Riemanniani, Mogli e Mariti

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

[L05] Riemanniani, Mogli e Mariti

Messaggioda Federico II » 13/10/2015, 16:22

In una nazione (una a caso, diciamo la Riemannia) il matrimonio è permesso a tutte le età e con un numero illimitato di partner, ma non è ammesso il matrimonio omosessuale. Un insieme di uomini si dice pieno di mogli se ogni donna in Riemannia è sposata con almeno un uomo dell'insieme, e analogamente un insieme di donne si dice pieno di mariti se ogni uomo in Riemannia è sposato con almeno una donna dell'insieme. Dimostrare che il numero di insiemi di uomini pieni di mogli e il numero di insiemi di donne pieni di mariti hanno la stessa parità.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L05] Riemanniani, Mogli e Mariti

Messaggioda matematto » 13/10/2015, 18:20

Federico II ha scritto:Il matrimonio è permesso a tutte le età e con un numero illimitato di partner, ma non è ammesso il matrimonio omosessuale..

Perchè tutta questa omofobia?? :? :(
Avatar utente
matematto
 
Messaggi: 137
Iscritto il: 27/11/2014, 17:12

Re: [L05] Riemanniani, Mogli e Mariti

Messaggioda Federico II » 13/10/2015, 20:11

Per non creare confusione nel problema... poi chiedilo al presidente della Riemannia :D
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L05] Riemanniani, Mogli e Mariti

Messaggioda cip999 » 26/10/2015, 17:40

Carino e interessante.

Testo nascosto:
Sia $\mathfrak{B}$ l'insieme degli uomini della Riemannia e $\mathfrak{G}$ l'insieme delle donne. Sia inoltre $E$ il numero di relazioni coniugali tra gli elementi di $\mathfrak{B}$ e $\mathfrak{G}$. Andiamo di induzione estesa su $\lvert\mathfrak{B}\rvert + \lvert\mathfrak{G}\rvert + E$.

Passo base: $\lvert\mathfrak{B}\rvert + \lvert\mathfrak{G}\rvert + E = 0$ (aka i Riemanniani sono estintisi). C'è poco da dire, il numero di insiemi di uomini pieni di mogli è uguale a $0$, così come il numero di insiemi di donne pieni di mariti.
Passo induttivo: Siano $b \in \mathfrak{B}$ e $g \in \mathfrak{G}$ un uomo e una donna sposati (il caso $E = 0$ si fa a parte ed è such trivial). Chiamiamo $W \subseteq \mathfrak{B}$ l'insieme degli insiemi pieni di mogli, e $\tilde{W} \subseteq W$ l'insieme degli insiemi pieni di mogli se si esclude il matrimonio tra $b$ e $g$. Poniamo $W' = W \setminus \tilde{W}$, da cui $\lvert W\rvert = \lvert \tilde{W}\rvert + \lvert W'\rvert$ ($W'$ è l'insieme degli insiemi pieni di mogli che cessano di esserlo se $b$ e $g$ non sono sposati). Qualche considerazione su $W'$:
  1. Ogni insieme pieno di mogli che appartiene a $W'$ contiene $b$, poiché altrimenti sarebbe un insieme pieno di mogli anche nel caso in cui $b$ non fosse sposato con $g$ (ogni donna sarebbe comunque sposata con ogni uomo nell'insieme), e quindi apparterrebbe a $\tilde{W}$.
  2. Ogni elemento di $W'$ non contiene nessuno degli uomini sposati con $g$, eccetto $b$. Infatti, in caso contrario $g$ avrebbe un marito nell'insieme pur non essendo sposata con $b$, pertanto quell'insieme sarebbe un elemento di $\tilde{W}$ e non di $W'$.
  3. Se un insieme pieno di mogli contiene $b$ e non contiene nessuno degli altri uomini sposati con $g$, allora quell'insieme sta in $W'$. Difatti, eliminando la relazione coniugale tra $b$ e $g$ quest'ultima non sarà più sposata con nessun uomo dell'insieme, per cui questo non è più pieno di mogli.
  4. Consideriamo un paese confinante con la Riemannia, la Gaùssia. Per ogni abitante $p$ della Riemannia, c'è un suo clone in Gaùssia di nome $p'$, salvo per $b$, $g$ e tutti gli uomini/donne sposati a uno di essi, che non hanno cloni. La Gaùssia non ha ulteriori abitanti, e due Gaussiani (di sesso opposto) sono sposati se e solo se lo sono i loro corrispettivi abitanti della Riemannia. Allora la cardinalità di $W'$ è uguale al numero di insiemi pieni di mogli in Gaùssia.
    Dimostrazione. È facile accorgersi, grazie alle considerazioni fin qui fatte, che è possibile associare in modo univoco a ogni elemento di $W'$ un insieme di uomini Gaussiani pieno di mogli.
In modo del tutto analogo (per simmetria, se vogliamo) si dimostra che, detti $H \subseteq \mathfrak{G}$ l'insieme degli insiemi pieni di mariti e $\tilde{H} \subseteq H$ l'insieme degli insiemi pieni di mariti se $b$ e $g$ non sono sposati, e posto $H' = H \setminus \tilde{H}$, esiste una bigezione tra $H'$ e l'insieme degli insiemi pieni di mariti in Gaùssia.
Ma per ipotesi induttiva $\lvert\tilde{W}\rvert$ e $\lvert\tilde{H}\rvert$ hanno la stessa parità, così come il numero di insiemi di uomini pieni di mogli e quello di donne piene di mariti in Gaùssia (e quindi $\lvert W'\rvert$ e $\lvert H'\rvert$). Ne consegue che anche $\lvert W\rvert = \lvert\tilde{W}\rvert + \lvert W'\rvert$ e $\lvert H\rvert = \lvert\tilde{H}\rvert + \lvert H'\rvert$ hanno la medesima parità.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L05] Riemanniani, Mogli e Mariti

Messaggioda cip999 » 27/10/2015, 16:00

Rettifico

Testo nascosto:
Il passo base non è esattamente quello che ho scritto ieri, in realtà bisognerebbe trattare tre casi:
  • $\lvert\mathfrak{B}\rvert = \lvert\mathfrak{G}\rvert = 0$: c'e un solo insieme pieno di mogli e un solo insieme pieno di mariti (l'insieme vuoto in ambedue i casi).
  • Uno tra $\mathfrak{B}$ e $\mathfrak{G}$ è vuoto e l'altro no (WLOG $\mathfrak{B} = \oslash$): allora non ci sono insiemi pieni di mogli, mentre gli insiemi pieni di mariti sono $2^{\lvert\mathfrak{G}\rvert}$ (quindi entrambi pari).
  • $\lvert\mathfrak{B}\rvert, \: \lvert\mathfrak{G}\rvert > 0$ ed $E = 0$: non ci sono né insiemi pieni di mogli né insiemi pieni di mariti.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L05] Riemanniani, Mogli e Mariti

Messaggioda Federico II » 27/10/2015, 17:11

Va bene, io ho avuto più o meno la tua idea ma un po' semplificata, e la mia soluzione corrisponde alla seconda di quelle ufficiali.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti