[Rozgrzewka OM][MIX] Łańcuszek olimpijski

[tkrass]

Dumel, wrzuć zadanie proszę.

[Dumel]

niech \(\displaystyle{ M}\) będzie zbiorem skończonych ciągów zerojedynkowych, takich że żaden nie jest prefiksem innego. niech \(\displaystyle{ m_i}\) będzie liczbą ciągów w \(\displaystyle{ M}\) o długości \(\displaystyle{ i}\).
udowodnić że
\(\displaystyle{ \sum_{k=1}^{\infty} \frac{m_k}{2^k} \le 1}\)

[Zordon]

To zadanie można rozwiązać w poniższy sposób, ale jest to dowód trochę nieelementarny, więc podaje tylko jako ciekawostkę i czekamy na jakiś ładniejszy dowód.

Ukryta treść:    

Rozważmy standardową miarę Haara \(\displaystyle{ \mu}\) na zbiorze Cantora.
Dla ciągu zerojedynkowego \(\displaystyle{ a=(a_0,a_1,...,a_n)}\) oznaczmy \(\displaystyle{ \phi(a)=\{f \in \{0,1\}^{\mathbb{N}}: f(k)=a_k, k=0,1,...n\}}\)

Dla danego \(\displaystyle{ M}\) z zadania jeśli \(\displaystyle{ a,b \in M}\) to \(\displaystyle{ \phi(a) \cap \phi(b)=\emptyset}\).

Niech \(\displaystyle{ M=\{a_1,a_2,...\}}\)
Jeśli długość ciągu \(\displaystyle{ a_i}\) oznaczymy przez \(\displaystyle{ len(a_i)}\) to \(\displaystyle{ \mu(\phi(a_i))= \frac{1}{2^{len(a_i)}}}\), zatem:
\(\displaystyle{ 1 = \mu(\mathcal{C}) \ge \mu( \bigcup_{}^{ } \phi(M))= \sum_{i=1}^{ \infty }\mu(\phi(a_i)) = \sum_{i=1}^{ \infty } \frac{1}{2^{len(a_i)}} =\sum_{k=1}^{ \infty } \frac{m_k}{2^k}}\)

[limes123]

Lewa strona to suma prawdopodobienstw zdarzen \(\displaystyle{ A_k}\), ze z wszystkich ciagow 0,1 dlugosci k wybieramy ten nalezacy do M. Zdarzenia sa rozlaczne, czyli \(\displaystyle{ \sum \frac{m_k}{2^k}=\sum Pr(A_k)\leq Pr(\cup A_k)\leq 1}\).

----------------------

Niech \(\displaystyle{ f\in Z[X]}\) i stopien f to \(\displaystyle{ n\geq 2}\). Udowodnic, ze \(\displaystyle{ f(f(X))-X=0}\) ma co najwyzej \(\displaystyle{ n}\) rozwiazan calkowitych.

[Dumel]

Lewa strona to suma prawdopodobienstw zdarzen \(\displaystyle{ A_k}\), ze z wszystkich ciagow 0,1 dlugosci k wybieramy ten nalezacy do M. Zdarzenia sa rozlaczne, czyli \(\displaystyle{ \sum \frac{m_k}{2^k}=\sum Pr(A_k)\leq Pr(\cup A_k)\leq 1}\)

sorry jeśli będe teraz klepał głupoty ale coś mi tu śmierdzi bo przecież jakby wywalić założenie o braku prefiksów to te zdarzenia i tak byłyby niezależne i wszystko w dowodzie zostałoby tak samo a teza byłaby fałszywa.
\(\displaystyle{ A_i}\) chyba powinno polegać na wylosowaniu ciągu, który jest podciągiem pewnego ciągu z M

[jerzozwierz]

ludzie, to chyba miał być temat o przygotowaniu do II etapu, a wy rzucacie jakimiś akademickimi problemami...

[smigol]

ja nawet nie wiem co to znaczy
\(\displaystyle{ f \in Z[X]}\).

