XVIII ZMPB - Zadanie 10

Dana jest tablica , której każde pole może być białe albo czarne. Początkowo wszystkie pola są białe. Możemy wykonywać następującą operację: wybieramy kolumnę lub wiersz i zmieniamy kolory wszystkich pól w tej kolumnie lub wierszu. Czy wykonując wielokrotnie taką operację możemy otrzymać tablicę, w której będzie dokładnie 16 czarnych pól?

Rozwiązanie

Odpowiedź: Nie można.

Zauważmy przede wszystkim, że jeżeli wykonując wielokrotnie opisaną operację wybierzemy dwukrotnie ten sam wiersz lub tę samą kolumnę, to uzyskamy taką samą tablicę, jaką uzyskalibyśmy nie wybierając w ogóle tego wiersza lub tej kolumny. Wobec tego wystarczy rozpatrywać przypadek, w którym każdy wiersz i każda kolumna została wybrana najwyżej raz.

Przypuśćmy, że udało nam się uzyskać tablicę, w której dokładnie 16 pól jest czarnych.

Ponieważ liczba wszystkich wierszy jest równa 18, więc istnieje wiersz , w którym wszystkie pola są białe. Załóżmy, że przy wykonywaniu ciągu dozwolonych operacji wybraliśmy wiersz . Skoro początkowo wszystkie pola położone w wierszu były białe oraz po zakończeniu operacji wszystkie te pola są również białe, więc musiała zostać wybrana każda kolumna. Wówczas jednak każdy wiersz składałby się wyłącznie z białych albo wyłącznie z czarnych pól; łączna liczba tych ostatnich byłaby zatem podzielna przez 18.

Z drugiej strony, jeżeli podczas wykonywania dopuszczalnych operacji nie wybraliśmy wiersza , to nie mogła zostać wybrana żadna kolumna - w przeciwnym bowiem razie pole stojące na przecięciu tej kolumny z wierszem byłoby czarne. To jednak oznacza, że we wszystkich wykonanych operacjach wybierany był wiersz, różny od wiersza . Podobnie jak poprzednio, wynika stąd, że każdy wiersz składa się tylko z białych albo tylko z czarnych pól, więc liczba czarnych pól nie może być równa 16. Otrzymana sprzeczność kończy rozwiązanie.