Przeskocz do treści

Delta mi!

Loading

O zastosowaniach Combinatorial Nullstellensatz

Jacek Dymel

o artykule ...

  • Publikacja w Delcie: lipiec 2017
  • Publikacja elektroniczna: 30 czerwca 2017
  • Autor: Jacek Dymel
    Afiliacja: Nauczyciel, V Liceum Ogólnokształcące im. Augusta Witkowskiego w Krakowie
  • Wersja do druku [application/pdf]: (228 KB)

Zadanie 6 z 48. Międzynarodowej Olimpiady Matematycznej (IMO) z 2007 roku było jednym z najtrudniejszych w historii Międzynarodowej Olimpiady Matematycznej.

obrazek

Oto treść zadania.

Zadanie. Niech |n będzie dodatnią liczbą naturalną. Przyjmijmy, że

S = {(x,y,z) x,y,z ∈{0, 1,...,n},x + y +z > 0}

jest zbiorem (n + 1)3 − 1 punktów w przestrzeni trójwymiarowej. Wyznacz najmniejszą możliwą liczbę płaszczyzn, których suma mnogościowa zawiera S, ale do której nie należy (0,0,0).

Zadanie rozwiązało tylko pięciu zawodników: Konstantin Matwiejew z Rosji, Peter Scholze z Niemiec, Danylo Radczenko z Ukrainy, Iurie Boreico z Mołdawii i Pietro Verteci z Włoch. W zasadzie tylko znajomość twierdzenia Combinatorial Nullstellensatz (kombinatoryczne twierdzenie o rozmieszczeniu zer, nawiązujące do twierdzenia Hilberta o zerach), któremu poświęcony jest ten artykuł, umożliwiała szybkie rozwiązanie zadania. Noga Alon opublikował swój artykuł Combinatorial Nullstellensatz [1] w 1999 roku, a już w 2007 roku kilku uczestników IMO stosowało metodę w nim opisaną. Wspomniane twierdzenie jest naturalnym uogólnieniem dobrze znanego uczniom twierdzenia, że wielomian jednej zmiennej stopnia |n o współczynnikach rzeczywistych ma co najwyżej n pierwiastków rzeczywistych, a jego treść jest następująca:

Twierdzenie (Combinatorial Nullstellensatz). Niech |P(x1,x2,...,xn) będzie niezerowym wielomianem |n zmiennych stopnia  n |Pi 1mi, w którym współczynnik przy  m1 mn x | 1 ⋯x n jest różny od zera. Wówczas dla dowolnych zbiorów S1,...,Sn ⊂ R spełniających warunki | Si > mi dla 1 |⩽ i ⩽n, istnieją takie |ci∈Si, że |P(c1,...,cn) ≠ 0.

Dowód. Przeprowadzimy indukcję ze względu na stopień wielomianu |P. Nietrudny dowód początku indukcji (degP = 1) pozostawiam Czytelnikowi Spragnionemu Ćwiczeń jako ćwiczenie.

Załóżmy teraz, że k > 1, oraz że teza zachodzi dla wszystkich wielomianów stopnia niższego niż k. Niech wielomian P ma stopień k. Bez straty ogólności można przyjąć, że |m1 Wybierzmy |a∈ S1. Podobnie, jak w przypadku wielomianów jednej zmiennej, możemy podzielić wielomian |P przez wielomian (x1− a), otrzymując

