Rozwi _{}azania

1. (by Robert Pałuba) Wykażemy, że wszystkie liczby postaci n^{4} + 4k^{4} dla k 2 s _{}a złożone. Zauważmy, że:

n^{4} + 4k^{4} = (n^{2} + 2kn + 2k^{2})(n^{2} − 2kn + 2k^{2})

Zatem rzeczywiście liczba n^{4} + 4k^{4} jest złożona, bo jest iloczynem dwóch liczb równych co najmniej 4, bo n^{2} + 2kn + 2k^{2} k^{2} 4 i n^{2} − 2kn + 2k^{2} = (n − k)^{2} + k^{2} k^{2} 4.

Wynika z tego, że wszystkie m postaci 4k^{4} dla k 2 spełniaj _{}a warunki zadania.

2. (by Olek Gajewski) Przypadek przek _{}atnych prostopadłych jest oczywisty (F = G = E).

W przeciwnym wypadku: Oznaczmy przez k prost _{}a prostopadł _{}a do AB przechodz _{}ac _{}a przez E. Wystarczy pokazać, że proste CF i DG oraz k przecinaj _{}a si_{}e w jednym punkcie (np. X) - bo wówczas w analogiczny sposób pokażemy, że BF, AG i k przecinaj _{}a sie w Y - a zatem otrzymamy równoległobok XGY F i zajdzie teza, gdyż przek _{}atne równoległoboku przecinaj _{}a si_{}e w połowie.

Na pocz _{}atek oznaczmy poprzez X przeci_{}ecie DG i k. Poprowadźmy prost _{}a l równoległ _{}a do AB przez X.

Udowodnienie tezy zadania sprowadza si _{}a do udowodnienia faktu:

Dla trójk _{}ata ABC i spodku wysokości H (spuszczonej z C); proste przechodz _{}ace przez H prostopadłe do odpowiednio BC, AC przecinaj _{}a odpowiednio AC i BC w punktach P i Q, takich, że P Q||AB.

Bo wtedy lemat ten stosujemy do trójk _{}ata wyci_{}etego z k _{}ata ZEB przez prost _{}a l oraz spodka wysokości X - i wtedy C i D to nasze domniemane punkty P i Q.

Dowód faktu:

Rozwi _{}azanie przeprowadzimy, zakładaj _{}ac, że k _{}at ACB jest rozwarty i punkty P, Q wówczas leż _{}a bliżej punktu C niż A i B odpowiednio - w przeciwnym razie rozwi _{}azanie jest analogiczne. Oznaczmy:

• E = HP ∩ BC,

• F = HQ ∩ AC,

• ∠BAC = α,

• ∠ABC = β

1. Na CF HE można opisać okr _{}ag - gdyż ∠HF C = ∠HEC = 90.

2. Zachodz _{}a nast_{}epuj _{}ace równości k _{}atów:

• ∠BAC = ∠F HC = ∠F EC = ∠F EQ,

• ∠ABC = ∠EHC,

• ∠AP H = ∠BQF = 90^{∘} − α − β (bo suma k _{}atów w trójk _{}acie wynosi 180^{∘})

Zatem na czworok _{}acie P QF E można opisać okr _{}ag - a zatem ∠QP F = ∠F EQ = ∠BAC Czyli proste AB i P Q s _{}a równoległe - CBDU.

3. (by Michał Pilipczuk)

Zauważmy, że jeśli w zapisie binarnym liczby na końcu wyst_{}epuje 00 lub 11, to funkcja ignoruje to i przyporz _{}adkowuje tak _{}a sam _{}a wartość, jakby tej końcówki nie było. Natomiast jeśli wyst_{}epuje 10 lub 01 to odpowiednio dodaje lub odejmuje 1. Zauważmy, że dodawanie 1 wyst_{}epuje, gdy mamy jedynk_{}e na miejscach o pewnej parzystości, zaś odejmowanie, gdy mamy na tej drugiej. Zatem funkcja po prostu zlicza różnic_{}e liczb jedynek w liczbie na miejscach o różnych parzystościach. Liczby x, dla których f(x) = 0 maj _{}a zatem równ _{}a liczb_{}e jedynek na miejscach parzystych i nieparzystych (jakkolwiek to liczyć).Zatem liczba x z przedziału od 0 do 2^{2n} − 1 ma n miejsc parzystych i n nieparzystych. Zakładaj _{}ac, że na każdym z nich ma być k jedynek, liczba możliwości b_{}edzie równa \binom{n}{k} ^{2} bo z każdego z dwóch zbiorów n miejsc wybieram k na których b_{}ed _{}a jedynki. Musimy zatem przesumować po k: nasz wynik b_{}edzie równy S = ∑ _{i=0}^{n} \binom{n}{k} ^{2}. Ale \binom{n}{k} = \binom{n}{n−k}, wi_{}ec S = ∑ _{i=0}^{n} \binom{n}{k} \binom{n}{n−k}. Rozpatrzmy zatem dwa zbiory n elementów: z jednego wybieramy k a z drugiego n − k elementów. Równie dobrze moglibyśmy z sumy tych dwóch zbiorów wybrać n elementów i jednoznacznie podzielić je na k z pierwszego zbioru i n − k z drugiego a tych wyborów jest \binom{2n}{n}. Wi_{}ec S = ∑ _{i=0}^{n} \binom{n}{k} ^{2} = \binom{2n}{n}, wi_{}ec taki jest wynik naszego zadania.

