Feladat: 2007. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Nagy Csaba 
Füzet: 2007/október, 391. oldal  PDF  |  MathML 
Témakör(ök): Térgeometriai számítások trigonometria nélkül, Sík egyenlete, Teljes indukció módszere, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 2007/szeptember: 2007. évi Nemzetközi Matematika Diákolimpia 23. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Nagy Csaba megoldása. A feladat kérdésére a válasz: 3n. Ennyi sík valóban elegendő, például az x+y+z=1, x+y+z=2, ..., x+y+z=3n egyenletű síkok megfelelnek.
Megfordítva, tegyük fel, hogy néhány síkkal lefedtük S-et, az origót azonban nem. Megmutatjuk, hogy a síkok száma legalább 3n. Írjuk föl a síkok egyenletét ax+by+cz+d=0 alakban (ahol a, b, c nem mind nulla). Szorozzuk össze az egyenletek bal oldalán álló kifejezéseket; egy p(x,y,z) polinomot kapunk, ami S pontjaiban nulla, az origóban pedig nem. Igazolnunk kell, hogy p foka legalább 3n. Ehelyett a következő, általánosabb állítást látjuk be:
a, b, c természetes számok, és legyen

S(a,b,c)={(x,y,z)∣x∈{0,1,...,a},y∈{0,1,...,b},z∈{0,1,...,c},x+y+z>0}.
Ha az f(x,y,z) polinom S(a,b,c) pontjaiban nulla, a (0,0,0) pontban pedig nem, akkor a foka legalább a+b+c.
A bizonyítást az (a+b+c)-re vonatkozó indukcióval végezzük. Ha a+b+c=1, akkor a polinom legalább elsőfokú (azaz nem konstans), hiszen felvesz két különböző értéket. Ha a+b+c>1, akkor tekintsünk egy, a feltételeknek megfelelő f polinomot, a fokát jelölje t. Az a, b, c számok között létezik pozitív, legyen ez például a. Képezzük a g(x,y,z)=f(x+1,y,z)-f(x,y,z) polinomot. A g polinom foka nyilván legfeljebb t; viszont f(x+1,y,z)-ben és f(x,y,z)-ben ugyanazok a megfelelő t-edfokú tagok együtthatói, így ezek kiejtik egymást g-ben. A g foka ezért legfeljebb t-1. A g polinom az S(a-1,b,c) halmaz pontjaiban nulla, az origóban viszont nem nulla; az indukciós feltevés szerint tehát g foka legalább a-1+b+c, amiből t-1≥a-1+b+c, azaz t≥a+b+c következik.