luty 2022

Data ostatniej modyfikacji:
2022-07-11

Zad. 1. Niech f:ℕ→ℕ będzie dowolną bijekcją, czyli funkcją różnowartościową i "na" (przyjmujemy, że 0 jest liczbą naturalną). Wykaż, że wówczas istnieją liczby naturalne a < b < c, dla których f(a) + f(c) = 2f(b).

Zad. 2. Na płaszczyźnie leży k prostych, z których żadne dwie nie są równoległe i żadne trzy nie przecinają się w jednym punkcie. Dla jakich wartości k możemy ponumerować punkty przecięcia prostych liczbami 1, 2, ..., k–1 (możemy używać tej samej liczby wielokrotnie, ale każdy punkt może mieć tylko jedną etykietę) tak, aby na każdej z prostych pojawiły się wszystkie numery?

Zad. 3. Niech P(x1, x2,..., xn) jest wielomianem n zmiennych. Jeżeli za każdą zezmiennych xi podstawimy 1 lub -1, to liczba P(x1,x2,..., xn) będzie dodatnia, jeżeli zmiennych, za które podstawiliśmy liczbę -1 będzie parzyście wiele, a ujemna w przeciwnym wypadku. Wykaż, że P jest wielomianem stopnia co najmniej n, tzn. zawiera składnik w którym suma potęg przy zmiennych jest równa co najmniej n.
Na przykład Q(x, y, z) = x3yz2 + x2y3 + xyz2 jest wielomianem stopnia 6, ponieważ zawiera składnik x3yz2, w którym suma potęg przy zmiennych jest równa 6, a suma potęg każdego innego składnika jest niewiększa niż 6. https://mathworld.wolfram.com/MultivariatePolynomial.html

 

Wyniki: 

Za rozwiązania zadań lutowych 20 pkt. zdobył Radosław Górzyński - I LO Lubin.

 

Odpowiedzi: 

Zad. 1. Weźmy a = 0 i niech b będzie najmniejszą liczbą dla której f(b) > f(a). Niech c będzie liczbą, dla której f(c) = 2f(b)–f(a) = f(b)+(f(b)–f(a)) > f(b) > f(a). Ponieważ f(c) > f(a), c ≥ b z definicji b. Równość nie może zachodzić, bo f(c) > f(b).

Zad. 2. Załóżmy, że numeracja z zadania istnieje. Wtedy na każdej prostej leży dokładnie jeden punkt (przecięcia) o numerze 1, a każdy punkt o numerze 1 leży na dwóch prostych. Takich punktów jest zatem k/2, więc k musi być liczbą parzystą. Dla k parzystego taką numerację można skonstruować w następujący sposób: Umieśćmy liczby 1, 2, ..., k–1 w wierzchołkach k–1 -kąta foremnego, a liczbę k w jego środku. Niech ℓ1, ℓ2, ..., ℓk będą prostymi z zadania. Dla m = 1, 2, ..., k–1 punktowi przecięcia prostych ℓm i ℓk przypisujemy numer m. Jeżeli i, j < k, to punktowi przecięcia prostych ℓi, ℓj przypisujemy liczbę m taką, że odcinek łączący m i k jest prostopadły do przekątnej wielokąta o końcach i, j. Wszystkie oczekiwane własności numeracji wynikają z tej konstrukcji. Uwaga. Poprawną numerację otrzymamy niezależnie od tego, w jakiej kolejności umieścimy liczby na wierzchołkach wielokąta.

Zad. 3. Zastosujemy indukcję względem n, aby pokazać, że każdy taki wielomian zawiera składnik, w którym występują wszystkie zmienne xi (podzielny przez x1x2...xn). Niech
Q(x1, x2, ..., xn) = 1/2·(P(x1, x2, ... ,xn) – P(x1, x2, ..., -xn)), czyli Q to suma wszystkich składników P, w których xn występuje w nieparzystej potędze. Rozważmy wielomian
T(x1, x2, ..., xn–1) = Q(x1, x2, ..., xn–1, 1). Jeżeli za każdą ze zmiennych x1, x2, ..., xn–1 podstawimy 1 lub -1, przy czym -1 podstawimy za parzyście wiele zmiennych, to obie liczby P(x1, x2, ..., xn–1, 1) oraz -P(x1, x2, ..., xn-1, -1) będą dodatnie, więc liczba T(x1, x2, ..., xn–1) też będzie dodatnia. Analogicznie, gdy -1 podstawimy za nieparzyście wiele zmiennych, to liczba T(x1, x2, ..., xn–1) będzie ujemna. Wobec tego na mocy założenia indukcyjnego T(x1, x2, ..., xn–1) ma składnik podzielny przez x1x2...xn–1, więc Q też. We wszystkich składnikach Q zmienna xn występuje w nieparzystej potędze, więc Q zawiera składnik podzielny przez x1x2...xn, co kończy krok indukcyjny.

 

Powrót na górę strony