4. (by Łukasz Mazurek)

a + b + c + d = 0
ab + ac + ad + bc + bd + cd = p

\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} = \frac{abc + bcd + cda + dab}{abcd} = 0 ⇔ abc + bcd + cda + dab = 0

abcd = 1

Znaj _{}ac wzory Viete’a rozważmy wielomian pomocniczy:

W (x) = (x − a)(x − b)(x − c)(x − d) = x^{4} + 0x^{3} + px^{2} + 0x + 1 = x^{4} + px^{2} + 1

= (x^{2} − \frac{−p − \sqrt{p^{2} − 4}}{2} )(x^{2} − \frac{−p + \sqrt{p^{2} − 4}}{2} )

Żeby wielomian ten miał 4 rzeczywiste pierwiastki a, b, c, d, wyrażenia pod znakiem pierwiastka musz _{}a być nieujemne, wi_{}ec musi być:

p^{2} − 4 0

|p| 2 5. (by Łukasz Mazurek) Niech x + y = AB, y + z = BC, z + x = CA, a r b_{}edzie promieniem okr_{}egu wpisanego w

trójk _{}at ABC. Przyrównuj _{}ac wzory �pr” i �Herona” na pole trójk _{}ata ABC otrzymujemy:

(x + y + z)r = \sqrt{(x + y + z)xyz}

r = \sqrt{\frac{xyz}{x + y + z}}

Odcinek IM policzymy z tw. Pitagorasa dla trójk _{}ata stworzonego m.in. przez promień okr_{}egu wpisanego poprowadzony do AB:

IM = \sqrt{r^{2} + ( \frac{x − y}{2} ) ^{2}} = \sqrt{\frac{xyz}{x + y + z} + \frac{(x − y)^{2}}{4}}

Zadanie sprowadza si_{}e wi_{}ec do udowodnienia nierównośći:

\sqrt{\frac{4xyz}{x + y + z} + (x − y)^{2}} (x + y)\sqrt{1 − \frac{2(x + y)}{2(x + y + z)}}

dla dodatnich x, y, z. Nic prostszego. Obie strony s _{}a dodatnie, wi_{}ec mogę podnieść je do kwadratu i udowodnić, że różnica lewej i prawej jest nie mniejsza od zera:

\frac{4xyz}{x + y + z} + (x − y)^{2} − (x + y)^{2} ( 1 − \frac{x + y}{x + y + z} ) =

= \frac{4xyz + (x + y + z)(x − y)^{2}}{x + y + z} − (x + y)^{2} ( \frac{z}{x + y + z} ) =

= \frac{4xyz + (x + y)(x − y)^{2} + z(x − y)^{2} − z(x + y)^{2}}{x + y + z} =

= \frac{4xyz + (x + y)(x − y)^{2} + z(−4xy)}{x + y + z} =

= \frac{(x + y)(x − y)^{2}}{x + y + z} 0

6. (by Michał Pilipczuk)

Niech graf z zadania b_{}edzie uporz _{}adkowan _{}a par _{}a zbiorów wierzchołków i kraw_{}edzi (V, E). Dla każdej uporz _{}adkowanej pary s, p ∈ V ∪ {−1} poł _{}aczonej kraw_{}edzi _{}a zdefiniujmy rekurencyjnie operacje DF S(s, p):

• Przyporz _{}adkowuje kraw_{}edzi pomi_{}edzy s i p kolejny numerek (zaznaczam jej czas przejścia).

• Jeśli odwiedziłem już wierzchołek p, to kończ_{}e.

• W przeciwnym razie odpalam po kolei dla każdego wierzchołka r, który jest s _{}asiadem p i takim, że s ≠ r DFS(p,r), jeśli kraw_{}edź pomi_{}edzy p i r nie została jeszcze ponumerowana.

Dla dowolnego v ∈ V odpalamy DF S(−1, v). Pokażemy, że powstała w ten sposób numeracja spełnia własności zadania. Po pierwsze, ponieważ graf jest spójny, to DF S przejdzie każd _{}a kraw_{}edź, wi_{}ec wszystkie zostan _{}a ponumerowane i każda dokładnie jeden raz. Po drugie, z wierzchołka v wychodzi kraw_{}edź o numerze 1, wi_{}ec na pewno NW D kraw_{}edzi zeń wychodz _{}acych b_{}edzie równe 1. Po trzecie rozpatrzmy dowolny w ∈ V różny od v i moment w którym po raz pierwszy do niego wchodzimy. Wówczas numeruj_{}e kraw_{}edź któr _{}a doszedłem doń pewnym l. Nast_{}epnie zauważmy, że żadna z pozostałych kraw_{}edzi dochodz _{}acych do w nie została jeszcze ponumerowana (gdyż w przeciwnym wypadku ten wierzchołek b_{}edzie już odwiedzony), wi_{}ec odpal_{}e DF S dla co najmniej jednego jeszcze s _{}asiada w, bo stopień w to co najmniej 2 i jej nadam numer l + 1. Wi_{}ec wśród kraw_{}edzi wychodz _{}acych z w s _{}a dwie kraw_{}edzie o numerach l i l + 1, a te s _{}a na pewno wzgl_{}ednie pierwsze. Zatem dla każdego w NW D kraw_{}edzi zeń wychodz _{}acy b_{}edzie równe 1. Zatem pokazaliśmy algorytm konstruuj _{}acy numeracj_{}e szukan _{}a w zadaniu, wi_{}ec ona istnieje.