Rozwi _{}azania

1.

Odpowiedź: nie, nie istnieje takie n. Dowód: Założmy, że istnieje takie n i ci _{}ag liczb pierwszych p_{1}, p_{2}, …, p_{n}, że _{\frac{n}{\frac{1}{p_{1}} + \frac{1}{p_{2}} +...+ \frac{1}{pn}}} jest całkowite.

Wówczas zauważmy, że:

\frac{n}{\frac{1}{p_{1}} + \frac{1}{p_{2}} + … + \frac{1}{p_{n}}} = \frac{np_{1}p_{2}p_{3} …p_{n−1} p_{n}}{p_{2}p_{3}p_{4} …p_{n−1} p_{n} + p_{1}p_{3}p_{4} …p_{n−1} p_{n} + … + p_{1}p_{2} …p_{n−1}}

Zatem ta liczba po prawej ma być całkowita. Zauważm, że dla każdego p_{i} w mianowniku wszystkie wyrazy oprócz jednego s _{}a podzielne przez p_{i} - oprócz tego w którym si_{}e to p_{i} skróciło, gdyż liczby z naszego ci _{}agu s _{}a parami różne. Zatem dla każdego p_{i} mianownik jest sum _{}a wyrazów podzielnych przez p_{i} i jednego niepodzielnego, wi_{}ec jest on niepodzielny. Zatem cały mianownik, który jest wi_{}ekszy od 1, bo n 2, musi si_{}e skrócić z n. Ale mianownik składa si_{}e z n składników, z których każdy jest iloczynem przynajmniej jednej liczby pierwszej, wi_{}ec każdy jest równy przynajmniej 2, wi_{}ec cały mianownik to przynajmniej 2n, zatem licznik nie skróci całego mianownika, wi_{}ec liczba nie mogła być całkowita. Uzyskaliśmy wi_{}ec sprzeczność, co dowodzi postawionej przez nas tezy.

Pokażemy, że w sześciok _{}acie ABCDEF dwusieczne wszyskich k _{}atów przetn _{}a si_{}e w jednym punkcie, wówczas punkt ten b_{}edzie równoodległy od każdej pary kolejnych boków, wi_{}ec b_{}edzie środkiem okr_{}egu wpisanego. Rozpatrzmy dwusieczne k _{}atów B, D, F. Jako, że trójk _{}aty ABC,CDE,EF A s _{}a równoramienne, to dwusieczne te s _{}a zarazem symetralnymi odcinków AC,CE,EA, wi_{}ec przecinaj _{}a si_{}e w punkcie I - środku okr_{}egu opisanego na trójk _{}acie ACE. Pokażemy, że dwusieczna k _{}ata przy wierzchołku A również przechodzi przez punkt I, czyli, że AI jest dwusieczn _{}a k _{}ata przy A. Oznaczmy ∠BCD = ∠DEF = ∠F AB = ζ, ∠BAC = ∠ACB = γ, ∠DCE = ∠CED = β, ∠F EA = ∠EAF = α. Wówczas z k _{}ata środkowego i wpisanego ∠AIE = 2∠ACE = 2(ζ −γ −β) = 2ζ −2γ −2β. Ponieważ trójk _{}at AIE jest równoramienny, to ∠IAE = 90^{∘}− \frac{1}{2}∠AIE = 90^{∘}− ζ + β + γ. Zatem ∠F AI = α + ∠AIE = 90^{∘}− ζ + α + β + γ. Zauważmy, że skoro w wyniku k _{}aty α, β, γ spełniaj _{}a symetryczne role, to analogicznie wyliczaj _{}ac k _{}at ∠BAI również uzyskamy ten sam wynik, wi_{}ec AI dzieli k _{}at przy wierzchołku A na równe cz_{}eści. Zatem analogicznie rozumuj _{}ac dla wierzchołków C i E mamy, że wszystkie dwusieczne przetn _{}a si_{}e w punkcie I, jest on zatem środkiem okr_{}egu wpisanego w sześciok _{}at.

