XLVIII MOM - Zadanie 6

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

\[<br /> S=\{(x,y,z):x,y,z\in\{0,1,\ldots,n\},\,x+y+z>0\}<br /> \]

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

\[<br /> (1) \qquad P(x_1,\ldots,x_{k-1},x_k)=<br /> Q(x_k)W(x_1,\ldots,x_{k-1},x_k)+R(x_1,\ldots,x_{k-1},x_k),<br /> \]

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

\[<br /> P(a_1,\ldots,a_{k-1},a_k)=R(a_1,\ldots,a_{k-1},a_k)<br /> \quad\hbox{dla }a_1,\ldots,a_{k-1},a_k\in<br /> \{0,1,\ldots,n\};<br /> \]

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

\[<br /> (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,<br /> \]

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

\[<br /> R_n(0,\ldots,0)\ne0\qquad\hbox{oraz}\qquad R_n(a_1,\ldots,a_{k-1})=0<br /> \]

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

\[<br /> x+y+z=i\qquad\hbox{dla }i=1,2,\ldots,3n<br /> \]

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 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź