XLVIII MOM

Zawody matematyczne:

XLVIII MOM, 2007

Zadania z XLVIII Międzynarodowej Olimpiady Matematycznej

Załącznik	Wielkość
XLVIII MOM - Zadania z rozwiązaniami [1]	161.93 KB

XLVIII MOM - Zadanie 1

Zawody matematyczne:

XLVIII MOM, 2007

Dane są liczby rzeczywiste $a_1$ , $a_2$ , $\ldots$ , $a_n$ . Dla każdego $i$ ( $1\le i\le n$ ) określamy

$ d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\} $

oraz

$ d=\max\{d_i:1\le i\le n\}. $

Dowieść, że dla każdych liczb rzeczywistych $x_1\le x_2\le\ldots\le x_n$ spełniona jest nierówność

$ \max\{|x_i-a_i|:1\le i\le n\}\ge{d\over 2}.\leqno(*) $
Wykazać, że istnieją takie liczby rzeczywiste $x_1\le x_2\le\ldots\le x_n$ , dla których nierówność $(*)$ staje się równością.

Rozwiązanie

Z określenia liczby $d$ wynika, że istnieje wskaźnik $q\in\{1,2,\ldots,n\}$ , dla którego $d=d_q$ . Niech ponadto wskaźniki $p$ i $r$ ( $1\le p\le q\le r\le n$ ) spełniają warunki

$ a_p=\max\{a_j:1\le j\le q\},\qquad a_r=\min\{a_j:q\le j\le n\}. $

Wówczas prawdziwa jest równość $d=a_p-a_r$ .

Jeżeli teraz $x_1\le x_2\le\ldots\le x_n$ są dowolnymi liczbami rzeczywistymi, to na mocy nierówności $x_r-x_p\ge 0$ otrzymujemy

$ (a_p-x_p)+(x_r-a_r)=(a_p-a_r)+(x_r-x_p)\ge a_p-a_r=d. $

Wynika stąd, że przynajmniej jedna z liczb $a_p-x_p$ , $x_r-a_r$ jest nie mniejsza niż $d/2$ . Tym bardziej jedna z liczb $|x_p-a_p|$ , $|x_r-a_r|$ jest nie mniejsza niż $d/2$ i w konsekwencji uzyskujemy

$ \max\{|x_i-a_i|:1\le i\le n\}\ge\max\{|x_p-a_p|,|x_r-a_r|\}\ge{d\over 2}, $

co dowodzi tezy punktu (a).
Wykażemy, że żądane własności mają następujące liczby:

$ x_1=a_1-{d\over 2} \qquad\hbox{oraz}\qquad x_k=\max\Bigl\{x_{k-1},a_k-{d\over 2}\Bigr\}\quad\hbox{dla }k=2,3,\ldots,n. $

Z powyższego określenia wynika, że dla $k=2,3,\ldots,n$ zachodzi nierówność $x_{k-1}\le x_k$ ; otrzymujemy stąd ciąg nierówności $x_1\le x_2\le\ldots\le x_n$ . Również na mocy tego określenia uzyskujemy

$ x_k-a_k\ge-{d\over 2}\qquad\hbox{dla }k=1,2,\ldots,n. $

Ustalmy teraz wskaźnik $k\in\{1,2,\ldots,n\}$ oraz niech $m$ będzie najmniejszym takim wskaźnikiem, że $x_m=x_k$ . Wówczas jeśli $m>1$ , to prawdziwa jest nierówność $x_m>x_{m-1}$ , co oznacza, że

$ x_k=x_m=a_m-{d\over 2}. $

Jest jasne, że powyższa równość ma miejsce także w przypadku, gdy $m=1$ . Możemy zatem napisać

$ a_m-a_k\le \max\{a_j:1\le j\le k\}-\min\{a_j:k\le j\le n\}= d_k\le d, $

skąd wnioskujemy, że

$ x_k-a_k=(x_k-a_m)+(a_m-a_k)=-{d\over 2}+(a_m-a_k)\le{d\over 2}. $

Udowodniliśmy w ten sposób, iż

$ -{d\over 2}\le x_k-a_k\le {d\over 2}\qquad\hbox{dla }k=1,2,\ldots,n, $

czyli

$ \max\{|x_i-a_i|:1\le i\le n\}\le{d\over 2}. $

Ponieważ jednak $|x_1-a_1|=d/2$ , więc w powyższej nierówności ma miejsce równość. To kończy rozwiązanie części (b).