Przeprowadzimy dowód indukcyjny po n. Krok 1 jest oczywisty - dla 4 gości (bo niżej założenie nie może być spełnione) każdy zna każdego, wi_{}ec wszyscy si_{}e znaj _{}a, istnieje wi_{}ec w grafie znajomości cykl długości 4. Teraz założmy, że mamy n znajomych uporz _{}adkowanych w taki graf i wiemy, że dla każdego q < n teza indukcyjna zachodzi. Założmy przeciwnie, że w grafie nie ma cyklu długości niepodzielnej przez 3. Zauważmy najpierw, że graf musi być spójny, gdyż w przeciwnym razie z założenia indukcyjnego w każdej spójnej składowej musiałby istnieć interesuj _{}acy nas cykl, wi_{}ec byłaby sprzeczność. Weźmy wi_{}ec w naszym grafie dowolny cykl (istnieje, gdyż w przeciwnym razie w grafie musiałyby istnieć wierzchołki o stopniu 1, a wszystkie maj _{}a stopień 3) i nazwijmy go K. Oczywiście długość K jest podzielna przez 3, wi_{}ec podzielmy wierzchołki K na 3 podzbiory A, B, C, które odpowiadaj _{}a kolejno co trzecim wieżzchołkom w cyklu K. Teraz udowodnijmy mały lemacik: jeśli dwa cykle maj _{}a wspóln _{}a ścieżk_{}e (i to jest cała ich cz_{}eśc wspólna), to długość tej ścieżki jest podzielna przez 3. Niech a, b, s to odpowiednio długości cykli i ścieżki. Wówczas możemy skonstruować cykl w postaci kawałków cykli, które nie należ _{}a do ścieżki i b_{}edzie miał on długość a + b − 2s, wieć jeśli a, b jest podzielne przez 3 zaś s nie, to uzyskaliśmy cykl długości niepodzielnej przez 3. Z tego lematu od razu nam wynika, że nie ma poł _{}aczenia mi_{}edzy żadnymi dwoma wierzchołkami z cyklu K (bo byłaby to ścieżka długości 1). Wi_{}ec skoro stopnie wierzchołków z K s _{}a równe 3, to istnieje niepusty zbiór U wierzchołków spoza K. A świstak na to niemożliwe. Weżmy pewne u ∈ U. Załóżmy, że istniej _{}a zeń dwie ścieżki, z których jedna dochodzi do cyklu K w wierzchołku należ _{}acym do zbioru A: a, a druga w wierzchołku należ _{}acym do B: b (jest to pierwsze zetkni_{}ecie tych ścieżek z cyklem K). Niech p b_{}edzie ostatnim wspólnym wierzchołkiem na tych ścieżkach licz _{}ac od u. Wówczas mamy dwa cykle: K i cykl złożony z dwóch kawałków sćieżek z u, ale rozpoczynaj _{}acych si_{}e w p i konćz _{}acych si_{}e odpowiednio w a i b oraz kawałku mie”dzy a i b. Ponieważ założyliśmy, że a i b należ _{}a do żożnych podzbiorów z A, B, C to długość ścieżki z a do b po cyklu K jest niepodzielna przez 3, wi_{}ec z lematu mamy sprzeczność. Zatem zbiór U mog_{}e podzielić na 3 podzbiory X, Y, Z, które odpowiadaj _{}a wierzchołkom z których ścieżki dochodz _{}a do cyklu K w wierzchołkach należ _{}acych do A, B, C. Zauważmy, że skoro A, B, C były niepuste to i X, Y, Z s _{}a niepuste, bo należ _{}a do nich chociażby trzeci s _{}asiedzi wierzchołków z A, B, C. Nich k = 3l b_{}edzie liczb _{}a wierzchołkoów z K. Bez szkody na ogólności mog_{}e założyć, że X ma najmniejsz _{}a moc z A, B, C, wi_{}ec |X| \frac{(n−k)}{3} = \frac{n}{3} − l. Jednocześnie kraw_{}edzie pomiedzy zbiorem X a cyklem K s _{}a trzecimi kraw_{}edziami wychodz _{}acymi z wierzchołków należ _{}acych do A. Niech X′= X ∪ A plus kraw_{}edzie mi_{}edzy wierzchołkami z X′, wi_{}ec mamy podgraf całego grafu G o mocy co najwyżej \frac{n}{3} − l + l = \frac{n}{3}. Teraz b_{}ed_{}e chciał z tego podgrafu zrobić graf o liczbie wierzchołków mniejszej niż n i który spełnia założenie o stopniu wierzchołków 3. Wiemy, że to założenie spełniaj _{}a już wszystkie wierzchołki z X (bo pomi_{}edzy X a Y i Z nie może być kraw_{}edzi), a nie spełniaj _{}a te z A, bo ich stopień to za każdym razem 1 (to trzecie poł _{}aczenie z wierzchołkiem z X). Aby zatem to zrobić b_{}edziemy zlepiali kolejne wierzchołki z A po trzy w p_{}eczku aby uzyskać nowe wieżzchołki o stopniu 3 (zlepiamy po kolei jad _{}ac wzdłuż cyklu K). W załeżności od reszty z dzielenia przez 3 l-a zostanie nam 0, 1 lub 2 wierzchołki. Jeśli 0 to nie ma problemu, mamy graf o liczbe wierzchołków co najwyżej \frac{n}{3}, bo zlepianie zabiera nam wierzchołki. Litwo, ojczyzno moja, ty jesteś jak zdrowie... Jeśli 1 to wykonujemy nast_{}epuj _{}acy manewr: bierzemy cały graf, który jak na razie skonstruowaliśmy oprócz niezgrupowanego wierzchołka i kraw_{}edzi do niego i odbijamy symetrycznie. Nast_{}epnie dwa uzyskane wierzchołki o stopniu 2 (te poł _{}aczone z wyrzuconym wierzchołkiem) ł _{}aczymy ze sob _{}a i założenie o stopniu każdego wierzchołka 3 jest spełnione zaŚ liczba wierzchołków całego skonstruowanego grafu jest co najwyżej \frac{2}{3}n. Jeśli zaś mamy reszt_{}e 2, to podł _{}aczamy te dwa wierzchołki w 1 wierzchołek, odbijamy cały konstruowany graf i podł _{}aczemy kraw_{}edzi _{}a dwa wierzchołki o stopniu 2- i mamy szukany graf o liczbie wierzchołków co najwyżej \frac{2}{3}n. Niech skonstruowany graf to b_{}edzie graf R. Z założenia indukcyjnego bierzemy w grafie R cykl S o długości niepodzielnej przez 3. Zauważmy, że skoro pomi_{}edzy odbitymi cz_{}eściami grafu (jeśli w ogóle odbijaliśmy), była tylko jedna kraw_{}edź, to cykl S musi należeć w całości do jednej z symetrycznych cz_{}eści, wi_{}ec w każdej jest symetryczny cykl S. Weźmy wi_{}ec cykl S należ _{}acy do tej rzeczywistej, czyli nieodbitej cz_{}eści. Jeśli cykl przechodzi przez wierzchołek powstały w wyniku sklejenia to w oryginalnym grafie G to sklejenie mog_{}e zast _{}apić poprzez przejście po ścieżce pomiedzy dwoma z wierzchołków sklejonych (tej krótszej ścieżce, aby ścieżki si_{}e nie pokrywały), a ponieważ wszystkie sklejane wierzchołki należ _{}a do zbioru A, to te wszystkie ścieżki maj _{}a długość podzieln _{}a przez 3, wi_{}ec dolepienie każdej nie zmieni faktu, że cykl S z dolepionymi ścieżkami ma długość niepodzieln _{}a przez 3. Wieć znaleźliśmy w grafie G cykl o długości niepodzielnej przez 3, wi_{}ec mamy sprzeczność. Zatem na mocy rozumowania indukcyjnego jesteśmy tak w stanie usadowić niepodzieln _{}a przez 3 liczb_{}e przyjaciół przy stole, aby teza zadania była spełniona (ktoś jeszcze pami_{}eta o jakichś przyjaciołach i stole???) c.k.d.

