XVIII ZMPB - Zadanie 8

Zawody matematyczne:

XVIII ZMPB, 2007

Nazwijmy zbiór $A$ liczb całkowitych nieizolowanym, jeżeli dla każdego $a\in A$ przynajmniej jedna z liczb $a-1$ , $a+1$ także należy do $A$ . Udowodnić, że liczba pięcioelementowych nieizolowanych podzbiorów zbioru $\{1,2,\ldots,n\}$ wynosi $(n-4)^2$ .

Rozwiązanie

Zauważmy, że pięcioelementowe zbiory nieizolowane dzielą się na dwie kategorie:

Zbiory postaci $\{a,a+1,a+2,a+3,a+4\}$ dla pewnej liczby całkowitej $a$ .
Zbiory postaci $\{a,a+1,a+2\}\cup\{b,b+1\}$ , gdzie $a$ i $b$ są takimi liczbami całkowitymi, że każda z liczb $a$ , $a+1$ , $a+2$ jest różna od $b-1$ , $b$ , $b+1$ , $b+2$ .

Podzbiory nieizolowane postaci $\{a,a+1,a+2,a+3,a+4\}\subseteq\{1,2,\ldots,n\}$ otrzymujemy dla $a=1,2,\ldots,n-4$ . Jest więc $n-4$ takich podzbiorów.

Podzbiory nieizolowane postaci $\{a,a+1,a+2\}\cup\{b,b+1\}\subseteq\{1,2,\ldots,n\}$ , dla których $a<b$ , otrzymujemy wybierając najpierw liczbę $b\in\{1,2,\ldots,n-1\}$ , a następnie liczbę $a\in\{1,2,\ldots,b-4\}$ . Musi przy tym być spełniona nierówność $b\ge 4$ ; w przeciwnym razie nie będziemy bowiem mogli dobrać żadnej wartości $a$ . Ponadto przy ustalonej wartości $b\ge 4$ możemy wybrać liczbę $a$ na $b-4$ sposobów. Sumując liczbę $b-4$ dla wartości $b=4,5,\ldots,n-1$ otrzymamy $0+1+2+\ldots+(n-5)=\xfrac{1}{2}(n-5)(n-4)$ .

Rozumując w analogiczny sposób łatwo stwierdzamy, że również liczba nieizolowanych podzbiorów postaci $\{a,a+1,a+2\}\cup\{b,b+1\}\subseteq\{1,2,\ldots,n\}$ , w których $a>b$ , wynosi $\frac{1}{2}(n-5)(n-4)$ . Stąd wniosek, że liczba wszystkich nieizolowanych pięcioelementowych podzbiorów zbioru $\{1,2,\ldots,n\}$ jest równa

$<br /> (n-4)+\xfrac{1}{2}(n-5)(n-4)+\xfrac{1}{2}(n-5)(n-4)=(n-4)^2.<br />$