XLVIII MOM - Zadanie 2

Zawody matematyczne:

XLVIII MOM, 2007

Rozpatrzmy takich pięć punktów płaszczyzny $A$ , $B$ , $C$ , $D$ , $E$ , że czworokąt $ABCD$ jest równoległobokiem, a na czworokącie wypukłym $BCED$ można opisać okrąg. Niech $\ell$ będzie prostą przechodzącą przez punkt $A$ . Przypuśćmy, że prosta $\ell$ przecina wnętrze odcinka $DC$ w punkcie $F$ , a prostą $BC$ w punkcie $G$ . Niech ponadto $EF=EG=EC$ . Udowodnić, że prosta $\ell$ jest dwusieczną kąta $DAB$ .

Rozwiązanie

Niech $K$ i $L$ będą rzutami prostokątnymi punktu $E$ odpowiednio na proste $CF$ i $CG$ (rys. 1). Z równości $EF=EG=EC$ wynika, że punkty $K$ i $L$ są odpowiednio środkami odcinków $CF$ i $CG$ , a ponadto $EK\perp CF$ i $EL\perp CG$ .

Na czworokącie $BCED$ można opisać okrąg, zatem

$ \measuredangle CBE=\measuredangle CDE. $

To oznacza, że trójkąty prostokątne $BLE$ i $DKE$ są podobne, skąd mamy

$ (1) \qquad {BL\over EL}={DK\over EK}. $

Zauważmy dalej, że na mocy równoległości $AD\parallel BG$ trójkąty $AFD$ i $GFC$ są podobne. To pozwala przeprowadzić następujący rachunek:

${BL\over CL}= {BC\over CL}+1= {BC\over\frac{1}{2}\cdot CG}+1= {AD\over \frac{1}{2}\cdot CG}+1= {DF\over \frac{1}{2}\cdot CF}+1= {DF\over FK}+1= {DK\over FK}= {DK\over CK}. $

Łącząc uzyskaną zależność z równością (1) stwierdzamy, że

$ {EL\over CL}={EK\over CK}. $

Zatem trójkąty prostokątne $ELC$ i $EKC$ są podobne (cecha bok-kąt-bok). Mają one jednak wspólny odpowiedni bok $EC$ ; są wobec tego przystające. W konsekwencji $CK=CL$ oraz $CF=CG$ . Udowodniliśmy w ten sposób, że trójkąt $FCG$ jest równoramienny. To daje

$ \measuredangle GAB=\measuredangle GFC=\measuredangle FGC=\measuredangle FAD, $

co jest równoznaczne z tezą.

XLVIII MOM - Zadanie 3

Zawody matematyczne:

XLVIII MOM, 2007

W zawodach matematycznych niektórzy uczestnicy przyjaźnią się. Przyjaźń jest zawsze wzajemna. Grupę uczestników nazwiemy kliką, jeśli każdych dwóch zawodników tej grupy przyjaźni się. (W szczególności, każda grupa złożona z mniej niż dwóch zawodników jest kliką.) Liczbę osób, jaką liczy klika nazwiemy jej rozmiarem.

Wiadomo, że w zawodach tych rozmiar największej kliki jest liczbą parzystą. Dowieść, że uczestników zawodów można rozdzielić do dwóch pokoi tak, aby rozmiar największej kliki w jednym pokoju był równy rozmiarowi największej kliki w drugim pokoju.

Rozwiązanie

Przedstawimy algorytm rozdzielenia uczestników zawodów do dwóch pokoi, które będziemy nazywać Pokój A oraz Pokój B. Rozpoczniemy od pewnego początkowego rozdzielenia, a następnie będziemy wielokrotnie przenosić jedną osobę do drugiego pokoju, tak by w efekcie uzyskać rozdzielenie spełniające warunki zadania.

Na każdym etapie postępowania niech $A$ i $B$ oznaczają zbiory uczestników znajdujących się w odpowiednich pokojach, zaś $k(A)$ oraz $k(B)$ - rozmiary największych klik w tych pokojach.

Postępowanie składa się z czterech kroków.

Krok 1. Niech $M$ będzie jedną z klik największego rozmiaru. Z założenia rozmiar $|M|=2m$ jest liczbą parzystą. Umieśćmy wszystkich zawodników z tej kliki w pokoju $A$ , a pozostałych uczestników w pokoju $B$ .

