Matematyka.pl

Pewnie to jest bełkotliwie opisane, ale liczę, że idea jest do zrozumienia. Tania może znaleźć tę liczbę poprzez odczytanie od końca jej zapisu binarnego, nie więcej niż siedem cyfr, bo \(\displaystyle{ 2^{7}>100}\), więc da radę w nie więcej niż siedmiu krokach (no powiedzmy, takie było pierwsze skojarzenie ).
Najpierw pyta na przykład o \(\displaystyle{ \NWD(X+2,2)}\), żeby sprawdzić parzystość, czyli ostatnią cyfrę rozwinięcia dwójkowego (oczywiście \(\displaystyle{ X+2\equiv X\pmod{2}}\)), gdy wyjdzie \(\displaystyle{ \NWD}\) równe jeden, to przy \(\displaystyle{ 2^{0}}\) mamy jedynkę, w przeciwnym razie zero. Dalej leci w ten sposób: jeśli zna już współczynniki przy \(\displaystyle{ 2^{0}, \ldots 2^{i}}\), to znaczy, że zna resztę z dzielenia \(\displaystyle{ X}\) przez \(\displaystyle{ 2^{i+1}}\). Niech tą resztą będzie \(\displaystyle{ r}\). W następnym kroku, by uzyskać współczynnik przy \(\displaystyle{ 2^{i+1}}\), sprawdza
\(\displaystyle{ \NWD\left (X+2^{i+1}-r, 2^{i+2}\right)}\). Oczywiście
\(\displaystyle{ 2^{i+1}|\left(X+2^{i+1}-r\right)}\), więc mamy dwie możliwe wartości tego \(\displaystyle{ \NWD}\), mianowicie zaś
\(\displaystyle{ 2^{i+1}}\) oraz \(\displaystyle{ 2^{i+2}}\).
Jeśli \(\displaystyle{ \NWD\left (X+2^{i+1}-r, 2^{i+2}\right)=2^{i+1} }\), to przy \(\displaystyle{ 2^{i+1}}\) w rozwinięciu binarnym \(\displaystyle{ X}\) będzie zero, a jeżeli \(\displaystyle{ \NWD\left (X+2^{i+1}-r, 2^{i+2}\right)=2^{i+2} }\), to współczynnikiem przy \(\displaystyle{ 2^{i+1}}\) będzie jedynka.

Oczywiście może się to zepsuć na samym końcu, gdyż dla \(\displaystyle{ i=5}\) (a więc \(\displaystyle{ i+1=6}\)) mamy \(\displaystyle{ 2^{i+2}=128>100}\), czyli przekroczony jest nasz zakres \(\displaystyle{ M,N}\).
Dokładnie, może to być problem dla reszt modulo \(\displaystyle{ 64}\) nie większych niż \(\displaystyle{ 36}\). Wiemy wtedy jednak, że \(\displaystyle{ X}\) jest postaci \(\displaystyle{ R}\) albo \(\displaystyle{ 64+R}\), gdzie \(\displaystyle{ R\in\left\{0,1\ldots 36\right\}}\) już odczytaliśmy. Wystarczy więc sprawdzić
\(\displaystyle{ \NWD(X+1, R+65)}\) i jeśli wyniesie ono \(\displaystyle{ R+65}\), to szukaną liczbą jest \(\displaystyle{ 64+R}\), a w przeciwnym razie \(\displaystyle{ R}\).

Tak naprawdę zakres \(\displaystyle{ X, \ M, \ N}\), co wynika z uważnej lektury powyższego, można poprawić do \(\displaystyle{ 2^{7}-1=127}\) i dalej przejdzie.

Przytoczę twierdzenie:

Graf ma \(\displaystyle{ n }\)wierzchołków i\(\displaystyle{ k}\) krawędzi

definiujemy:

\(\displaystyle{ M(n)}\)

dla:

\(\displaystyle{ n=2m}\)

\(\displaystyle{ M(n)=m^2 }\)

dla:

\(\displaystyle{ n=2m+1}\)

\(\displaystyle{ M(n)=m(m+1) }\)

Z: \(\displaystyle{ n \ge 3 , k =M(n)+1}\)

T: Graf ma minimum:

\(\displaystyle{ \left[ \frac{n}{2} \right] }\)

wierzchołków...

U nas mamy:

\(\displaystyle{ n=6=2 \cdot 3}\)

\(\displaystyle{ M(6)=9}\)

\(\displaystyle{ k=10}\) co się zgadza

czyli mamy trójkątów co najmniej:

\(\displaystyle{ \left[ \frac{6}{2}\right] =3 }\)

co się zgadza z tezą zadania...

