Zadanie 3
2016
Etap I
★★★☆☆Kombinatoryka
Logika
Tablica z liczbami , ,
Treść zadania
W każde pole tablicy należy wpisać jedną z liczb , , w taki sposób, aby suma liczb w każdej kolumnie była nieujemna, a suma liczb w każdym wierszu była niedodatnia. Jaką najmniejszą liczbę zer można w ten sposób wpisać w pola tablicy? Odpowiedź uzasadnij.
Umiejętności (5)
Wymagane umiejętności:
Zasada ekstremalna
Konstrukcja przykładu
Zdobywane umiejętności:
Zasada ekstremalna
Konstrukcja przykładu
Podwójne zliczanie
Wskazówki (0/4)
Wskazówka 1
Zauważ, że suma wszystkich liczb w tablicy jest sumą sum wierszy, ale też sumą sum kolumn. Jakie ograniczenie na tę całkowitą sumę wynika z faktu, że sumy wierszy są niedodatnie, a kolumn nieujemne?
Wskazówka 2
Skoro całkowita suma liczb w tablicy musi wynosić 0, to jakie muszą być sumy poszczególnych wierszy i kolumn, biorąc pod uwagę warunki z treści zadania?
Wskazówka 3
Rozważ dowolny wiersz o sumie 0. Jeśli jest w nim jedynek, to ile musi być minus jedynek? Pamiętaj, że wiersz ma długość 11 (liczba nieparzysta) – co z tego wynika dla minimalnej liczby zer w tym wierszu?
Wskazówka 4
Wiesz już, że w każdym wierszu musi wystąpić co najmniej jedno zero, więc zer jest minimum 11. Spróbuj skonstruować przykład takiej tablicy, umieszczając zera na przekątnej i odpowiednio dobierając oraz .