Ponieważ $M$ jest kliką największego rozmiaru, w takim początkowym rozmieszczeniu prawdziwa jest zależność $k(A)=|M|\ge k(B)$ .

Krok 2. Dopóki zachodzi nierówność $k(A)>k(B)$ , przenosimy dowolnie wybraną osobę z pokoju $A$ do pokoju $B$ .

Zauważmy przede wszystkim, że nierówność $k(A)>k(B)$ oznacza, że pokój $A$ jest niepusty. Ponadto wszyscy aktualni mieszkańcy pokoju $A$ tworzą klikę, więc po przeniesieniu jednej osoby z tego pokoju rozmiar największej kliki w pokoju $A$ zmniejszy się o 1. Natomiast rozmiar największej kliki w pokoju $B$ nie zmienia się albo zwiększy się o 1.

Po wielokrotnym przeprowadzeniu przeniesienia jednej osoby z pokoju $A$ do pokoju $B$ otrzymamy sytuację, w której

$ k(A)=k(B)\quad\hbox{albo}\quad k(A)=k(B)-1. $

Dodatkowo w pokoju $A$ pozostało co najmniej $m$ osób, gdyż w przeciwnym razie w pokoju $B$ znalazłoby się przynajmniej $m+1$ osób należących do kliki $M$ , a w pokoju $A$ pozostałoby najwyżej $m-1$ osób; mielibyśmy więc $k(A)\le m-1$ , $k(B)\ge m+1$ , wbrew uzyskanej wcześniej alternatywie.

Jeżeli $k(A)=k(B)$ , to otrzymane rozmieszczenie uczestników spełnia warunki zadania.

Możemy więc przyjąć w dalszej części rozumowania, że $k(A)=n$ oraz $k(B)=n+1$ . Jak udowodniliśmy powyżej, mamy wówczas

$ n=|A|=|A\cap M|\ge m\quad\hbox{oraz}\quad|B\cap M|\le m. $

Krok 3.Jeżeli istnieje uczestnik $x\in B\cap M$ oraz $(n+1)$ -elementowa klika $C$ , do której uczestnik $x$ nie należy, to przenosimy uczestnika $x$ do pokoju $A$ .

Uczestnik $x$ należy do kliki $M$ i wobec tego po przeniesieniu go do pokoju $A$ w pokoju tym znajdzie się $n+1$ uczestników, z których wszyscy należą do tej kliki. W efekcie $k(A)=n+1$ . Ponadto rozmiar największej kliki w pokoju $B$ wynosił $n+1$ przed przeniesieniem uczestnika $x$ , zaś $(n+1)$ -osobowa klika $C$ pozostała w całości w pokoju $B$ . Tak więc $k(B)=n+1$ , czyli $k(A)=k(B)$ .

Zatem jeśli udało się wykonać krok 3, uzyskaliśmy żądane rozmieszczenie uczestników w pokojach. W przeciwnym razie przechodzimy do kroku 4.

Krok 4. Dopóki spełniona jest równość $k(B)=n+1$ , wybieramy dowolną $(n+1)$ -osobową klikę $C$ znajdującą się w pokoju $B$ i przemieszczamy jednego uczestnika $x\in C\setminus M$ do pokoju $A$ .

Zauważmy przede wszystkim, że procedura ta jest wykonalna:

$ |C|=n+1\ge m+1>m\ge|B\cap M|, $

co dowodzi, że zbiór $C\setminus M$ jest niepusty.

Przemieszczając jedną osobę z pokoju $B$ do pokoju $A$ zmniejszamy rozmiar $k(B)$ najwyżej o 1. Wobec tego po zakończeniu kroku 4 uzyskamy rozmieszczenie, w którym $k(B)=n$ .

Ponadto po zakończeniu kroku 4 w pokoju $A$ będzie znajdowała się $n$ -osobowa klika $A\cap M$ . Udowodnimy, że w tym pokoju nie ma większej kliki.

Niech więc $D$ będzie dowolną kliką w pokoju $A$ .

Uczestników umieszczonych w pokoju $A$ można podzielić na dwie grupy:

uczestnicy należący do kliki $M$ ;
uczestnicy, którzy w kroku 4 zostali
przeniesieni z pokoju $B$ .

