Dividere in 2 stanze in modo che le conoscenze siano pari

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Dividere in 2 stanze in modo che le conoscenze siano pari

Messaggio da dario2994 » 20 set 2011, 15:53

Ci sono tanti tizi, alcuni di loro si conoscono e la conoscenza è sempre simmetrica.
Sia $M$ il numero di modi in cui posso dividerli in 2 stanze in modo che ognuno conosca un numero pari di persone nella propria stanza.
Sia $N$ il numero di modi in cui posso dividerli in 2 stanze in modo che ognuno conosca un numero pari di persone nell'altra stanza.
Dimostrate che $M=N$

p.s. Inventato in parte da me. Credo sia un risultato noto perchè è troppo bello per non esserlo :D Una soddisfazione immensa averlo risolto :!: :!: :!:
p.p.s. è tosto, perlomeno la mia soluzione lo è abbastanza, quindi piazzate anche solo idee e santoddio non mettetele nascoste ;) E se proprio serve metterò hint tra un poco (anche se non sono un gran fan degli hints... soprattutto ora che sul forum vanno fortissimo :? )
p.p.p.s. Gallai ha dimostrato $M\ge 1$ (il matematico Ungherese non il vecchio utente del forum :!: ) che è un facile corollario di questo ;)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Tess
Messaggi: 254
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Tess » 23 set 2011, 20:40

Ecco le mie misere considerazioni sviluppate in qualche ora di letteratura.

Equivalentemente posso 2 colorare i vertici del grafo in modo che:
a) il numero di vertici adiacenti ad uno dato del colore uguale a questo siano pari;
b) il numero di vertici adiacenti ad uno dato del colore divesro a questo siano pari.

Alcune osservazioni anche abbastanza banali:
Se prendo un pezzo di grafo che è un albero ed è collegato con al più un lato alla parte restante, questo posso colorarlo in un solo modo (a meno di scambiare i colori), sempre che mi sia permesso dal resto del grafo;
Posso costruire dei cammini (in realtà cicli) che percorrino una strada in (a) monocromatica, in (b) di colori alterni e di lunghezza pari se trovo un modo di colorarlo tale che in (a) ci sia almeno un vertice collegato con uno dello stesso colore, in (b) di colore diverso.

L'unica idea che mi è venuta in mente che potrebbe avvicinarsi, perlomeno, alla soluzione è quella di costruire una sorta di funzione che mi trasformi una colorazione di (a) in una di (b) sfruttando il fatto di poter "suddividere" il grafo in parti ad albero ed in parti cicli. Questa funzione (che poi è una bigezione) fa una sorta di scambio tra cammini monocromatici ed alterni.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da dario2994 » 23 set 2011, 20:49

Tess ha scritto:Ecco le mie misere considerazioni sviluppate in qualche ora di letteratura.

Equivalentemente posso 2 colorare i vertici del grafo in modo che:
a) il numero di vertici adiacenti ad uno dato del colore uguale a questo siano pari;
b) il numero di vertici adiacenti ad uno dato del colore divesro a questo siano pari.

Alcune osservazioni anche abbastanza banali:
Se prendo un pezzo di grafo che è un albero ed è collegato con al più un lato alla parte restante, questo posso colorarlo in un solo modo (a meno di scambiare i colori), sempre che mi sia permesso dal resto del grafo;
Posso costruire dei cammini (in realtà cicli) che percorrino una strada in (a) monocromatica, in (b) di colori alterni e di lunghezza pari se trovo un modo di colorarlo tale che in (a) ci sia almeno un vertice collegato con uno dello stesso colore, in (b) di colore diverso.

L'unica idea che mi è venuta in mente che potrebbe avvicinarsi, perlomeno, alla soluzione è quella di costruire una sorta di funzione che mi trasformi una colorazione di (a) in una di (b) sfruttando il fatto di poter "suddividere" il grafo in parti ad albero ed in parti cicli. Questa funzione (che poi è una bigezione) fa una sorta di scambio tra cammini monocromatici ed alterni.
Viva :D Vanno benissimo e sono apprezzatissimi, soprattutto dal sottoscritto, considerazioni del genere :wink:
Qualche commento:
l'equivalenza con le colorazioni è giusta
il fatto che gli alberi li posso non considerare è giusta ;)
Non ho capito il fatto sui cicli...
Riguardo all'esistenza della bigezione ecco un fatto a riguardo, che può essere un hint quindi lo nascondo:
Testo nascosto:
La bigezione purtroppo non è una buona strada dato che per b) esiste sempre la soluzione banale di colorare tutti dello stesso colore, mentre per a) spesso non esiste alcuna soluzione banale :roll:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Tess
Messaggi: 254
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Tess » 23 set 2011, 21:37

