Opublikowane na Archiwum Olimpiady Matematycznej (https://archom.ptm.org.pl)

Strona główna > Wersja do wydruku > Wersja do wydruku

XVIII ZMPB - Zadanie 10

Zawody matematyczne: 
XVIII ZMPB, 2007

Dana jest tablica $ 18\times 18 $, 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 $, w którym wszystkie pola są białe. Załóżmy, że przy wykonywaniu ciągu dozwolonych operacji wybraliśmy wiersz $ W $. Skoro początkowo wszystkie pola położone w wierszu $ W $ 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 $ W $, to nie mogła zostać wybrana żadna kolumna - w przeciwnym bowiem razie pole stojące na przecięciu tej kolumny z wierszem $ W $ byłoby czarne. To jednak oznacza, że we wszystkich wykonanych operacjach wybierany był wiersz, różny od wiersza $ W $. 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.

  • Kombinatoryka i logika
  • Zawody Matematyczne Państw Bałtyckich
  • 2000-2009
  • 2006-2007
© Prawa autorskie Polskie Towarzystwo Matematyczne | Serwis znajduje się na serwerze MIMUW | Projekt: Krystyna Jaworska | Realizacja: Paweł Witkowski INTools, Tomasz Filar

Adres źródła: https://archom.ptm.org.pl/?q=node/133