1) rozwiązania dodatnie mają postać:
\(\displaystyle{ \begin{cases} \lfloor y \rfloor =a \\ x= \frac{2019}{a} \\ \left\{ y\right\}= \frac{2020}{\lfloor \frac{2019}{a} \rfloor } -a \end{cases} }\)
dla \(\displaystyle{ a \in \left\{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,\\
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 53, 54, 56, 57, 59, 61, 63, 65, 67, \\
69, 72, 74, 77, 80, 84, 87, 91, 96, 106, 112, 118, 126, 134, 144, 155, 168, 183, 224, 252, 288, 336, 673\right\} }\)
Tylko takie wartości parametru \(\displaystyle{ a}\) spełniają warunek \(\displaystyle{ 0 \le \left\{ y\right\} <1 }\)
2) rozwiązania ujemne:

a) dla \(\displaystyle{ \left\{ x\right\} =0 }\) brak rozwiązań.

b) dla \(\displaystyle{ \left\{ y\right\} =0 }\) rozwiązaniem jest para:
\(\displaystyle{ y=-a \wedge x=- \lfloor \frac{2019}{a} \rfloor -1+ \frac{1}{a}}\)
dla \(\displaystyle{ a \in \left\{ 2, 4, 5, 10, 20, 101, 202, 404, 505, 1010, 2020 \right\} }\)

c) dla \(\displaystyle{ (0<\left\{ x\right\} <1 ) \wedge (0<\left\{ y\right\} <1 )}\) rozwiązaniem jest:
\(\displaystyle{ \begin{cases} \lfloor y \rfloor =-a \\ \lfloor x \rfloor= - \lfloor \frac{2019}{a} \rfloor -1 \\ \left\{ x\right\}= \frac{-2019}{a}+ \lfloor \frac{2019}{a} \rfloor +1 \\ \left\{ y\right\} = a- \frac{2020}{ \lfloor \frac{2019}{a} \rfloor +1} \end{cases} }\)
a założenia spełniają \(\displaystyle{ a \in \left\{
6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, \\
38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 54, 55, 57, 58, 60, 62, 64, 66, 68, 70, 73, 75, 78, 81, \\
85, 88, 92, 97, 107, 113, 119, 127, 135, 145, 156, 169, 184, 225, 253, 289, 337, 674 \right\} }\)

Ze wzorów Viete'a wynika, że liczby \(\displaystyle{ z_{1}, \ z_{2}, \ z_{3}}\) są pierwiastkami wielomianu
\(\displaystyle{ P(z)=z^{3}-z^{2}+Bz-1, \ B\in \CC}\)
Niech teraz dla pewnego \(\displaystyle{ z}\) o module \(\displaystyle{ 1}\) będzie \(\displaystyle{ P(z)=0}\). Możemy zapisać \(\displaystyle{ z=\cos \varphi+i\sin \varphi,
\ \varphi\in [0,2\pi)}\), a liczba zespolona jest równa zero, gdy jej część rzeczywista oraz urojona wynosi zero. Czyli
\(\displaystyle{ P(z)=0\Leftrightarrow \left(\cos(3\varphi)-\cos(2\varphi)+B\cos \varphi-1=0 \wedge \sin(3\varphi)-\sin(2\varphi)+B\sin \varphi=0 \right)}\).
1) Jeśli \(\displaystyle{ \sin \varphi=0}\), to \(\displaystyle{ z=\pm 1}\), wstawienie \(\displaystyle{ z=1}\) daje \(\displaystyle{ B=1}\), zaś wstawienie \(\displaystyle{ z=-1}\) prowadzi do \(\displaystyle{ B=-3}\). Tę drugą możliwość odrzucamy, gdyż pozostałe pierwiastki (które można wyliczyć dzięki twierdzeniu Bezouta i znajomości trójmianów kwadratowych chociażby) nie mają modułu \(\displaystyle{ 1}\).
2) Jeśli \(\displaystyle{ \cos \varphi=0}\), to \(\displaystyle{ z=\pm i}\) a wstawiając to do równania \(\displaystyle{ P(z)=0}\) otrzymujemy \(\displaystyle{ B=1}\).
3) Przypuśćmy, że \(\displaystyle{ \cos \varphi\neq 0, \ \sin \varphi\neq 0}\); wówczas mnożymy stronami pierwsze równanie układu
\(\displaystyle{ \begin{cases}\cos(3\varphi)-\cos(2\varphi)+B\cos(\varphi)-1=0\\\sin(3\varphi)-\sin(2\varphi)+B\sin (\varphi)=0\end{cases}}\)
przez \(\displaystyle{ \sin (\varphi)}\), drugie równanie mnożymy przez \(\displaystyle{ \cos(\varphi)}\), odejmujemy stronami drugie równanie od pierwszego i otrzymujemy:
\(\displaystyle{ \sin (\varphi)\cos(3\varphi)-\cos (\varphi)\sin(3\varphi)-\sin (\varphi)\cos(2\varphi)+\cos(\varphi)\sin(2\varphi)-\sin (\varphi)=0}\)
A to ze wzoru na sinus różnicy elegancko upraszcza się do postaci
\(\displaystyle{ -\sin(2\varphi)=0}\), czyli \(\displaystyle{ \varphi\in \left\{0, \frac{\pi}{2} \ , \pi, \ \frac{3}{2}\pi\right\}}\)
To jednak prowadzi do \(\displaystyle{ \sin \varphi=0\vee \cos \varphi=0}\), wbrew założeniu.