dario2994 ha scritto:Non ho capito il fatto sui cicli...
Prendiamo un vertice che abbia collegato un vertice di colore uguale (se in (a)) o divesro (se in (b)). Per l'ipotesi sulla parità (mettiamo di aver già una configurazione che funzioni) ce n'è un altro. Per entrambi questi due ne esiste un altro ancora, e così via finchè le strade che partono da questi due non si incontrano: ho formato un ciclo che sarà monocromatico in (a) e alternato in (b).
La bigezione effettivamente non è banale...
Può essere che sia N, o M, una potenza di 2?

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da dario2994 » 23 set 2011, 21:43

Tess ha scritto: Può essere che sia N, o M, una potenza di 2?
Può essere :wink:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Anér » 24 set 2011, 10:50

Algebra lineare?
Sono il cuoco della nazionale!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da dario2994 » 24 set 2011, 14:54

Anér ha scritto:Algebra lineare?
La mia soluzione circa sì... ma ora piazzala!
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Anér » 24 set 2011, 20:14

Chiamo $n$ il numero di tizi e pongo, per i che va da 1 a n, $x_i=0$ se l'i-esimo tizio sta nella prima stanza, e $x_i=1$ se l'i-esimo tizio sta nella seconda stanza. Le $x_i$ sono dunque n variabili da pensare modulo 2. Pongo infine $a_{ij}=1$ se i tizi numero i e j si conoscono, e 0 altrimenti. Ovviamente $a_{ij}=a_{ji}$ e impongo $a_{ii}=0$ per ogni i da 1 a n.
A questo punto ho che $x_i+x_j=1$ se e solo se i e j sono in stanze diverse, per cui in una configurazione del secondo tipo devo avere , per ogni i da 1 a n, $\sum_{j=1}^n a_{ij}(x_i+x_j)=0$ che è come dire che il tizio i conosce un numero pari (0 modulo 2) di altri tizi nell'altra stanza. Dunque N è il numero di soluzioni del sistema delle n equazioni lineari nelle variabili $x_i$ come questa. M invece, analogamente, sarà il numero di soluzioni del sistema delle n equazioni del tipo $\sum_{j=1}^n a_{ij}(x_i+x_j+1)=0$ con i che va da 1 a n. Da qui si trova subito che tanto M quanto N sono pari a 0 (se i sistemi sono impossibili) oppure sono potenze di 2 (grossolanamente bisogna vedere quanti gradi di libertà si hanno e per ogni grado di libertà si possono scegliere 2 valori). A questo punto bisogna dimostrare che il secondo sistema ha una soluzione, e che le soluzioni dei due sistemi, prese come vettori, si comportano bene rispetto alla somma.
Sono il cuoco della nazionale!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da dario2994 » 24 set 2011, 20:22

Anér ha scritto: A questo punto bisogna dimostrare che il secondo sistema ha una soluzione, e che le soluzioni dei due sistemi, prese come vettori, si comportano bene rispetto alla somma.
Tutto quello scritto prima di questo è perfetto, uguale a me.
Anche la prima cosa che scrivi è giusta... tocca ancora mostrare che $M\ge 1$.
La seconda cosa non l'ho capita... che vuol dire che si comportano bene rispetto alla somma? Per concludere credo basti $M\ge 1$ :roll: (e se non basta io non ho concluso allora :D )

edit: Aner sta dando per scontato che $N\ge 1$... se qualcuno non sa perchè lo dimostri e lo scriva :wink: (ma questo è facile facile)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Tess
Messaggi: 254
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Tess » 24 set 2011, 23:57

Spero di non sparare grandissime boiate, ora che credo di aver trovato qualchecosa di sensato! :)

