Matematyka.pl

Oczywiście wszystkie liczby \(\displaystyle{ 2^0, 2^1, \ldots 2^9=512}\) muszą mieć parami różne kolory, a to dlatego, że \(\displaystyle{ 2^{\min(a,b)}|2^a}\) i \(\displaystyle{ 2^{\min(a,b)}|2^b}\) (więc dla każdych dwóch z tych liczb któraś dzieli drugą)
tj. \(\displaystyle{ n\ge 10}\). Pokażemy, że dla \(\displaystyle{ n=10}\) się da: kolorujemy kolorem sraczkowatym liczbę \(\displaystyle{ 512}\) i wszystkie większe od niej liczby naturalne aż do \(\displaystyle{ 1000}\), kolorem liliowym liczbę \(\displaystyle{ 256}\) i wszystkie od niej większe aż do \(\displaystyle{ 511}\) włącznie, kolorem seledynowym wszystkie od \(\displaystyle{ 128}\) do \(\displaystyle{ 255}\) włącznie, kolorem kanarkowożółtym wszystkie od \(\displaystyle{ 64}\) do \(\displaystyle{ 127}\) włącznie itd. (nie chce mi się już pisać), ogólnie i-tym kolorem kolorujemy liczby od \(\displaystyle{ 2^{10-i}}\) poczynając, na \(\displaystyle{ \min(2^{11-i}-1, 1000)}\) kończąc, \(\displaystyle{ i=1,2\ldots 10}\). To działa, gdyż jeśli dwie różne liczby \(\displaystyle{ x,y}\) z rozważanego zbioru są tego samego koloru, to \(\displaystyle{ \max(x,y) \in \left( \min(x,y), 2\cdot \min(x,y))}\), więc oczywiście \(\displaystyle{ \min(x,y)\nmid \max(x,y)}\).
Sorry, nie chciało mi się klikać albo pisać klamrowych nawiasów.

Powiedzmy najpierw, że \(\displaystyle{ a>1 \wedge b>1}\). Niech \(\displaystyle{ a= \prod_{i=1}^{ \infty }p_i^{\alpha_i}}\) oraz \(\displaystyle{ b= \prod_{j=1}^{ \infty } p_j^{\beta_j}}\), gdzie tylko skończenie wiele spośród całkowitych nieujemnych \(\displaystyle{ \alpha_i, \ \beta_j}\) przekracza zero (niektórzy matematycy mają w życiu za mało konwersacji czy kopulacji, więc tworzą inne wyrazy zaczynające się od „ko-", na przykład „koskończony", moim zdaniem paskudztwo).
Wówczas \(\displaystyle{ a^b b^a= \prod_{i=1}^{ \infty }p_i^{b\alpha_i+a\beta_i}}\)
Ponieważ \(\displaystyle{ a,b}\) są z założenia nieparzyste, więc zarówno każda z liczb \(\displaystyle{ b\alpha_i}\), jak i każda z liczb \(\displaystyle{ a\beta_i}\) jest takiej samej parzystości, jak \(\displaystyle{ \alpha_i}\) oraz \(\displaystyle{ \beta_i}\) odpowiednio.
Ogólnie: aby liczba całkowita \(\displaystyle{ 1<x= \prod_{k=1}^{ \infty } p_k^{\eta_k}}\), gdzie \(\displaystyle{ p_k}\) to kolejne liczby pierwsze, zaś \(\displaystyle{ \eta_k \in \NN}\) (łącznie z zerem), była kwadratem liczby naturalnej, potrzeba i wystarcza, by dla \(\displaystyle{ k=1,2\ldots}\) zachodziło \(\displaystyle{ 2|p_k}\) (raczej nie trzeba tego dowodzić).
Aby liczba \(\displaystyle{ a^b b^a}\) była kwadratem liczby naturalnej, potrzeba i wystarcza, by każdy z wykładników \(\displaystyle{ b\alpha_i+a\beta_i}\) był liczbą parzystą, ale ponieważ, jakeśmy już stwierdzili, z nieparzystości liczb \(\displaystyle{ a,b}\) mamy \(\displaystyle{ a\beta_i\equiv \beta_i\pmod{2}}\) oraz \(\displaystyle{ b\alpha_i\equiv \alpha_i\pmod{2}}\), to
\(\displaystyle{ b\alpha_i+a\beta_i\equiv \alpha_i+\beta_i \pmod{2}}\).
Skoro więc wiemy, że dla każdego \(\displaystyle{ i}\) jest \(\displaystyle{ b\alpha_i+a\beta_i\equiv 0\pmod{2}}\), to także dla każdego \(\displaystyle{ i}\) mamy \(\displaystyle{ \alpha_i+\beta_i \equiv 0\pmod{2}}\), no a
\(\displaystyle{ ab= \prod_{i=1}^{ \infty } p_i^{\alpha_i+\beta_i}}\), co kończy dowód w przypadku \(\displaystyle{ a>1 \wedge b>1}\).

Pozostaje zauważyć, że gdy \(\displaystyle{ a=1}\) lub \(\displaystyle{ b=1}\), to teza jest trywialna, bo w tych przypadkach mamy \(\displaystyle{ a^bb^a=ab}\).

Ciekawe, jak wygląda rozwiązanie tego zadania nieużywające rozkładu na czynniki pierwsze.

