Można trochę prościej [niż to, co ja tutaj napiszę], działa np. lemat że jeśli rozmawiają jakiekolwiek 2 osoby które mają jakąkolwiek wspólną informację, to można zmniejszyć liczbę osób o 1 i liczbę rozmów o 2, co rozwala zadanie prawie natychmiast i dowód jest nieco krótszy.
Czy istnieje funkcja dwóch zmiennych \(\displaystyle{ f:\mathbb{R}^{2} \rightarrow \mathbb{R}}\) t. że \(\displaystyle{ f(x,y)}\) jest wielomianem iksa po ustaleniu igreka oraz wielomianem igreka po ustaleniu iksa, ale \(\displaystyle{ f(x,y)}\) nie jest wielomianem dwóch zmiennych?
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:01
autor: TheCB
Ukryta treść:
Pokażemy, że taka funkcja nie istnieje. W tym celu przypuśćmy, że funkcja \(\displaystyle{ f(x,y)}\) spełnia warunki zadania. Wówczas istnieją takie funkcje \(\displaystyle{ f_{0}(y), f_{1}(y), ..., f_{n}(y)}\), że dla dowolnych \(\displaystyle{ x, y \in \mathbb{R}}\) mamy \(\displaystyle{ f(x,y)=\sum_{i=0}^{n} f_{i}(y)x^{i}}\). Następnie definiujemy funkcje \(\displaystyle{ g^{1}_{1}(y),g^{1}_{2}(y),...,g^{1}_{n}(y)}\) tak, że dla dowolnego dodatniego całkowitego \(\displaystyle{ k \le n}\) mamy \(\displaystyle{ g^{1}_{k}(y)=f(k,y)}\). Z założenia wynika, że funkcje te są wielomianami. Dla dowolnych liczb całkowitych \(\displaystyle{ k,l}\),
dla których mamy \(\displaystyle{ 1<k \le n}\) oraz \(\displaystyle{ 0<l \le n-k+1}\) będziemy definiować funkcję \(\displaystyle{ g^{k}_{l}(y)}\) tak, że \(\displaystyle{ g^{k}_{l}(y)=g^{k-1}_{l+1}(y)-g^{k-1}_{l}(y)}\) (takie funkcje są oczywiście wyznaczone jednoznacznie i są wielomianami). Można pokazać (prosta indukcja po \(\displaystyle{ k}\)), że dla dowolnych \(\displaystyle{ k}\), \(\displaystyle{ l}\) (spełniające wcześniejsze założenia) istnieją wielomiany \(\displaystyle{ C_{n}, C_{n-1}, ..., C_{k-1}}\) odpowiednio stopni \(\displaystyle{ n-k+1, n-k, ..., 0}\), że dla dowolnego \(\displaystyle{ y \in \mathbb{R}}\) zachodzi równość \(\displaystyle{ g^{k}_{l}(y)=\sum_{i=k-1}^{n} f_{i}(y)C_{i}(k)}\). Pokażemy teraz przy pomocy tego faktu, że funkcje \(\displaystyle{ f_{0}(y), f_{1}(y), ..., f_{n}(y)}\)są wielomianami, co zakończy dowód. W tym celu udowodnimy indukcyjnie, że dla dowolnego całkowitego nieujemnego \(\displaystyle{ k \le n}\) funkcja \(\displaystyle{ f_{n-k}(y)}\) jest wielomianem. Istotnie, dla \(\displaystyle{ k=0}\) teza jest spełniona, gdyż wielomian \(\displaystyle{ g^{n}_{1}(y)}\) jest postaci \(\displaystyle{ C \cdot f_{n}(y)}\), gdzie \(\displaystyle{ C \neq 0}\) jest pewną stałą. Załóżmy teraz, że dla \(\displaystyle{ k=0, 1, 2, .., m-1}\) teza jest spełniona (\(\displaystyle{ 0<m \le n}\)). Pokażemy, że jest ona również spełniona dla \(\displaystyle{ k=m}\). Istotnie, istnieją wielomiany \(\displaystyle{ C_{n}, C_{n-1}, ..., C_{n-m}}\) odpowiednio stopni \(\displaystyle{ m, m-1, ..., 0}\), że dla dowolnego \(\displaystyle{ y \in \mathbb{R}}\) mamy \(\displaystyle{ g^{n-m+1}_{1}(y)=\sum_{i=n-m}^{n} f_{i}(y)C_{i}(n-m+1)=\sum_{i=n-m+1}^{n} f_{i}(y)C_{i}(n-m+1)+f_{n-m}(y)C_{n-m}(n-m+1)}\).
Funkcje \(\displaystyle{ g^{n-m+1}_{1}(y)}\) oraz \(\displaystyle{ h(y)=\sum_{i=n-m+1}^{n} f_{i}(y)C_{i}(n-m+1)}\) są wielomianami (ta druga z założenia indukcyjnego). Stąd i funkcja \(\displaystyle{ g^{n-m+1}_{1}(y)-h(y)=f_{n-m}(y)C_{n-m}(n-m+1)}\) jest wielomianem, a zatem funkcja \(\displaystyle{ f_{n-m}(y)}\)
- też. Kończy to dowód indukcyjny, a zatem też i rozwiązanie zadania.
Jak jest OK to coś wrzucę.
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:11
autor: timon92
TheCB pisze:Wówczas istnieją takie funkcje \(\displaystyle{ f_{0}(y), f_{1}(y), ..., f_{n}(y)}\), że dla dowolnych \(\displaystyle{ x, y \in \mathbb{R}}\) mamy \(\displaystyle{ f(x,y)=\sum_{i=0}^{n} f_{i}(y)x^{i}}\).
dlaczego?
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:22
autor: TheCB
Czy to nie wynika bezpośrednio z faktu, że \(\displaystyle{ f(x,y)}\) jest wielomianem iksa po ustaleniu igreka? Wtedy dla danego \(\displaystyle{ y \in \mathbb R}\) funkcje te przyjmowałyby wartości będące współczynnikami takiego wielomianu, a \(\displaystyle{ n}\) byłoby największym możliwym stopniem takiego wielomianu.
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:27
autor: timon92
dla różnych igreków te wielomiany mogą mieć różne stopnie, w szczególności może być tak, że występują tam dowolnie duże stopnie, a w swoim rozwiązaniu zakładasz, że stopnie tych wielomianów są ograniczone przez \(\displaystyle{ n}\)
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:29
autor: TheCB
Aha, czyli bzdury napisałem :/
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 18 lip 2017, o 13:32
autor: a4karo
F. W. Carroll, "A polynomial in each variable separately is a polynomial." Amer. Math. Monthly 68 (1961) 42.
-- 18 lip 2017, o 19:40 --
Nie tak bardzo bzdury.
Rozwiązanie opiera się o obserwację, że dla pewnego \(\displaystyle{ n}\) zbiór ygrekow dla których stopień \(\displaystyle{ f(x, y)}\) nie przekracza \(\displaystyle{ n}\) jest nieskończony.
Re: [Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 17 sie 2024, o 14:46
autor: mol_ksiazkowy
Zadanie Udowodnić, ze \(\displaystyle{ \frac{n+1}{2} \le H_{2^n} \le n+1,}\) gdy \(\displaystyle{ H_n = 1+ \frac{1}{2} +...+ \frac{1}{n} .}\)