Zauważmy, że przekształcaj _{}ac równoważnie:

x_{i+1} x_{i}(x_{i} + 2) = 2x_{i}^{3} + x_{i+1}^{2}
0 = 2x_{i}^{3} − x_{i}^{2}x_{i+1} − 2x_{i}x_{i+1} + x_{i+1}^{2}
(2x_{i} − x_{i+1} )(x_{i}^{2} − x_{i+1} ) = 0

Zatem nast_{}epny wyraz ci _{}agu x_{i} jest poprzednim przemnożonym przez 2 lub podniesionym do kwadratu. Oznaczmy wi_{}ec poprzez ci _{}agi zerojedynkowe długości 2005 odpowiednie ci _{}agi operacji, które wykonujemy aby uzyskać kolejne wyrazy ci _{}agu x_{i}, gdzie 0 b_{}edzie wyrażało operacje przemnożenia przez 2 zaś 1 podniesienia do kwadratu. Najpierw pokażemy, że każdy ci _{}ag oprócz samych zer koduje pewne dokładnie jedno rozwi _{}azanie. Zauważmy, że maj _{}ac najpierw x_{1} a nast_{}epnie wynik przemnażaj _{}ac według schematu danego przez ci _{}ag zerojedynkowy przez dwójki lub podnosz _{}ac do kwadratu uzyskuj _{}ac nowy wynik w końcu, po wykonaniu 2005 operacji uzyskamy pewne wyrażenie, które znowu ma si_{}e równać x_{1}. Mamy wi_{}ec równanie na x_{1} postaci:

