marzec 2022

Zad. 1. Każdy równoległobok jest wyznaczony przez dwie pary prostych, z których każda para jest równoległa do jednego z boków trójkąta, wobec tego liczba równoległoboków jest trzykrotnością liczby równoległoboków wyznaczonych przez proste równoległe do dwóch ustalonych boków trójkąta ABC. Oznaczmy tę liczbę przez T_n. Mamy T₁ = 0, T₂ = 1. Jeżeli w sytuacji z zadania usuniemy z rysunku wszystkie równoległoboki mające wierzchołek na jednym z boków trójkąta (np. AB dla ustalenia uwagi), to otrzymamy sytuację analogiczną z podziałem boków trójkąta na n–1 równych części i narysowaniu prostych równoległych do jego boków. Liczba równoległoboków o krawędziach równoległych do prostych AC lub BC zmniejszyła się o 1·(n–1) + 2·(n–2) + ... + (n–1)·1 = B(n+1, 3), gdzie B(n, k) to symbol dwumianowy Newtona. Otrzymaliśmy zależność rekurencyjną T_n = T_n–1 + B(n+1, 3), z której wynika jawny wzór na T_n, mianowicie T_n = B(n+1, 3) + B(n, 3) + ... + B(3, 3) = B(n+2, 4) (to tzw. twierdzenie o haku: https://en.wikipedia.org/wiki/Hockey-stick_identity). Liczba wszystkich równoległoboków wewnątrz trójkąta ABC jest więc równa 3T_n = 3 B(n+2, 4).

Zad. 2. Rozważmy graf, którego wierzchołki odpowiadają punktom P_i. Krawędź między dwoma wierzchołkami istnieje wówczas, gdy kąt wpisany oparty na łuku o końcach w punktach odpowiadającym tym dwóm wierzchołkom ma miarę większą od 120°. Taki graf ma 21 wierzchołków i nie zawiera żadnych trójkątów, więc z twierdzenia Turana (https://mathworld.wolfram.com/TuransTheorem.html) ma co najwyżej 110 krawędzi. Ponieważ wszystkich łuków P_iP_j jest B(21, 2) = 210, musi istnieć przynajmniej 210–110 = 100 łuków spełniających warunki zadania.

Zad. 3. Zaczniemy od pokazania, że równanie nie ma pierwiastków, gdy p jest liczbą nieparzystą. Bez straty ogólności możemy przyjąć, że x i y są względnie pierwsze, tzn. ich wspólnym dzielnikiem większym od 1 może być jedynie p, a podzielenie przez p dałoby inne rozwiązanie równania. Zauważmy, że x^p + y^p = (x+y)(x^p–1 + x^p–2y + ... + y^p–1). Ten drugi nawias przystaje do px^p–1 modulo x+y. Zauważmy, że ponieważ x i y są względnie pierwsze, a iloczyn wyrażeń w nawiasach jest potęgą p, wyrażenie w jednym z nawiasów musi być równe 1 (sprawdź to). Równość x+y = 1 nie może zachodzić, bo obie liczby są dodatnie, a równość x^p + y^p = x + y prowadzi do x=y=1, co daje sprzeczność z nieparzystością p. Rozważmy teraz równanie dla p=2. Pokażemy, że jedyne jego rozwiązania są postaci (2^k)² + (2^k)² = 2^2k+1. Zapiszmy x=ad, y=bd, gdzie liczby a i b są względnie pierwsze. Liczba d musi być potęgą dwójki. Równość a=b=1 daje rozwiązania jak podano wyżej. W przeciwnym wypadku a²+b² musi być podzielne przez 4, co jest możliwe tylko wtedy, gdy obie liczby są parzyste, a to daje sprzeczność ze względną pierwszością a i b.