XLVIII MOM - Zadanie 6

Zawody matematyczne:

XLVIII MOM, 2007

Niech $n$ będzie liczbą całkowitą dodatnią. Rozpatrujemy

$ S=\{(x,y,z):x,y,z\in\{0,1,\ldots,n\},\,x+y+z>0\} $

jako zbiór $(n+1)^3-1$ punktów w przestrzeni trójwymiarowej. Wyznaczyć najmniejszą możliwą liczbę płaszczyzn, których suma zawiera zbiór $S$ , ale nie zawiera punktu $(0,0,0)$ .

Rozwiązanie

Udowodnimy najpierw następujący

Lemat

Niech $P(x_1,x_2,\ldots,x_k)$ będzie wielomianem $k$ zmiennych. Przypuśćmy, że dla dowolnych liczb $a_1,a_2,\ldots,a_k \in\{0,1,\ldots,n\}$ , nie wszystkich równych zeru, zachodzi równość $P(a_1,a_2,\ldots,a_k)=0$ , natomiast $P(0,0,\ldots,0)\ne 0$ . Wówczas stopień wielomianu $P$ jest nie niższy niż $kn$ .

Dowód

Przeprowadzimy indukcję ze względu na wartość $k$ .

Dla $k=1$ teza jest prawdziwa, gdyż wielomian $P$ ma $n$ pierwiastków: 1, 2, $\ldots$ , $n$ , lecz nie jest wielomianem zerowym ( $P(0)\ne 0$ ). Jego stopień jest zatem równy co najmniej $n$ .

Niech teraz dany będzie wielomian $P(x_1,\ldots,x_{k-1},x_k)$ , gdzie $k\ge 2$ . Niech $W(x_1,\ldots,x_{k-1},x_k)$ i $R(x_1,\ldots,x_{k-1},x_k)$ będą odpowiednio ilorazem i resztą z dzielenia wielomianu $k$ zmiennych $P(x_1,\ldots,x_{k-1},x_k)$ przez wielomian jednej zmiennej $x_k$ określony wzorem $Q(x_k)=x_k(x_k-1)\ldots(x_k-n)$ . Inaczej mówiąc, prawdziwa jest równość wielomianów

$ (1) \qquad P(x_1,\ldots,x_{k-1},x_k)= Q(x_k)W(x_1,\ldots,x_{k-1},x_k)+R(x_1,\ldots,x_{k-1},x_k), $

przy czym wszystkie potęgi zmiennej $x_k$ występujące w wielomianie $R$ mają wykładniki mniejsze od stopnia wielomianu $Q$ .

Liczby 0, 1, 2, $\ldots$ , $n$ są pierwiastkami wielomianu $Q$ , zatem na mocy równości (1) otrzymujemy

$ P(a_1,\ldots,a_{k-1},a_k)=R(a_1,\ldots,a_{k-1},a_k) \quad\hbox{dla }a_1,\ldots,a_{k-1},a_k\in \{0,1,\ldots,n\}; $

oznacza to, że wielomian $R$ również spełnia założenia lematu. Ma on ponadto stopień nie wyższy niż wielomian $P$ . Wystarczy więc dowieść, że stopień wielomianu $R$ jest równy co najmniej $kn$ .

Ponieważ $Q$ jest wielomianem zmiennej $x_k$ stopnia $n+1$ , więc wszystkie potęgi zmiennej $x_k$ występujące w wielomianie $R$ mają wykładnik nie większy niż $n$ . Wobec tego istnieje przedstawienie postaci

$ (2) \qquad R(x_1,\ldots,x_{k-1},x_k)= \sum_{i=0}^n R_i(x_1,\ldots,x_{k-1})x_k^i, $

gdzie $R_n$ , $R_{n-1}$ , $\ldots$ , $R_0$ są wielomianami $k-1$ zmiennych.

Wykażemy, że do wielomianu $R_n(x_1,\ldots,x_{k-1})$ można zastosować założenie indukcyjne.