P (x1,...,xn) = (x1− a)Q(x1,

gdzie R(x2, ...,xn) = P(a, x2,...,xn) jest wielomianem n − 1 zmiennych, natomiast Q musi zawierać nieznikający jednomian postaci xm1 |1 xm22⋯ xmnn oraz |degQ Dla dowodu nie wprost załóżmy, że wielomian P nie spełnia tezy. Wówczas dla dowolnych a ∈ S,...,a ∈S 2 2 n n zachodzi równość P (a,a2,...,an) = 0, co oznacza, że także R(a2, ...,an) = 0.

Wybierzmy teraz dowolnie |a ∈S ∖{a}. 1 1 Otrzymujemy równości:

0 = P(a1,...,an) = (a1 − a)Q(a1,

Ponieważ (a1 −a) ≠ 0 oraz R(a2,...,an) = 0, więc |Q(a1, Wielomian |Q ma stopień k | − 1 i niezerowy współczynnik przy xm1 xm2⋯ xmn 1 2 n oraz przyjmuje wartość zero dla wszystkich a1 ∈S1 ∖{a}, a2∈ S2,..., an ∈Sn, co jest sprzeczne z założeniem indukcyjnym. Uzyskana sprzeczność kończy dowód indukcyjny.


Poniżej przedstawię zastosowania Combinatorial Nullstellensatz do zadań olimpijskich, aby w końcu pokazać rozwiązanie zadania z IMO z 2007 roku, które było pretekstem do opowiedzenia o tej metodzie.

Zadanie (Rosja 2007). W każdy wierzchołek wypukłego |2n-kąta wpisano dwie różne liczby rzeczywiste. Udowodnić, że można z każdego wierzchołka usunąć po jednej liczbie w taki sposób, aby liczby w każdych dwóch sąsiednich wierzchołkach były różne.

Dowód. Niech S (i = 1,...,2n) i będzie dwuelementowym zbiorem liczb wpisanych w i-ty wierzchołek. Określmy wielomian |P(x1,...,xn) == (x1− x2)(x2 −x3)⋯ (x2n− x1). Wielomian |P jest stopnia 2n, współczynnik przy wyrażeniu x1⋯ x2n, które jest stopnia 2n, jest równy |2. Na podstawie Combinatorial Nullstellensatz istnieją |a1∈ S1, |a2∈ S2,..., a2n∈ S2n, takie że P (a1,...,a2n) ≠ 0. To oznacza, że każda z różnic: (a1− a2),(a2− a3),... , |(a2n− a1) jest różna od 0, czyli istnieje taki wybór liczb ze zbiorów |S1,...,S2n, że |a ≠ a ,a ≠ a ,...,a ≠ a . 1 2 2 3 2n 1


Zadanie (5th NIMO Winter Contest 2014). Zdefiniujmy taką funkcję |ξ Z2 Z, że |ξ(n,k) = 1, gdy n ⩽ k oraz ξ(n,k) = −1, gdy |n > k i zdefiniujmy wielomian

 10001000 P (x1,...,x1000) = M ( Q ξ(n,k)xk). n 1 k 1

Wyznacz współczynnik przy |x1⋯x1000 w wielomianie |P.

Rozwiązanie. Zauważmy, że wielomian P jest stopnia |1000. Załóżmy, że współczynnik przy |x1x2⋯ x1000 jest różny od |0. Zdefiniujmy zbiory S1 = S2 =⋅⋅⋅= S1000 = {− 1,1}. Wówczas korzystając z Combinatorial Nullstellensatz, otrzymujemy takie elementy |c ∈S , i i gdzie |i∈{1,...,1000}, że P (c,...,c )≠ 0. 1 1000 Z drugiej strony sumy częściowe C1 definiują pewien "spacer po liczbach całkowitych", kończący się na |C Liczba |C musi być parzysta, dlatego spacer ten w pewnym momencie osiągnie C/2, zatem dla pewnego |k⩽ 1000 zachodzi Ck Oznacza to jednak, że k -ty czynnik w definicji wielomianu P wynosi 0, co przeczy stwierdzeniu |P(c1,...,c1000) ≠0. Zatem współczynnik przy x1x2⋯ x1000 musi być równy 0.


Przejdziemy teraz do rozwiązania przytoczonego na początku artykułu zadania 6 z IMO 2007, które jest trudniejsze niż poprzednie zadania.

Rozwiązanie (Danylo Radczenko). Niech k ∈N+ i k < 3n. Weźmy |k parami różnych płaszczyzn, których suma mnogościowa zawiera zbiór |S i żadna z tych płaszczyzn nie przechodzi przez punkt (0,0,0). Niech |i-ta płaszczyzna będzie określona równaniem aix + biy + ciz = di, gdzie |a2i + b2i + c2i≠ 0 oraz di ≠0. Rozważmy wielomian P postaci

 k n P(x,y,z) = M (aix + biy +ciz− di)− α M (x − j)(y − j)(z− j), i 1 j 1

gdzie α jest tak dobrane, że |P(0,0,0) = 0. Wielomian |P(x,y,z) przyjmuje wartość 0 dla każdego elementu należącego do zbioru |S. Dla |k < 3n współczynnik przy  n n n |x y z nie jest równy 0, gdyż jest równy |α≠ 0. Dla zbiorów S1 = S2 = S3 == {0,1,...,n} zachodzą warunki:  S1 > n, | S2 > n, S3 > n, więc na podstawie Combinatorial Nullstellensatz istnieje taki punkt |(a,b,c)∈ {0,1,...,n}3, że |P(a,b,c) ≠ 0. Zatem istnieje punkt |(a,b,c)∈ S, dla którego P(a, b,c)≠ 0. Otrzymaliśmy sprzeczność. Wobec tego |k ⩾3n.

Wystarczy jeszcze wskazać przykład 3n płaszczyzn, które spełniają warunki zadania. Są nimi

x = 1,x = 2,...,x = n,y = 1,y = 2,...,y = n,z = 1,z = 2,...,z = n. ◻

Powyższe zadanie jest pewną wariacją na temat problemu, jaki postawił Peter Komjáth: ile potrzeba hiperpłaszczyzn, aby pokryć wszystkie, z wyjątkiem jednego, wierzchołki kostki jednostkowej w przestrzeni |n-wymiarowej. Rozwiązanie tego problemu pojawiło się przed 1993 rokiem, ale dopiero Noga Alon i Zoltan Füredi w 1993 roku w pracy [2] przedstawili krótkie i eleganckie rozumowanie. Poniższy dowód pochodzi z pracy [1].

Twierdzenie. Niech |H1, będzie rodziną hiperpłaszczyzn w Rn, których suma zawiera wszystkie, z wyjątkiem jednego, wierzchołki kostki jednostkowej, czyli zbiór |{0,1}n. Wówczas |m

Dowód. Bez straty ogólności możemy przyjąć, że usuniętym wierzchołkiem jest punkt (0,...,0). Niech hiperpłaszczyzna Hi dana będzie równaniem ⟨ai,x⟩= bi, gdzie x = (x1,...,xn) i ⟨a, b⟩ jest standardowym iloczynem skalarnym |a i b. Dla każdego |i∈{1,...,m} zachodzi warunek |bi≠ 0, gdyż żadna z hiperpłaszczyzn nie przechodzi przez punkt |(0,...,0). Załóżmy dla dowodu nie wprost, że |m i zdefiniujmy wielomian

 m n m P (x) = (−1)n+m+1M b jM (xi− 1)+ M (⟨ ai,x⟩ − bi). j 1 i 1 i 1

Wielomian |P ma stopień n i współczynnik przy x1⋯ xn równy

 m (−1)n+m+1M b j, j 1

zatem różny od 0. Na podstawie Combinatorial Nullstellensatz dla |m1 oraz |S1 = ... = Sn = {0,1}, istnieje taki punkt |c∈ {0,1}n, że P (c)≠ 0. Punkt |c jest różny od |(0,...,0), gdyż wielomian |P przyjmuje wartość 0 dla x = (0,...,0), a zatem punkt |c należy do zadanego zbioru i nie należy do żadnej z hiperpłaszczyzn. Otrzymaliśmy sprzeczność, wobec tego m Teraz wystarczy wskazać |n hiperpłaszczyzn spełniających warunki zadania; są one zadane równaniami x1 = 1,...,xn = 1.


obrazek

Mam nadzieję, że powyższe przykłady przekonały Cię, Drogi Czytelniku, o użyteczności Combinatorial Nullstellensatz w rozwiązywaniu problemów z pozoru z nim niezwiązanych. Na zakończenie chciałbym zauważyć, że to wspaniałe twierdzenie jest słuszne dla wielomianów o współczynnikach z dowolnego ciała. Dotychczas używaliśmy jedynie ciała liczb rzeczywistych. Drugim w kolejności naturalnym wyborem ciała jest ciało |Zp - ciało reszt z dzielenia przez liczbę pierwszą p z dodawaniem i mnożeniem modulo |p. Zastosowanie Combinatorial Nullstellensatz w tej sytuacji prowadzi do niezwykle eleganckich dowodów bardzo pięknych twierdzeń z teorii liczb. Niestety, w tym artykule brakuje już miejsca na przedstawienie przykładów, obiecuję jednak zaprezentować je w numerze wrześniowym w nadziei, że oczekiwanie zaostrzy apetyt nie tylko Czytelnika Bardzo Zainteresowanego.


Do czytania
[1]
N. Alon: Combinatorial Nullstellensatz, Combinatorics Probability and Computing 8 (1999), 7-29.
[2]
N. Alon, Z. Füredi, Covering the cube by affine hyperplanes, European Journal of Combinatorics 14 (1993), 79-83.
[3]
M. Michałek: A short proof of Combinatorial Nullstellensatz, American Mathematical Monthly 117 (2010), 821-823.