Zadanie 5
2018
Etap III
★★★★☆Kombinatoryka
Logika
Tablica
Treść zadania
W każde pole tablicy o wymiarach wpisano jedną z liczb , lub . Okazało się, że w każdym kwadracie złożonym z pól tablicy suma pewnych trzech spośród czterech wpisanych liczb jest równa zero. Jaka jest największa możliwa suma wszystkich liczb wpisanych w pola tablicy? Odpowiedź uzasadnij.
Umiejętności (5)
Wymagane umiejętności:
Analiza przypadków
Konstrukcja przykładu
Zasada ekstremalna
Zdobywane umiejętności:
Niezmienniki
Konstrukcja przykładu
Wskazówki (0/4)
Wskazówka 1
Rozważ dowolny kwadrat 2x2. Zgodnie z warunkiem zadania, suma trzech z jego czterech liczb wynosi 0. Co to mówi o sumie wszystkich czterech liczb w tym kwadracie?
Wskazówka 2
Aby znaleźć największą możliwą sumę, spróbuj umieścić w tablicy jak najwięcej jedynek. Zastanów się, jakie są konsekwencje wypełnienia całego wiersza jedynkami.
Wskazówka 3
Pokaż, że jeśli w pewnym wierszu znajdują się same jedynki, to w każdym wierszu z nim sąsiadującym suma liczb nie może być większa niż -2.
Wskazówka 4
Wykorzystaj wniosek z poprzedniej wskazówki, aby oszacować maksymalną sumę. Ile wierszy z samymi jedynkami można maksymalnie umieścić w tablicy i gdzie, aby suma wszystkich liczb była jak największa?