Mieszkańcy pokoju $A$ należący do pierwszej grupy oczywiście przyjaźnią się ze wszystkimi osobami tworzącymi klikę $M$ . Weźmy teraz pod uwagę mieszkańca sklasyfikowanego w drugiej grupie. Ponieważ nie udało się wykonać kroku 3, więc przed rozpoczęciem kroku 4 każda $(n+1)$ -osobowa klika w pokoju $B$ zawierała $B\cap M$ jako podzbiór. Wobec tego każda osoba przeniesiona z tej kliki do pokoju $A$ przyjaźniła się ze wszystkimi osobami należącymi do kliki $B\cap M$ .

Udowodniliśmy w ten sposób, że wszyscy mieszkańcy pokoju $A$ przyjaźnią się ze wszystkimi uczestnikami kliki $B\cap M$ . Zauważmy następnie, że zbiór $D\cup(B\cap M)$ jest sumą dwóch klik: $D$ oraz $B\cap M$ ; ponadto każdy uczestnik należący do pierwszej kliki przyjaźni się z dowolnym uczestnikiem należącym do drugiej kliki. Wobec tego $D\cup(B\cap M)$ jest kliką. Jej rozmiar nie przekracza największego rozmiaru kliki wśród wszystkich uczestników zawodów, czyli liczby $|M|$ . Stąd mamy

$ |M|\ge |D\cup(B\cap M)|=|D|+|B\cap M|=|D|+|M|-|A\cap M|. $

To pociąga nierówność $|D|\le|A\cap M|=n$ . Tym samym wykazaliśmy, że dowolna klika w pokoju $A$ liczy najwyżej $n$ uczestników.

Ostatecznie $k(A)=k(B)=n$ , a to oznacza, że rozmieszczenie uczestników w pokojach po zakończeniu kroku 4 spełnia warunki zadania.

XLVIII MOM - Zadanie 4

W trójkącie $ABC$ dwusieczna kąta $BCA$ przecina okrąg opisany na tym trójkącie w punkcie $R$ różnym od $C$ , symetralną odcinka $BC$ w punkcie $P$ oraz symetralną odcinka $AC$ w punkcie $Q$ . Punkt $K$ jest środkiem odcinka $BC$ , a punkt $L$ jest środkiem odcinka $AC$ . Wykazać, że trójkąty $RPK$ oraz $RQL$ mają równe pola.

Rozwiązanie

Niech $O$ oznacza środek okręgu opisanego na trójkącie $ABC$ .

Jeżeli $AC=BC$ , to dwusieczna kąta $BCA$ jest osią symetrii trójkąta $ABC$ . Zatem punkty $P$ , $Q$ i $O$ pokrywają się, zaś punkty $K$ i $L$ są symetryczne względem tej dwusiecznej. Wobec tego trójkąty $RPK$ i $RQL$ są symetryczne względem prostej $CR$ ; w szczególności mają one równe pola.

Załóżmy więc, że $AC\ne BC$ . Dla ustalenia uwagi niech $AC<BC$ (rys. 2).

Oznaczmy: $\measuredangle BCA=\gamma$ . Trójkąty $PKC$ i $QLC$ mają kąty proste odpowiednio przy wierzchołkach $K$ i $L$ , a ponadto $\measuredangle PCK=\measuredangle QCL=\gamma/2$ . Zatem trójkąty te mają równe także trzecie kąty: $\measuredangle KPC$ i $\measuredangle LQC$ . Stąd mamy

$ \measuredangle OPQ=\measuredangle KPC=\measuredangle LQC=\measuredangle PQO. $

To dowodzi, że trójkąt $OPQ$ jest równoramienny ( $OP=OQ$ ). Ponadto

$ \measuredangle OPQ=\measuredangle KPC=90^\circ-\measuredangle KCP=90^\circ-\frac{1}{2}\gamma $

i w efekcie dostajemy zależność $\measuredangle POQ=180^\circ-2\measuredangle OPQ=\gamma$ . Dalej, zauważmy, że $OA=OR=OB$ oraz

$ \measuredangle AOR=\measuredangle ROB=2\measuredangle ACR=2\measuredangle RCB=\gamma. $

Uzyskane zależności pozwalają stwierdzić, że obrót wokół punktu $O$ o kąt $\gamma$ przeprowadza punkty $Q$ , $A$ , $R$ odpowiednio na punkty $P$ , $R$ , $B$ . Stąd wniosek, że trójkąty $RQA$ i $RBP$ są przystające.

Punkt $K$ jest środkiem odcinka $BC$ , więc jego odległość od prostej $CR$ jest równa połowie odległości punktu $B$ od tej prostej. To oznacza, że