[limes123]

Dumel, rzeczywiscie to nie bylo najladniej napisane (ale o to chodzilo). Mozna po prostu powiedziec, ze losujemy dowolny nieskonczony ciag zero-jedynkowy r i sprawdzamy jakie jest prawdopodobienstwo, ze dany ciag z M jest prefiksem r i dostajemy
\(\displaystyle{ \sum_{x\in M} \frac{1}{2^{|x|}}\leq 1}\) co jest rownowazne tezie (|x| jest dlugoscia ciagu x z M).
Smigol, to znaczy ze f nalezy do zbioru wielomianow o wspolczynnikach calkowitych. Wydaje mi sie, ze ten zapis jest dosc popularny.

[smigol]

ja nawet nie wiem co to znaczy
\(\displaystyle{ f \in Z[X]}\).

Może popularny, po prostu nie spotkałem się nigdy z nim )

[binaj]

Załóżmy, wbrew tezie, że \(\displaystyle{ F(F(x))=x}\) dla \(\displaystyle{ x_1 > x_2 > \ldots > x_{n+1}}\).
dla \(\displaystyle{ i\in\{1,\ldots n\}}\) mamy:

\(\displaystyle{ x_i-x_{i+1}|F(x_i)-F(x_{i+1})|F(F(x_i))-F(F(x_{i+1}))=x_i-x_{i+1}}\)
z bardzo znanej własności wielomianu W o współczynnikach całkowitych: \(\displaystyle{ a-b|W(a)-W(b)}\)

zatem: \(\displaystyle{ x_i-x_{i+1}=|F(x_i)-F(x_{i+1})|}\), oraz:

\(\displaystyle{ x_1-x_{n+1}= \sum_{i=1}^{n}(x_i-x_{i+1})= \sum_{i=1}^{n}|(F(x_i)-F(x_{i+1}))| \ge
|\sum_{i=1}^{n}(F(x_i)-F(x_{i+1}))|=|\sum_{i=1}^{n}(x_i-x_{i+1})|=|x_1-x_{n+1}|=x_1-x_{n+1}}\)

czyli liczby \(\displaystyle{ F(x_i)-F(x_{i+1})}\) są tego samego znaku, niech będą dodatnie: (dla ujemnych będzie analogicznie):

\(\displaystyle{ x_i-x_{i+1}=F(x_i)-F(x_{i+1}) \Leftrightarrow F(x_i)-x_i=F(x_{i+1})-x_{i+1}}\)

Niech \(\displaystyle{ Q(x)=F(x)-x, degQ=n}\)
otrzymujemy: \(\displaystyle{ Q(x_1)=Q(x_2)=\ldots Q(x_{n+1})}\) - sprzeczność, bo wielomian stopnia \(\displaystyle{ n}\) nie może przyjmować tej samej wartości dla \(\displaystyle{ n+1}\) różnych argumentów

--------------------------------------------------------------------------------------------------

Na prostej danych jest \(\displaystyle{ 6n}\) punktów, z czego \(\displaystyle{ 4n}\)jest czarnych a \(\displaystyle{ 2n}\) białych. Udowodnić, że istnieje odcinek zawierający dokładnie \(\displaystyle{ 2n}\) punktów czarnych i dokładnie \(\displaystyle{ n}\) punktów białych.

[tkrass]

