2024 Kolokwium 1
Zadanie 1
Rozwiązanie 1
Przykładowa plansza dla \( n = 4\) wraz z zaznaczonym kwadratem centralnym \( A \). Zauważmy, że możemy ponumerować linie poziome i pionowe w planszy, a każdy prostokąt będzie jednoznacznie wyznaczony przez wybrane 4 linie (2 pionowe i 2 poziome). Pamiętając o tym, że wybrane prostokąty muszą zawierać \( A \) dochodzimy do wniosku, że początkowa linia pozioma musi znajdować się ponad \( A \), czyli na przedziale \( [0, n-1] \), zaś końcowa pod \( A \), czyli na przedziale \( [n, 2n-1] \). Analogiczne rozumowanie należy przeprowadzić dla linii pionowych.
Powyższe rozumowanie prowadzi nas do sumy, w której otrzymamy pola wszystkich możliwych prostokątów: $$ \sum_{i = 0}^{n-1} \sum_{j=n}^{2n-1} \sum_{k = 0}^{n-1} \sum_{l = n}^{2n-1} (j-i) \cdot (l-k) = n^6 $$
Rozwiązanie 2
Zauważmy, że suma pól prostokątów zawierających wyróżnione pole jest równa sumie pól wszystkich prostokątów minus sumie pól prostokątów, które nie zawierają tego pola. Oznaczmy jako \( A_{n \times m} \) sumę pól prostokątów złożonych z kwadratów jednostkowych w prostokącie wielkości \( n \times m \). Aby wyznaczyć tą wartość policzmy w ilu prostokątach zawarte jest wyróżnione pole o współrzędnych \(i , j \). Zawarte jest ono zawsze, jeżeli lewy górny róg znajduje się w lewo i w górę od tego pola, analogicznie prawy dolny w prawo i w dół. Czyli w \( ij(n-i+1)(m-j+1)\) prostokątach.
A zatem $$ A_{n \times m} = \sum_{i=1}^{n}\sum_{i=1}^{m}ij(n-i+1)(m-j+1) = \left(\sum_{i=1}^{n}i(n-i+1)\right) \left(\sum_{j=1}^{m}j(n-j+1)\right) = \binom{n+2}{3} \binom{m+2}{3} $$ Z zasady włączeń - wyłączeń nasz wynik jest równy $$ A_{2n-1 \times 2n-1} - 4A_{2n-1 \times n-1} + 4A_{n-1 \times n-1} $$ Po przekształceniach otrzymujemy \( n^6\).