Podsumowując, otrzymaliśmy \(\displaystyle{ B=1}\) i mamy \(\displaystyle{ \left\{z_{1}, \ z_{2}, \ z_{3}\right\}=\left\{-i, \ i, \ 1\right\}}\),
więc łatwo wyliczyć \(\displaystyle{ \left|(z_{1}+2)(z_{2}+2)(z_{3}+2)\right|=15}\)

albo z tego iz ciąg \(\displaystyle{ y_n = x_n x_{n-1}-1}\) jest geometryczny (\(\displaystyle{ q= \frac{1}{2} }\)) gdyby był okresowy to by było \(\displaystyle{ y_n =y_1 =0}\)

Nie istnieją, co poniżej udowodnię.
Najpierw popatrzmy na równanie \(\displaystyle{ a^{3}+6ab+2b^{3}=4}\) ogólniej w liczbach rzeczywistych. Połóżmy w tym równaniu \(\displaystyle{ a=\sqrt[3]{4}x, \ b=\sqrt[3]{2}y, \ x,y\in \RR}\). Po prostych przekształceniach równanie przyjmuje formę
\(\displaystyle{ x^{3}+3xy+y^{3}=1}\), a następnie \(\displaystyle{ (x+y)^{3}+3xy-3xy(x+y)=1 \ (*)}\)
Jeśli \(\displaystyle{ x+y=1}\), to równanie \(\displaystyle{ (*)}\) jest spełnione; przypuśćmy dalej, że \(\displaystyle{ x+y\neq 1}\). Wówczas mamy równoważnie
\(\displaystyle{ 3xy(1-(x+y))=1-(x+y)^{3}\\ 3xy=1+x+y+(x+y)^{2}}\),
jednak nietrudno się przekonać, że wtedy
\(\displaystyle{ \frac{3}{4}(x+y)^{2}\ge 3xy=1+x+y+(x+y)^{2}}\), a innymi słowy
\(\displaystyle{ (x+y+2)^{2}\le 0}\), czyli musi być \(\displaystyle{ x+y=-2}\)
i równość w nierówności \(\displaystyle{ \frac{3}{4}(x+y)^{2}\ge 3xy}\) zachodzi tylko dla \(\displaystyle{ x=y}\).

Zatem jeśli liczby \(\displaystyle{ a,b\in \RR}\) spełniają równanie \(\displaystyle{ a^{3}+6ab+2b^{3}=4}\) i mamy \(\displaystyle{ a=\sqrt[3]{4}x, \ b=\sqrt[3]{2}y}\), to zachodzi jedna z możliwości \(\displaystyle{ x+y=1, \ x+y=-2}\), przy czym w tym drugim przypadku musi zajść \(\displaystyle{ x=y=-1}\).
Oczywiście jeśli \(\displaystyle{ x=y=-1}\), to wręcz żadna z liczb \(\displaystyle{ a=\sqrt[3]{4}x, \ b=\sqrt[3]{2}y}\) nie jest wymierna.
Pozostaje więc rozpatrzyć przypadek \(\displaystyle{ x+y=1}\).