Rozważmy wielomian $T(y)=R(0,\ldots,0,y)$ zmiennej $y$ . Na mocy równości (2) ma on stopień co najwyżej $n$ ; ponadto liczby $1, 2, \ldots, n$ są jego pierwiastkami, zaś liczba 0 - nie jest. Skutkiem tego wielomian $T$ ma stopień równy $n$ , a współczynnik przy potędze $y^n$ , czyli $R_n(0,\ldots,0)$ , jest różny od zera.

Podobnie, niech $a_1,\ldots,a_k\in\{0,1,\ldots,n\}$ będą dowolnymi liczbami, z których przynajmniej jedna jest różna od zera i weźmy pod uwagę wielomian $T(y)=R(a_1,\ldots,a_n,y)$ zmiennej $y$ . W tym przypadku wielomian $T$ ma $n+1$ pierwiastków: 0, 1, $\ldots$ , $n$ , lecz jego stopień nie przekracza $n$ . Wobec tego wielomian $T$ jest zerowy i jego współczynnik $R_n(a_1,\ldots,a_{k-1})$ przy potędze $y^n$ jest równy zeru.

Udowodniliśmy w ten sposób, że

$ R_n(0,\ldots,0)\ne0\qquad\hbox{oraz}\qquad R_n(a_1,\ldots,a_{k-1})=0 $

dla dowolnych liczb $a_1$ , $\ldots$ , $a_{k-1}\in\{0,1,\ldots,n\}$ , nie wszystkich równych zeru.

Na mocy założenia indukcyjnego wielomian $R_n(x_1,\ldots,x_{k-1})$ ma więc stopień nie niższy niż $(k-1)n$ . Stąd wniosek, że wielomian $R_n(x_1,\ldots,x_{k-1})x_k^n$ zawiera jednomian stopnia co najmniej $kn$ , w którym występuje czynnik $x_k^n$ . Jednomian ten nie skróci się z żadnym z jednomianów występujących w składnikach postaci $R_i(x_1,\ldots,x_{k-1})x_k^i$ dla $i=0,1,\ldots,n-1$ , ponieważ te ostatnie zawierają potęgi zmiennej $x_k$ o wykładniku nie przekraczającym $n-1$ . Stąd i z zależności (2) wynika, że wielomian $R(x_1,\ldots,x_{k-1},x_k)$ zawiera jednomian stopnia co najmniej $kn$ . To kończy rozumowanie indukcyjne i dowód lematu.

Przechodzimy do rozwiązania zadania.

Przypuśćmy, że danych jest $N$ płaszczyzn, których suma zawiera zbiór $S$ , ale nie zawiera punktu $(0,0,0)$ . Niech $i$ -ta płaszczyzna ( $i=1,2,\ldots,N$ ) zadana będzie równaniem $a_ix+b_iy+c_iz+d_i=0$ . Rozpatrzmy wielomian $P(x,y,z)$ będący iloczynem $N$ wielomianów postaci $a_ix+b_iy+c_iz+d_i$ . Jest to wielomian stopnia $N$ o następujących własnościach:

$P(x_0,y_0,z_0)=0$ dla każdego punktu $(x_0,y_0,z_0)\in S$ ;
$P(0,0,0)\ne 0$ .

Zatem wielomian $P(x,y,z)$ spełnia założenia lematu. Wobec tego jego stopień jest nie niższy niż $3n$ , skąd otrzymujemy nierówność $N\ge 3n$ .

Pozostaje zauważyć, że suma $3n$ płaszczyzn zadanych równaniami

$ x+y+z=i\qquad\hbox{dla }i=1,2,\ldots,3n $

zawiera zbiór $S$ - gdyż punkty tego zbioru mają współrzędne całkowite, których suma należy do przedziału $\langle 1; 3n\rangle$ - oraz nie zawiera punktu $(0,0,0)$ .

Odpowiedź: Szukana najmniejsza liczba płaszczyzn wynosi $3n$ .