2^{k}x_{1}^{l} = x_{1}

Zauważmy teraz, że jeśli cały czas mnożyliśmy przez 2, to x_{1} si_{}e skróci (bo wtedy l = 1), wi_{}ec równanie b_{}edzie postaci 2 do dużej pot_{}egi jest równe 1, wi_{}ec wówczas nie może być spełniaj _{}acego x_{1}. W przeciwnym razie, co najmniej raz kwadratowaliśmy wynik, wi_{}ec pot_{}ega przy x_{1} b_{}edzie co namniej 2, wi_{}ec po skróceniu równanie b_{}edzie postaci:

x_{1} = \frac{1}{2^{\frac{k}{l−1}}}

Wi_{}ec x_{1} b_{}edzie odwrotności _{}a liczby wi_{}ekszej równej od 1, wi_{}ec b_{}edzie mniejsze równe od 1. Zauważmy, że podobne równania moglibyśmy napisać dla dowolnego x_{i}, wi_{}ec w każdym działaj _{}acym ci _{}agu dla każdego i zachodzi x_{i} 1. Zatem dla każedgo ci _{}agu zerojedynkowego istnieje dokładnie jedno rozwi _{}azanie oprócz ci _{}agu z samymi zerami. Teraz pokażemy, że dla dowolnych dwóch ci _{}agów zerojedynkowych rozwi _{}azanie w postaci ci _{}agu x_{i} jest różne. Załormy, że dwa różne ci _{}agi zerojedynkowe realizuj _{}a rozwi _{}azanie w postaci tego samego ci _{}agu x_{i}. Niech pewnym miejscem, gdzie ci _{}agi zerojedynkowe si_{}e różni _{}a jest indeks p. Wówczas, jako, że realizowane jest to samo rozwi _{}azanie, to z x_{p} przy pomocy przemnożenia przez 2 i podniesienia do kwadratu uzyskaliśmy ten sam wyraz x_{p+1} . Jednocześnie skoro wiemy, że każde rozwi _{}azanie jest realizowane przez jakiś ci _{}ag zerojedynkowy, a dla każdego rozwi _{}azania realizowanego przez ci _{}ag, każdy wyraz jest wi_{}ekszy od zera i mniejszy równy 1, to również zachodzi 0 < x_{p} 1. Zatem przemnożenie przez 2 x_{p} tworzy x_{p+1} > x_{p}, zaś podniesienie do kwadratu toworzy x_{p+1} x_{p}, zatem mamy sprzeczność, bo x_{p+1} nie może być zarówno mniejsze równe jak i w”ieksze od x_{p}. Zatem dla każdego z 2^{2005} −1 ci _{}agów (tych oprócz samym zer) istnieje rozwi _{}azanie i dla każdych dwóch jest inne, wi_{}ec rozwi _{}azań układu jest 2^{2005} − 1.