Udowodnimy dalej, że jeśli \(\displaystyle{ x,y\in \RR, \ x+y=1}\), to co najmniej jedna spośród liczb \(\displaystyle{ \sqrt[3]{4}x, \ \sqrt[3]{2}y}\) jest niewymierna.
Przypuśćmy mianowicie, że liczba \(\displaystyle{ \sqrt[3]{4}x}\) jest wymierna. Wówczas musi istnieć takie \(\displaystyle{ t\in \QQ}\), że \(\displaystyle{ x=\sqrt[3]{2}t}\): istotnie, gdy \(\displaystyle{ \sqrt[3]{4}x=r, \ r\in\QQ}\), to \(\displaystyle{ x=\frac{r}{\sqrt[3]{4}}=\frac{\sqrt[3]{2}r}{\sqrt[3]{8}}=\frac{r}{2}\cdot \sqrt[3]{2}}\) i oczywiście gdy \(\displaystyle{ r\in \QQ}\), to również \(\displaystyle{ \frac{r}{2}\in \QQ}\).
Jednak skoro \(\displaystyle{ x=\sqrt[3]{2}t, \ t\in \QQ}\), to \(\displaystyle{ y=1-x=1-\sqrt[3]{2}t}\) i wtedy mamy
\(\displaystyle{ \sqrt[3]{2}y=\sqrt[3]{2}\left(1-\sqrt[3]{2}t\right)}\).
Liczba ta jest niewymierna, co wykażę nie wprost. By to wykazać, rozważę trzy przypadki.
\(\displaystyle{ 1^{\circ}}\) Niech \(\displaystyle{ t=\frac{p}{q}, \ p,q\in \ZZ, \ \NWD(p,q)=1, \ 2\nmid q}\).
Wówczas jeśli oznaczymy \(\displaystyle{ x=q\sqrt[3]{2}\left(1-\sqrt[3]{2}t\right)}\), to na mocy założenia nie wprost liczba ta będzie wymierna, jednak nietrudno się przekonać, że
\(\displaystyle{ x^{3}+6pqx=2q^{3}-4p^{3}}\) i mamy \(\displaystyle{ 2|\left(4p^{3}-2q^{3}\right), \ 4\nmid\left(4p^{3}-2q^{3}\right), \ 2|6pq, \ 2|0, \ 2\nmid 1}\),
zatem na mocy kryterium Eisensteina wielomian
\(\displaystyle{ P(X)=X^{3}+6pqX+4p^{3}-2q^{3}}\) jest nierozkładalny w \(\displaystyle{ \QQ[X]}\), ale \(\displaystyle{ x}\) jest jego wymiernym pierwiastkiem – sprzeczność.
\(\displaystyle{ 2^{\circ}}\) Niech \(\displaystyle{ t=\frac{p}{q}, \ p,q\in \ZZ, \ \NWD(p,q)=1, \ 2|q}\).
Podobnie wprowadzamy liczbę \(\displaystyle{ x=q\sqrt[3]{2}\left(1-\sqrt[3]{2}t\right)}\), która na mocy założenia nie wprost musiałaby być wymierna jako iloczyn liczb wymiernych i dochodzimy do równości \(\displaystyle{ x^{3}+6pqx=2q^{3}-4p^{3}}\)
Następnie podstawiamy \(\displaystyle{ x=2u, \ q=2r, \ u\in \QQ, \ r\in \ZZ}\) i po podzieleniu stronami mamy równość
\(\displaystyle{ 2u^{3}+6pru=4r^{3}-p^{3}}\)
a następnie wstawiamy \(\displaystyle{ u=\frac{1}{v}}\) (jasnym jest, że \(\displaystyle{ x\neq 0}\), a więc i \(\displaystyle{ u\neq 0}\))
i po prostych przekształceniach dostajemy
\(\displaystyle{ 2+6pr v^{2}=\left(4r^{3}-p^{3}\right)v^{3}}\)
przy czym oczywiście \(\displaystyle{ v=\frac{1}{\frac{x}{2}}}\) jest na mocy założenia nie wprost liczbą wymierną.
Ponadto skoro \(\displaystyle{ 2|q, \ \NWD(p,q)=1}\), to \(\displaystyle{ 2\nmid p}\) i wielomian
\(\displaystyle{ Q(X)=\left(4r^{3}-p^{3}\right)X^{3}-6prX^{2}-2}\) jest nierozkładalny w \(\displaystyle{ \QQ[X]}\) na mocy kryterium Eisensteina, ale ma pierwiastek wymierny \(\displaystyle{ v}\), co prowadzi do sprzeczności.

\(\displaystyle{ 3^{\circ}}\) Niech \(\displaystyle{ t=0}\). Wówczas sprawa sprowadza się do niewymierności \(\displaystyle{ \sqrt[3]{2}}\), ale liczba ta jest pierwiastkiem \(\displaystyle{ P(X)=X^{3}-2}\), który na mocy twierdzenia o pierwiastkach wymiernych wielomianu o współczynnikach całkowitych (w zasadzie to też szczególny przypadek Eisensteina tutaj, ale bez przesady) nie ma wymiernych pierwiastków.

Czy czegoś nie brakuje w opisie drzewa?

Wobec niejednoznaczności należy uznać za rozwiązane.