Zadanie 2
2007
Etap II
★★★★☆Kombinatoryka
Logika
Tablica z zerami i jedynkami
Powiązane zadania:
Zad. 2 (2005)
Treść zadania
W każde pole tablicy o wymiarach wpisano liczbę lub . Następnie obliczono sumy liczb stojących w każdym wierszu, w każdej kolumnie i na obu przekątnych. Wykaż, że co najmniej trzy sumy są jednakowe.
Umiejętności (4)
Wymagane umiejętności:
Zasada szufladkowa
Parzystość i nieparzystość
Zdobywane umiejętności:
Zasada szufladkowa
Parzystość i nieparzystość
Wskazówki (0/4)
Wskazówka 1
Ile jest wszystkich sum do obliczenia i jakie wartości mogą one przyjmować? Zauważ, że proste użycie zasady szufladkowej nie wystarczy, by udowodnić tezę.
Wskazówka 2
Załóż dla dowodu nie wprost, że żadne trzy sumy nie są równe. Co w tej sytuacji możesz powiedzieć o zbiorze wartości wszystkich dziesięciu sum?
Wskazówka 3
Jeśli żadne trzy sumy nie są równe, to zbiór sum musi zawierać po dwie wartości 0, 1, 2, 3 i 4. Zastanów się, co oznacza dla liczb w tablicy, że jedna z sum jest równa 0, a inna 4.
Wskazówka 4
Linia (wiersz, kolumna lub przekątna) o sumie 0 składa się z samych zer, a linia o sumie 4 z samych jedynek. Czy takie dwie linie mogą się przeciąć? Rozważ wszystkie możliwe pary takich linii.