To zadanie z kółka, na którym miałem przyjemność być. Rozważmy dwa odcinki - ten który zawiera "lewe" 3n punktów i ten, który zawiera "prawe" 3n punktów. Będziemy dowodzić przez sprzeczność, więc żaden z tych odcinków nie zawiera dokładnie 2n punktów czarnych. Przypuśćmy, że odcinek "lewy" zawiera ich mniej (jeśli zawiera ich więcej, dowód jest analogiczny). Zauważmy, że jeśli przesuniemy teraz nasz odcinek o jeden punkt w prawo (tzn. rozważymy 3n punktów od drugiego do 3n+1), to liczba czarnych punktów zmieni się co najwyżej o jeden. Zatem, jeśli odcinek "prawy" miałby więcej niż 2n punktów czarnych, to przesuwając się cały czas o jeden punkt w prawo od lewego minęlibyśmy taki odcinek, który zawiera dokładnie 2n punktów czarnych. Ale taki nie może istnieć, a zatem odcinek "prawy" również ma mniej niż 2n punktów czarnych. Ale na odcinkach "prawym" i "lewym" w sumie znajdują się wszystkie punkty z prostej, w szczególności 4n punktów czarnych. Z drugiej strony pokazaliśmy, że na każdym z tych odcinków jest mniej niż 2n punktów czarnych, zatem w sumie jest mniej niż 4n. Sprzeczność, która dowodzi tezy.

Nowe:
Udowodnić, że równanie \(\displaystyle{ x^2+y^2+z^2=x^3+y^3+z^3}\) ma nieskończenie wiele rozwiązań w liczbach całkowitych x, y, z.

[waral]

\(\displaystyle{ x=-2n , y=-3n , z=4n}\) dla dowolnego n całkowitego \(\displaystyle{ \ge 0}\)

Świeże: Dowieść, że dla dowolnej liczby całkowitej \(\displaystyle{ m>1}\) istnieje wielomian o współczynnikach wymiernych, taki że \(\displaystyle{ f(k)= p_{k}}\) dla \(\displaystyle{ k=1,...,m}\) i gdzie \(\displaystyle{ p_{k}}\) oznacza k-tą z kolei liczbę pierwszą,

[tkrass]

waral, \(\displaystyle{ 29n^2 \neq 29n^3}\) dla \(\displaystyle{ n>1}\). Innymi słowy chyba wrzuciłeś blefa, więc w dalszym ciągu obowiązujące zadanie to:
Udowodnić, że istnieje nieskończenie wiele liczb całkowitych x, y, z, dla których:
\(\displaystyle{ x^2+y^2+z^2=x^3+y^3+z^3}\)

[XMaS11]

Zauważmy, że dla każdej liczby całkowitej k trójka liczb całkowitych:
\(\displaystyle{ (x,y,z)=(2k^3+k,-2k^3-k,2k^2+1)}\) spełnia wyjściowe równanie.
Trójek takich jest oczywiście nieskończenie wiele, skąd teza.

Nowe:
Dowieść, że dla dowolnej liczby całkowitej \(\displaystyle{ m>1}\) istnieje wielomian o wsp. wymiernych taki, że \(\displaystyle{ f(k)=p_k}\) dla \(\displaystyle{ k=1,...,m}\) i gdzie \(\displaystyle{ p_k}\) oznacza \(\displaystyle{ k}\)-tą liczbę pierwszą.

[Dumel]

\(\displaystyle{ f(x)=A_1p_1(x-2)(x-3)...(x-m)+A_2p_2(x-1)(x-3)...(x-m)+...+A_mp_m(x-1)...(x-m+1)}\)
dla x=1,2,...m wszystkie składki oprócz jednego nam się zerują więc \(\displaystyle{ A_i}\) dobieramy wiadomo jak

nowe:
Ufoludek zaatakował dom składający się z piwnicy, parteru, piętra i poddasza. między sąsiednimi kondygnacjami domu są schody po których się porusza. Gdy dochodzi do piwnicy pije wino z jednej z dwóch znajdujących się w niej beczek (są bardzo duże więc wina nie zabraknie) a gdy wchodzi na poddasze wysyła sygnał na Marsa za pomocą jednego ze swoich dwóch nadajników. Ufoludek startuje z parteru i \(\displaystyle{ n}\) razy przechodzi między kondygnacjami (jak dojdzie na skrajne wykonuje co trzeba na jeden z dwóch sposobów). łażenie po domu nie jest zbyt pasjonujące więc aby urozmaicić sobie misję ufoludek zastanawia się na ile sposobów może sobie połazić. Pomóż mu!