Pi_{}eciogodzinówka, dzień czwarty

luty 2005

10. Rozstrzygn _{}ać, czy istnieje funkcja f : ℤ^{+} → ℤ^{+} taka, że dla każdego n ∈ ℤ^{+} zachodzi f(f(n)) = n + 1.

Rozwi _{}azanie. Nie istnieje taka funkcja. Wykażemy to zadania nie wprost. Przypuśćmy, że istnieje taka funkcja f. Niech f(1) = k. Wtedy f(l + 1) = l + k. Można to wykazać indukcyjnie. Dla n = 0 zachodzi. Niech f(n + 1) = n + k, wykaże, że f(n + 2) = n + k + 1. Mamy f(n + 2) = f(f(f(n + 1))) = f(f(n + k)) = n + k + 1. Stosujemy wi_{}ec lemat do n = k − 1 i mamy, że f(k) = f(1 + k − 1) = k +k −1 = 2k −1. Jednocześnie f(k) = f(f(1)) = 2. A zatem musi być 2k −1 = 2, co prowadzi do sprzności z założeniem, że k ∈ ℤ^{+} . ■

11. Odcinek AD jest wysokości _{}a trójk _{}ata ostrok _{}atnego nierównoramiennego ABC. Punkty E i F s _{}a odpowiednio rzutami punktu D na odcinki AB i AC. Proste EF i BC przecinaj _{}a si_{}e w punkcie K. Punkt L jest punktem środkowosymetrycznym do A wzgl_{}edem środka okr_{}egu opisanego na trójk _{}acie ABC. Wykazać, że DL ⊥ AK.

Rozwi _{}azanie. Zauważmy, iż na czworok _{}acie AEDF da si_{}e opisać okr _{}ag i AD jest jego średnic _{}a, jest on styczny do prostej BC. Okr_{}egi o średnicach BD i CD s _{}a styczne do prostej AD i do siebie. Wobec tego, z pot_{}egi punktu A wzgl_{}edem nich wynika AE · AB = AD^{2} = AF · AC, wobec tego na czworok _{}acie BCF E da si_{}e opisać okr _{}ag. Niech M b_{}edzie drugim przeci_{}eciem okr_{}egu o średnicy AD z prost _{}a AK. Z pot_{}egi punktu K wzgl_{}edem obu ostatnich okr_{}egów mamy KM · KA = KE · KF = KB · KC, wi_{}ec na czworok _{}acie AMBC da si_{}e opisać okr _{}ag i jest to okr _{}ag opisany na trójk _{}acie ABC. Skoro M należał do okr_{}egu o średnicy AD, to ∡AMD = \frac{π}{2}. Przedłużmy prost _{}a MD do przeci_{}ecia z okr_{}egiem opisanym na ABC, niech to b_{}edzie punkt N. Skoro k _{}at AMD był prosty, to AN jest średnic _{}a okr_{}egu opisanego na trójk _{}acie ABC, czyli N = E. Ale DM ⊥ AK, co należało dowieść. ■

12. Podziałem zbioru nazywamy dowolny zbiór jego parami rozł _{}acznych podzbiorów, sumuj _{}acych si_{}e do całego zbioru. Dla dowolnego podziału p przez p(x) oznaczamy liczb_{}e elementów tego elementu podziału, do którego należy x. Pokazać, że dla dowolnych podziałów p i q zbioru {1, 2, …, 9} istniej _{}a takie x i y, że p(x) = p(y) i q(x) = q(y).

Rozwi _{}azanie. Zauważmy, iż relacja p(x) = p(y) jest relacj _{}a równoważności na {1, 2, …, 9} i wyznacza jakiś podział tego zbioru p′, analogicznie q′. Podział p′ składa si_{}e z maksymalnie trzech podzbiorów, bo w podziale p mogły istnieć co najwyżej trzy różne liczności zbiorów, bo jeśli istniały cztery a < b < c < d, to a + b + c + d 1 + 2 + 3 + 4 = 10 > 9, sprzeczność. Czyli p′ i q′ to podziały {1, 2, …, 9} na co najwyżej trzy zbiory. Skupmy si_{}e na podzbiorze mocy 3 w p′, jeśli taki istnieje. Mógł on powstać z jednego zbioru mocy 3 w p lub z trzech mocy 1, s _{}a tylko dwie możliwości. Czyli podział p′nie może si_{}e składać z trzech trzyelementowych zbiorów (bo każdy zbiór odpowiada jednej wartości p(x)). Czyli istnieje w nim zbiór przynajmniej czteroelementowy. Czyli dwa elementy z niego należ _{}a do tego samego zbioru w q′, bo q′ też ma co najwyżej trzy zbiory. Czyli te dwa elementy leż _{}a w tych samych klasach abstrakcji w obu podziałach p′ i q′, c.k.d. ■