Ukryta treść:
Zauważmy, że możliwych podzbiorów do pokolorowania (razem z pustym) jest \(\displaystyle{ 2^{2n-1}}\) i tyle samo jest możliwych ustawień parzystości w kolumnach i wierszach (bo się sumy muszą zgadzać). Zatem jeżeli dla każdego kolorowania to ustawienie parzystości jest inne, to jest takie przy którym mamy wszędzie nieparzyście.
Jeśli z kolei są dwa takie same to bierzemy ich różnicę symetryczną i wychodzi nam wszędzie parzyście.
Jeśli z kolei są dwa takie same to bierzemy ich różnicę symetryczną i wychodzi nam wszędzie parzyście.
Ukryta treść:
Rozważmy przestrzeń liniową \(\displaystyle{ W}\) wszystkich kolorowań nad \(\displaystyle{ \mathbb Z_2}\) (z różnicą symetryczną jako dodawaniem). Teraz rozważamy przekształcenie liniowe w możliwe ustawienia parzystości (wiadomo, jakie) i jeżeli jądro jest trywialne, to wartość \(\displaystyle{ (1,1,\dots,1)}\) jest przyjmowana, a jeżeli nie, to przyjmowana jest wartość \(\displaystyle{ (0,0,\dots,0)}\) gdzieś poza zerem.
Poza tym widać tutaj, że ustawień, gdzie jest wszędzie nieparzyście jest tyle, co takich, że wszędzie jest parzyście lub 0, i zawsze liczba ustawień, gdzie wszędzie jest parzyście, jest potęgą dwójki.
Poza tym widać tutaj, że ustawień, gdzie jest wszędzie nieparzyście jest tyle, co takich, że wszędzie jest parzyście lub 0, i zawsze liczba ustawień, gdzie wszędzie jest parzyście, jest potęgą dwójki.
Ukryta treść:
Rozważamy sobie równania postaci \(\displaystyle{ \delta_{i1} a_{i1}+\delta_{i2}a_{i2}+\dots+\delta_{in}a_{in}=a}\) nad \(\displaystyle{ \mathbb Z_2}\) dla ustalonego \(\displaystyle{ i}\), gdzie \(\displaystyle{ a_{ij}}\) to stan w \(\displaystyle{ i}\)-tym wierszu i \(\displaystyle{ j}\)-tej kolumnie, a \(\displaystyle{ \delta_{ij}}\) jest zerowe wtedy i tylko wtedy, gdy pole w \(\displaystyle{ i}\)-tym wierszu i \(\displaystyle{ j}\)-tej kolumnie jest niewyróżnione (analogiczne równania rozważamy dla stałych kolumn, zauważmy że jako niewiadome traktujemy tylko te \(\displaystyle{ a_{ij}}\), które się biorą z wyróżnionych pól). Teraz robimy z nich układ równań i ponieważ równania są jednorodne, to z Kroneckera-Capellego przestrzeń liniowa rozwiązań ma wymiar co najmniej 1 (bo rząd macierzy układu jest mniejszy od \(\displaystyle{ 2n}\) dlatego, że wszystkie równania się zerują).