Z układu równań i z niezerowości \(\displaystyle{ a,b,c}\) wynika po wymnożeniu, że
\(\displaystyle{ abc=(b^2-a^2)(c^2-b^2)(a^2-c^2) \ (*)}\),
z drugiej strony po dodaniu trzech równań stronami i skróceniu dostaniemy
\(\displaystyle{ a+b+c=0}\).
Ze wzoru skróconego mnożenia na różnicę kwadratów zapisujemy więc \(\displaystyle{ (*)}\) w postaci
\(\displaystyle{ abc=(b-a)(c-b)(a-c)(b+a)(c+b)(a+c)}\), wstawiamy po prawej \(\displaystyle{ b+a:=-c, \ c+b:=-a, \ a+c:=-b}\), dostajemy
\(\displaystyle{ abc=-abc(b-a)(c-b)(a-c)}\), dzielimy stronami przez niezerowe (żeby bylo zerowe, któryś z czynników musiałby być zerem, a założenia tak nie jest) \(\displaystyle{ abc}\), zauważamy, że \(\displaystyle{ -(b-a)(c-b)(a-c)=(a-b)(b-c)(c-a)}\) i po zadaniu.

\(\displaystyle{ a=2y+1\\
b= 2z+1\\
x^2=(2y+1)^{2z+1} \cdot (2z+1)^{2y+1}\\
x^2=(2y+1)^{2z} \cdot (2y+1) \cdot (2z+1)^{2y} \cdot (2z+1)\\
x^2=[(2y+1)^{z} \cdot (2z+1)^{y}]^{2} \cdot ab\\
x=(2y+1)^{z} \cdot (2z+1)^{y} \cdot \sqrt{ab}}\)
Z tego już widać, że \(\displaystyle{ ab}\) musi być kwadratem liczby naturalnej.

Kolorujemy następująco (działa dla dowolnego \(\displaystyle{ n}\)):
\(\displaystyle{ 1}\) dostaje kolor \(\displaystyle{ 1}\), a dowolna liczba naturalna rozłożona na czynniki pierwsze \(\displaystyle{ n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\dots p_{l}^{\alpha_{l}}}\) dostaje kolor \(\displaystyle{ \alpha_{1}+\alpha_{2}+\dots + \alpha_{l}+1}\). Pozostawiam jako ćwiczenie pokazanie, że takie kolorowanie spełnia warunki zadania. Można równie łatwo pokazać, że jest to kolorowanie minimalne (używające najmniejszej ilości kolorów). Wystaczy zauważyć, że liczby \(\displaystyle{ 1,2,2^2, 2^3,
\dots 2^k}\) muszą mieć różne kolory. Stąd dla \(\displaystyle{ n}\) trzeba użyć przynajmniej \(\displaystyle{ \lfloor \log _{2}n\rfloor +1}\) a łatwo pokazać, że to kolorawanie użyje właśnie tyle kolorów.
PS: Jak to znaleźć? Ja zacząłem zachłannie kolorować, czyli liczbie \(\displaystyle{ 1}\) dałem kolor \(\displaystyle{ 1}\), liczbom pierwszym kolor \(\displaystyle{ 2}\) i po kolei każdej liczbie najmniejszy kolor jaki mogłaby dostać (algorytm zachłanny). I się okazało, że to działa

Z podobieństwa trójkątów \(\displaystyle{ \Delta ABE \sim \Delta CDE}\) mamy \(\displaystyle{ \frac{DE}{EB}=\frac{CD}{AB}}\). Z Talesa \(\displaystyle{ \frac{DE}{EB}=\frac{DF}{FA}}\). Łącząc te dwie zależności i używając założenia \(\displaystyle{ AB+CD=AD}\) dostajemy \(\displaystyle{ AF=AB}\) oraz \(\displaystyle{ CD=DF}\). Stąd z trójkątów równoramiennych i równoległości łatwo dostać \(\displaystyle{ \angle BFC = 90^{\circ}}\).

fakcik pierwszy: jeśli \(\displaystyle{ D}\) jest środkiem okręgu dopisanego do boku \(\displaystyle{ BC}\) trójkąta \(\displaystyle{ ABC}\), to \(\displaystyle{ \angle CDB = 90^\circ - \frac 12 \angle BAC}\)

dowód: prościutkie przeliczenie kątów

fakcik drugi: fakcik pierwszy można odwrócić: jeśli punkt \(\displaystyle{ D}\) leży na dwusiecznej kąta \(\displaystyle{ BAC}\) poza trójkątem \(\displaystyle{ ABC}\) i spełniona jest równość \(\displaystyle{ \angle CDB = 90^\circ - \frac 12 \angle BAC}\), to punkt \(\displaystyle{ D}\) jest środkiem okręgu dopisanego do boku \(\displaystyle{ BC}\) trójkąta \(\displaystyle{ ABC}\)

dowód: im dalej \(\displaystyle{ D}\) od \(\displaystyle{ A}\), tym mniejszy kąt \(\displaystyle{ CDB}\), tzn. istnieje tylko jeden punkt \(\displaystyle{ D}\) spełniający równość \(\displaystyle{ \angle CDB = 90^\circ - \frac 12 \angle BAC}\) i na mocy fakciku pierwszego jest nim środek okręgu dopisanego do boku \(\displaystyle{ BC}\) trójkąta \(\displaystyle{ ABC}\)

przechodzimy do rozwiązania zadania: na mocy fakciku drugiego \(\displaystyle{ M}\) jest środkiem okręgu dopisanego do boku \(\displaystyle{ DE}\) trójkąta \(\displaystyle{ CDE}\)

wystarczy teraz narysować tenże okrąg i przerachować długości odcinków stycznych do tegoż okręgu