Oznaczmy ∠BAC = α oraz k = \frac{AC}{AB}. Zauważmy, że skoro również ∠BF D = α to z k _{}atów naprzemioanległych AC∥DF wi_{}ec czworok _{}at AF DC jest trapezem równoramiennym, wi_{}ec AF = CD. Zauważmy, że skoro ∠EDC = ∠ECD = α, to trójk _{}at EDC jest równoramienny i podowbnyu do BAC z cechy KKK. Zatem EF = CD = k · EC, wi_{}ec wektor \overrightarrow{AF} powstaje z wektora \overrightarrow{EC} poprzez obrót o k _{}at α i jednokładność o skali k. Analogicznie jest z wektorami \overrightarrow{AC} i \overrightarrow{BC}. Wi_{}ec w tym podobieństwie trójk _{}at EBC przechodzi na F CA, wi_{}ec odpowiadaj _{}ace boki tych trójk _{}atów s _{}a do sibie pod k _{}atem α. Wi_{}ec ∠F P B = α st _{}ad ∠F P E + ∠F AE = 180^{∘} − α + α = 180^{∘}, wi_{}ec na czworok _{}acie AEP F da si_{}e opisać okr _{}ag c.k.d.

6.(by Robert Pałuba) Na pocz _{}atku mamy coś takiego:

a\sqrt{b^{2} + c^{2} + bc} + b\sqrt{a^{2} + c^{2} + ac} + c\sqrt{a^{2} + b^{2} + ab} \sqrt{3}(ab + ac + bc)

Po podzieleniu stronami przez abc otrzymujemy:

\sqrt{\frac{1}{b^{2}} + \frac{1}{c^{2}} + \frac{1}{bc}} + \sqrt{\frac{1}{a^{2}} + \frac{1}{c^{2}} + \frac{1}{ac}} + \sqrt{\frac{1}{a^{2}} + \frac{1}{b^{2}} + \frac{1}{ab}} \sqrt{3}(\frac{1}{a} + \frac{1}{b} + \frac{1}{c})

Wykonuj _{}ac oryginalne podstawienie \frac{1}{x} = a, \frac{1}{y} = b, i \frac{1}{z} = c, wychodzi:

\sqrt{x^{2} + y^{2} + xy} + \sqrt{x^{2} + z^{2} + xz} + \sqrt{y^{2} + z^{2} + yz} \sqrt{3}(x + y + z)

Nierównośc ta jest jednorodna, wi_{}ec możemy założyć, że x + y + z = 1. Wtedy sprowadza si_{}e ona do:

\sqrt{(1 − z)^{2} − xy} + \sqrt{(1 − y)^{2} − xz} + \sqrt{(1 − x)^{2} − yz} \sqrt{3}

Teraz najwi_{}ekszy myk tego zadania:

\frac{(x + y)^{2}}{4} xy

\frac{(1 − z)^{2}}{4} xy

Zatem zamiast xy możemy wstawić \frac{(1−z)^{2}}{4} i tylko wzmocni to tez_{}e. Analogicznie wstawiamy za xz i yz.

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

\frac{1 − z}{2} + \frac{1 − y}{2} + \frac{1 − x}{2} 1

1 1

Co kończy dowód