Voglio dimostrare che il secondo sistema è indeterminato. (che significa che esistono almeno 2 soluzioni, d'altra parte anche del primo ne esistono almeno 2)
Per farlo mi basta dimostrare che prese le matrici $ A,A_1,...,A_n $, che sono $ A $ la matrice principale del sistema, $ A_i $ le matrici associate alle variabili $ x_i $ (quelle ottenute sostituendo alla colonna $ i $ della matrice $ A $ la colonna dei termini noti), ho che i determinanti di tutte sono 0.
Ora, la matrice $ A $ è uguale alla matrice formata dagli $ a_{ij} $ prima definiti da Anér, se non per la diagonale, che presenta un 1 nell'$ i-esima $ posizione se il vertice $ i $ ha grado dispari, 0 se ha grado pari. Questo ci dice che ogni riga (e colonna) ha un numero pari di 1. D'altra parte, anche il vettore dei termini noti ha un numero pari di 1. Quindi ogni $ A_i $ ha per ogni colonna un numero pari di 1.
Notiamo, ora, che moltiplicando una qualsiasi matrice con questa proprietà per il vettore di tutti 1, otteniamo quello nullo (infatti sommo un numero pari di 1 per ogni prodotto scalare). Ma allora un autovalore è nullo, quindi il determinante è nullo.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da dario2994 » 25 set 2011, 10:04

Mi mancano un po' di conoscenze per capire la soluzione di Tess... ma credo di averne abbastanza per dire che è sbagliata :o
Mi pare che il tuo ragionamento si applichi anche al sistema (modulo 2!):
$1x+1y+0z=1$
$1x+1y+0z=0$
$0x+0y+0z=1$
Dato che anche qui tutte le colonne hanno somma pari... ma questo sistema chiaramente non ha soluzione!
Potrei aver preso una gran cantonata, nel caso correggimi :!:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

fph
Site Admin
Messaggi: 3625
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da fph » 25 set 2011, 11:43

I conti che fa Tess mi sembrano giusti, ma ad essere sbagliato è il teorema che vuole applicare:
Per farlo mi basta dimostrare che prese le matrici $ A,A_1,...,A_n $, che sono $ A $ la matrice principale del sistema, $ A_i $ le matrici associate alle variabili $ x_i $ (quelle ottenute sostituendo alla colonna $ i $ della matrice $ A $ la colonna dei termini noti), ho che i determinanti di tutte sono 0.
Ora, sembra che tu voglia applicare una variante di Rouché-Capelli, ma in realtà non funziona perché dimostrando che i determinanti sono 0 dimostri che il rango delle matrici è $\leq n-1$, non $=n-1$. Potrebbe succedere che i ranghi della matrice del sistema e di quella aumentata siano per esempio $n-1$ e $n-2$, come nel controesempio di dario2994; quindi non sono uguali e i due sistemi non hanno soluzione. Per "aggiustare" questo ragionamento dovresti andare a guardarti i minori, ma sembra impossibile cavare qualcosa di buono perché i ranghi "veri" (cioè il numero di soluzioni) dipendono da come è fatto il grafo (cioè la matrice $A$).

Inoltre, per rendere più chiaro il tutto a chi legge il thread, sottolineo il fatto che state usando questo risultato:
sia $\ker A:=\{z : Az=0\}$ lo spazio delle soluzioni di quel sistema omogeneo (che è un sottospazio vettoriale), e sia $x_*$ una soluzione particolare del sistema $Ax=b$. Allora le soluzioni di $Ax=b$ sono tutti e soli i vettori che si scrivono nella forma $x_*+z$, con $z\in \ker A$. In particolare, è un traslato di $\ker A$ (sottospazio affine) e ha la stessa dimensione.

Questo si può interpretare come un enunciato sulla controimmagine della funzione $f(x)=Ax$: se chiamiamo $f^{-1}(b)$ l'insieme di tutti i vettori $x$ tali che $f(x)=b$, allora per ogni $b$ gli insiemi $f^{-1}(b)$ sono tutti uguali a meno di traslazione e sono tutti sottospazi affini isomorfi al sottospazio vettoriale $\ker(A)=f^{-1}(0)$. Questa è una situazione che ricapita spesso è che è bene avere chiara. Per esempio in tutti i problemi "di tipo lampadine", una delle idee base da capire per smontarli di algebra lineare è chiamare $f(x)=Ax$ l'applicazione che manda una configurazione degli interruttori $x$ nella corrispondente configurazione di lampadine $b=f(x)$. A questo punto questo risultato vi dice che ogni configurazione di lampadine ottenibile la ottenete in tanti modi diversi che differiscono tra loro per un oggetto nel kernel (cioè una delle possibili operazioni sugli interruttori che lascia invariata la configurazione delle lampadine). In particolare, questo vi permette di contare le possibili configurazioni di lampadine diverse ottenibili, in quanto
\[
\text{numero di punti nell'immagine di $f$}=\frac{\text{numero di punti nello spazio di partenza $\mathbb{F}^n$ (configurazioni di interruttori possibili)}}{\text{numero di punti in $f^{-1}(0)=\ker f$}}.
\]
Notate che sono tutte potenze di due, in quanto dimensioni di sottospazi vettoriali. Questa formula è vera più in generale (basta avere un omomorfismo tra due gruppi, cioè un oggetto che "rispetta l'addizione"). Si può anche andare oltre, e definire lo spazio "$\mathbb{F}^n \mod \ker A$" dei vettori nello spazio di partenza modulo un oggetto in $\ker A$, e dire che questo è isomorfo all'immagine. Questo è noto come (primo) teorema di isomorfismo (ricordatevi di citare il nome o riscrivere l'enunciato se lo usate in una soluzione, non è un fatto banalissimo).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

gatto_silvestro
Messaggi: 27
Iscritto il: 20 nov 2010, 17:48

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da gatto_silvestro » 25 set 2011, 14:43

Il sistema $ \sum_{j=1}^n a_{ij}(x_i+x_j+1)=0 $ ha almeno una sol per la simmetria degli $ a_{i,j} $ (poichè le conoscienze son simmetriche) e per il fatto che il coef di $ x_i $della i-esima equazione è uguale al termine noto.

Se infatti due equazioni (k e l) avessero gli stessi coef. allora in particolare detti K e L i rispettivi termini noti (e dunque anche i coef di $ x_k $ della prima e di $ x_l $ nella seconda, allora $ K=a_{l,k}=a_{k,l}=L $
Ultima modifica di gatto_silvestro il 25 set 2011, 15:34, modificato 1 volta in totale.

fph
Site Admin
Messaggi: 3625
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da fph » 25 set 2011, 15:05

gatto_silvestro ha scritto:Il sistema $ \sum_{j=1}^n a_{ij}(x_i+x_j+1)=0 $ ha almeno una sol per la simmetria degli $ a_{i,j} $ e per il fatto che l'i-esimo coef della i-esima equazione è uguale al termine noto.
Se infatti due equazioni (k e l) avessero gli stessi coef. allora in particolare detti K e L i rispettivi termini noti $ K=a_{k,l}=a_{l,k}=L $
Sorry ma non seguo... puoi spiegare con qualche parola in più?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: Dividere in 2 stanze in modo che le conoscenze siano par

Messaggio da Anér » 25 set 2011, 21:25

Chiamiamo sistema introverso quello le cui soluzioni corrispondono alle disposizioni dei tizi per cui ogni tizio conosce un numero pari di caii nella sua stanza, ed estroverso l'altro (così distinguiamo i due sistemi). Ora è facile vedere (basta un conticino) che se B e C sono vettori soluzioni del sistema introverso e F e G sono vettori soluzioni del sistema estroverso, allora B+C e F+G sono soluzioni del sistema estroverso, mentre F+B è soluzione del sistema introverso. Questo è il significato esplicitato di "i vettori soluzione si comportano bene rispetto alla somma". Ora serve dimostrare che il sistema introverso ammette una soluzione: scelta una soluzione B del sistema introverso, sommando B a tutte le soluzioni del sistema estroverso si ottengono tutte quelle del sistema introverso, e viceversa (tra l'altro sommando due volte B si torna al punto di partenza, quindi siamo sicuri anche che l'associazione che stiamo facendo è bigettiva). Ora perché esiste una soluzione al sistema introverso? Se non prendo un granchio dovrebbe valere il seguente teorema: dato un sistema di equazioni lineari in n incognite da risolvere in un campo, chiamiamo composizione delle equazioni la somma membro a membro di alcune equazioni, ognuna con un peso. Ogni equazione, anche una composizione, è formata da un termine noto e da una somma di variabili moltiplicate ognuna per un coefficiente. Se componendo le equazioni di un sistema si ottiene un'equazione con termine noto non nullo ma "parte delle variabili" nulla (ovvero tutte le variabili hanno coefficiente 0) allora il sistema è chiaramente impossibile (ha un contraddizione interna). Ma se ciò non accade, ovvero ogni composizione con parte delle variabili nulla ha anche termine noto nullo, allora il sistema ammette soluzione.
Se poi il campo sono gli interi modulo 2 una composizione sarà prendere alcune equazioni e sommarle membro a membro (c'è poca scelta per i pesi delle equazioni). Bisogna dimostrare che se una tale composizione ha parte delle variabili nulla, allora 1) L'insieme di equazioni scelte è una stanza di una disposizione estroversa e 2) In una disposizione estroversa la somma dei gradi dei vertici in una stanza è pari.
Sono il cuoco della nazionale!

Rispondi