$ [RPK]=\frac{1}{2}[RBP], $

gdzie przez $[{\cal F}]$ oznaczamy pole figury ${\cal F}$ . Analogicznie

$ [RQL]=\frac{1}{2}[RQA]. $

Łącząc dwie powyższe równości z wykazanym wcześniej przystawaniem trójkątów $RBP$ i $RQA$ dostajemy tezę zadania:

$ [RPK]=\frac{1}{2}[RBP]=\frac{1}{2}[RQA]=[RQL]. $

XLVIII MOM - Zadanie 5

Zawody matematyczne:

XLVIII MOM, 2007

Niech $a$ oraz $b$ będą liczbami całkowitymi dodatnimi. Dowieść, że jeśli liczba $(4a^2-1)^2$ jest podzielna przez $4ab-1$ , to $a=b$ .

Rozwiązanie

Przypuśćmy, że teza zadania jest fałszywa. Niech $S$ oznacza zbiór wszystkich takich par $(a,b)$ liczb całkowitych dodatnich, że $a\ne b$ oraz liczba $(4a^2-1)^2$ jest podzielna przez $4ab-1$ .

Z przyjętego założenia wynika, że zbiór $S$ jest niepusty. Udowodnimy ponadto, że:

Dla każdej pary $(k,m)\in S$ spełniającej warunek $k<m$ istnieje para $(k,n)\in S$ , w której $n<k$ .
Jeżeli para $(k,m)$ należy do zbioru $S$ , to para $(m,k)$ również.

Dowód zdania1. Przyjmijmy

$ w={(4k^2-1)^2\over 4km-1}. $

Para $(k,m)$ należy do zbioru $S$ , zatem liczba $w$ jest całkowita. Zależności $(4k^2-1)^2\equiv 1\,\,\mod{4k}$ oraz $4km-1\equiv -1\,\,\mod{4k}$ w połączeniu z równością $(4k^2-1)^2=(4km-1)w$ dowodzą, że $m\equiv -1\,\,\mod{4k}$ , czyli $w=4kn-1$ dla pewnej liczby całkowitej dodatniej $n$ . Wykażemy, że liczba $n$ spełnia tezę zdania 1.

Rzeczywiście, z określenia liczby $w$ wynika, że jest ona dzielnikiem liczby $(4k^2-1)^2$ . Z uwagi na równość $w=4kn-1$ dostajemy więc $(k,n)\in S$ . Ponadto na podstawie zależności $k<m$ możemy napisać

$ 4kn-1=w={(4k^2-1)^2\over 4km-1}<{(4k^2-1)^2\over 4k^2-1}=4k^2-1, $

skąd płynie wniosek, że $n<k$ .

Dowód zdania2. Należy dowieść, że z podzielności $4km-1\,|\,(4k^2-1)^2$ wynika podzielność $4km-1\,|\,(4m^2-1)^2$ . Ponieważ liczba

$ \begin{split} k^2(4m^2-1)^2-m^2(4k^2-1)^2 &=16m^2k^2(m^2-k^2)+k^2-m^2=\cr &=(m^2-k^2)(4km-1)(4km+1) \end{split} $

jest podzielna przez $4km-1$ , więc z zależności $4km-1\,|\,(4k^2-1)^2$ otrzymujemy $4km-1\,|\,k^2(4m^2-1)^2$ . Jednak liczby $k^2$ i $4km-1$ są względnie pierwsze, co pociąga podzielność $4km-1\,|\,(4m^2-1)^2$ .

Zbiór $S$ jest niepusty, więc wśród wszystkich par $(c,d)\in S$ możemy wybrać parę, dla której wartość $2c+d$ jest najmniejsza.

Przypuśćmy, że $c<d$ . Wówczas na mocy zdania 1. istnieje w zbiorze $S$ taka para $(c,d')$ , że $d'<c$ . Zatem $2c+d'<2c+c<2c+d$ , wbrew minimalności liczby $2c+d$ . Wobec tego zachodzi nierówność $c>d$ . Zdanie 2. dowodzi, że para $(d,c)$ należy do zbioru $S$ . Jednakże $2d+c<2c+d$ , co ponownie prowadzi do sprzeczności z minimalnością liczby $2c+d$ .

Uzyskana sprzeczność dowodzi, że rozpatrywana teza jest prawdziwa.

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