Dividere in 2 stanze in modo che le conoscenze siano pari

[dario2994]

Aner credo ti stia un po' complicando la vita ma non poi tanto, l'idea fondamentale comunque è la stessa mia e consiglio di portarla avanti (sarebbe quello della somma di alcune equazioni che danno la nulla e termine noto non nullo <-> sistema impossibile).

Mi pare che qui la teoria stia diventando controproducente! Tutto quello dimostrato finora (M,N potenza di $2$, $M\ge 1$ allora $M=N$, il fatto detto da Aner) si dimostrano benissimo e facilmente senza determinanti e robe di algebra lineare

Comunque continua a restar solo da dimostrare $M\ge 1$... e l'idea di Aner aiuta molto

p.s. Tutta la roba sugli introversi ed estroversi mi pare proprio superflua... il fatto è che 2 sistemi che differiscono solo nei termini noti che hanno entrambi almeno una soluzione hanno lo stesso numero di soluzioni! E poco importa di tutto il resto

[Nabir Albar]

Provo a concludere da dove ha lasciato Andrea: se sommando alcune equazioni si annullano tutti i coefficienti e il termine noto, posso eliminare una di queste equazioni (che è deducibile dalle altre) e ottenere un sistema equivalente; altrimenti se il termine noto non si annulla il sistema è impossibile. Dunque, se dimostro che il termine noto si deve annullare sempre, eliminando abbastanza equazioni arriverò a un sistema con le righe dei coefficienti "linearmente indipendenti" (si vede facilmente che questo ha almeno una soluzione).
Sia $A'$ la matrice $n\times n$ dei coefficienti e $c_1,c_2,\dots,c_n$ i termini noti. È facile osservare che $a'_{ij}=a_{ij}$ se $i\neq j$, mentre $a'_{ii}=-c_i=c_i$ (siamo modulo 2).
Se sommando alcune equazioni si annullano tutti i coefficienti, questo equivale a dire che per un certo sottoinsieme $S\subseteq \{1,2,\ldots,n\}$ (cui corrisponde il sottoinsieme di equazioni) vale, per ogni $j$, $\displaystyle\sum_{i\in S} a'_{ij}=0$ (questo è il coeff. di $x_j$ nell'equazione ottenuta).
La tesi in simboli è $\displaystyle\sum_{i\in S} c_i=0$. Riducendomi a considerare le $j\in S$, ottengo che $\displaystyle\sum_{i\in S} a'_{ij}=\sum_{i\in S\setminus\{j\}} a'_{ij}+a'_{jj}$. I termini dell'ultima somma sono $a_{ij}$ (essendo $i\neq j$), mentre $a'_{jj}=c_j=0+c_j=a_{jj}+c_j$. Quindi possiamo scrivere che se $j\in S$ vale $\displaystyle 0=\sum_{i\in S} a'_{ij}=\sum_{i\in S} a_{ij}+c_j$, da cui $\displaystyle c_j=\sum_{i\in S} a_{ij}$.
Ma allora $\displaystyle\sum_{j\in S} c_j=\sum_{j\in S}\sum_{i\in S} a_{ij}=\sum_{(i,j)\in S\times S} a_{ij}$. Ogni $a_{ij}$, con $i<j$, si semplifica con $a_{ji}$ e $a_{ii}=0$, dunque il secondo membro è $0$, da cui $\sum_{j\in S} c_j=0$.

[Anér]

Ok, Nabir Albar ha concluso quello che mancava, ora sappiamo che il sistema introverso non ammette contraddizioni; bisognerebbe ora dimostrare che 1) il numero di soluzioni è una potenza di 2 (cosa che non abbiamo ancora fatto) e che non dipende dai termini noti (cosa che ho fatto attraverso la funzione bigettiva che manda il vettore V nel vettore V+B, ove B è una soluzione scelta del sistema introverso).

[dario2994]

Non ho letto come si deve quello che ha scritto Nabir Albar ma sono fiduciosissimo che sia più che giusto
Bon il problema per me è risolto e la soluzione è identica alla mia.
Continuo a non cogliere le problematiche che sollevi Aner... in ogni caso per quel che capisco rispondo:
Il fatto che un sistema con una soluzione abbia una potenza di 2 di soluzioni... bon si può fare facendo finta di risolvere il sistema per sostituzione e quando si arriva ad un 0=0 si salta quell'equazione... tante volte capiterà uno 0=0 sostituendo una per volta le varie variabili tante variabili mi "avanzeranno alla fine" e ne potrò scegliere il valore come voglio... ma allora il numero di soluzioni è $2$ alla numero di variabili libere dato che queste le posso scegliere in 2 modi.

Bon ora che l'avete risolto qualche commento:
1) Si può mostrare $M\ge 1$ anche con pura combinatoria, ma la dimostrazione è parecchio difficile, la trovate in Combinatorial problems and exercises di Lovasz non ricordo in che sezione ma mi pare problema 17 di quella sezione (forze sezione 5)
2) Gallai in un articolo mai pubblicato è stato il primo a piazzare la dimostrazione che avete piazzato qui di $M\ge 1$... da cui poi viene banalmente tutto il problema, quindi insomma questo problema è di Gallai
3) Io l'ho letto ad uno stage in Francia in cui si chiedeva solo di dimostrare, credo, $N$ potenza di 2 ma sbagliandomi a ricordare il testo del problema ho pensato di dover dimostrare $M$ potenza di 2... poi ho riscoperto il vero problema e bon è venuto fuori questo.