Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
To zadanie jest dość ciekawe:
P.S. 1
Jak wstawiałem to zadanie, to myślałem, że je zrobiłem, ale potem się okazało, że w zadaniu ciągłość nie jest dana xp. Zatem jeżeli nikomu to nie przeszadza, to mimo tego, że nie umiem zrobić tego zadania, zostawię je tutaj wbrew przepisowi, że powinienem je umieć zrobić xp.
P.S. 2
Używajcie opcji
Podstawiamy \(\displaystyle{ x:= \frac{x+1}{x}, x>0}\) do ostatniej równości opisującej f (oczywiście będę się posiłkować drugą własnością i nieparzystością): \(\displaystyle{ f(\frac{x}{x+1}) = f(1 - \frac{1}{x+1}) = 1 - f(\frac{1}{x+1}) = \frac{f(1 + \frac{1}{x})}{(\frac{x+1}{x})^2}=\frac{1 + f(\frac{1}{x})}{(\frac{x+1}{x})^2}}\).
Teraz stosuję po raz kolejny ostatnią własność i wymnażam obie strony przez \(\displaystyle{ (x+1)^2}\): \(\displaystyle{ (x+1)^2 -(f(x+1)) = x^2 + f(x) \\
x^2 + 2x+1 -f(x) - 1 = x^2 + f(x) \\
f(x) = x}\).
Z nieparzystości rozszerzamy ten wynik na wszystkie rzeczywiste.
Nowe zadanie:
Wielomian stopnia drugiego o całkowitych współczynnikach przyjmuje dla całkowitych argumentów wartości będące kwadratami liczb całkowitych. Pokazać, że jest on kwadratem pewnego wielomianu.
Niech \(\displaystyle{ f(x) = ax^2 + bx + c}\)
Oznaczmy \(\displaystyle{ g(x) = \sqrt{f(x)}}\).
Łatwo pokazać, że \(\displaystyle{ \lim_{x \to \infty } g(x+1) - g(x) = \sqrt{a}}\)
Wobec tego \(\displaystyle{ \sqrt{a}}\) jest liczbą całkowitą, i od pewnego miejsca \(\displaystyle{ g(x+1)= g(x) + \sqrt{a}}\)
Niech \(\displaystyle{ y}\) będzie taką liczbą całkowitą, że dla \(\displaystyle{ x \ge y}\) jest \(\displaystyle{ g(x+1)= g(x) + \sqrt{a}}\).
Wobec tego \(\displaystyle{ g(x) = g(y) + \sqrt{a}(x-y)}\)
Oznaczamy \(\displaystyle{ q= g(y)- \sqrt{a}y}\), q jest całkowite, czyli \(\displaystyle{ \sqrt{f(x)}=px+q}\), czego należało dowieść.
Ta granica najpierw dla \(\displaystyle{ x}\) całkowitych. Bo wtedy też \(\displaystyle{ g(x)}\) jest całkowite i z definicji granicy od pewnego momentu musi być tak jak napisał.
Niech \(\displaystyle{ F}\) bedzie rodzina podzbiorow zbioru \(\displaystyle{ \{1,2,...,n\}}\) taka, ze \(\displaystyle{ |F|=2^{n-1}}\) oraz \(\displaystyle{ A,B,C\in F}\) implikuje \(\displaystyle{ |A\cap B\cap C|\neq 0}\). Udowodnic, ze istnieje element nalezacy do kazdego z elementow \(\displaystyle{ F}\).
XMaS11 pisze:Ta granica najpierw dla \(\displaystyle{ x}\) całkowitych. Bo wtedy też \(\displaystyle{ g(x)}\) jest całkowite i z definicji granicy od pewnego momentu musi być tak jak napisał.
Niekoniecznie, może być tak, że dla całkowitych równość zachodzi, a dla innych odległość nie będzie równa zero. Może być np. tak, że dzieląc sobie rzeczywiste na przedziały między kolejnymi liczbami całkowitymi odległość od tej granicy będzie maksymalna w środku przedziału i będzie np. harmonicznie malejąca... W tym przypadku tak nie będzie, ale wymaga to argumentacji związanej bezpośrednio z tą funkcją, a na tym polega to zadanie... Z definicji granicy samej w sobie nic tu nie wynika
limes123 pisze:
Niech \(\displaystyle{ F}\) bedzie rodzina podzbiorow zbioru \(\displaystyle{ \{1,2,...,n\}}\) taka, ze \(\displaystyle{ |F|=2^{n-1}}\) oraz \(\displaystyle{ A,B,C\in F}\) implikuje \(\displaystyle{ |A\cap B\cap C|\neq 0}\). Udowodnic, ze istnieje element nalezacy do kazdego z elementow \(\displaystyle{ F}\).
Ukryta treść:
Każde dwa zbiory mają niepuste przecięcie. Niech \(\displaystyle{ k = |A \cap B|}\) będzie rozmiarem najmniejszego przecięcia dwóch zbiorów z \(\displaystyle{ F}\). Oznaczmy \(\displaystyle{ C = A \cap B}\) i \(\displaystyle{ C' = \{1,2,...,n\} \setminus C}\). Podzbiorów niepustych \(\displaystyle{ C}\) jest \(\displaystyle{ 2^k - 1}\) i każdy zawiera się w pewnym zbiorze z \(\displaystyle{ F}\). I na odwrót, każdy zbiór z \(\displaystyle{ F}\) ma niepuste przecięcie z \(\displaystyle{ C}\).
Gdy \(\displaystyle{ k=1}\) to teza jest oczywista. Załóżmy, że \(\displaystyle{ k > 1}\).
Zauważmy, że do \(\displaystyle{ F}\) nie może należeć \(\displaystyle{ C}\), bo wtedy z minimalności \(\displaystyle{ k}\) każdy zbiór z \(\displaystyle{ F}\) zawiera \(\displaystyle{ C}\), ale wtedy \(\displaystyle{ F}\) byłby rozmiaru co najwyżej \(\displaystyle{ 2^{n-k}}\).
Czyli do \(\displaystyle{ F}\) może należeć co najwyżej \(\displaystyle{ 2^{n-k}-1}\) zbiorów zawierających \(\displaystyle{ C}\) -- dobieramy do \(\displaystyle{ C}\) dowolny niepusty podzbiór \(\displaystyle{ C'}\).
Czyli istnieje co najmniej \(\displaystyle{ 2^{n-1}-2^{n-k}+1}\) podzbiorów z \(\displaystyle{ F}\), których przecięcie z \(\displaystyle{ C}\) jest ani niepuste, ani całym \(\displaystyle{ C}\). Stąd wynika, że pewien właściwy podzbiór \(\displaystyle{ C}\) jest obcięciem do \(\displaystyle{ C}\) dla co najmniej \(\displaystyle{ \frac{2^{n-1}-2^{n-k}+1}{2^k-2}}\) zbiorów z \(\displaystyle{ F}\). Z drugiej strony \(\displaystyle{ \frac{2^{n-1}-2^{n-k}+1}{2^k-2} > \frac{2^{n-1}-2^{n-k}}{2^k-2} = \frac{2^{n-k-1}(2^{k}-2)}{2^k-2} = 2^{n-k-1}}\).
Podzbiorów \(\displaystyle{ C'}\) jest \(\displaystyle{ 2^{n-k}}\), zatem istnieją dwa zbiory \(\displaystyle{ D,E \in F}\), takie że \(\displaystyle{ ( D \cap C') \cap (E \cap C') = \emptyset}\). To jednak przeczy minimalności \(\displaystyle{ k}\).
Niech \(\displaystyle{ A_1,...,A_n}\) będą podzbiorami \(\displaystyle{ \{1,...,n\}}\). Dla różnych \(\displaystyle{ i,j}\) mamy \(\displaystyle{ i \in A_j \leftrightarrow j \notin A_i}\) oraz \(\displaystyle{ |A_i \cap A_j| = k}\) dla pewnej stałej \(\displaystyle{ k}\). Ponadto dla każdego \(\displaystyle{ i}\) mamy \(\displaystyle{ i \notin A_i}\). Pokazać, że wszystkie podzbiory są tego samego rozmiaru.
Ostatnio zmieniony 6 maja 2010, o 01:56 przez półpasiec, łącznie zmieniany 3 razy.
Piotr Rutkowski, miałem na myśli to, że od pewnego momentu równość musi zachodzić dla całkowitych, czyli w szczególności dla nieskończenie wielu różnych liczb. No ale to oczywiście mój błąd, bo przejście z tego do równości dla wszystkich liczb wymaga paru słów komentarza.
No tak, bawimy się tylko w liczby całkowite, a z definicji granicy wynika, że dla liczb całkowitych będzie się zgadzać. Na końcu wystarczy zauważyć, że wielomian \(\displaystyle{ ax^2 + bx + c - (px+q)^2}\) ma nieskończenie wiele pierwiastków, więc \(\displaystyle{ ax^2 + bx + c = (px+q)^2}\) dla wszystkich.
Niech \(\displaystyle{ A_1,...,A_n}\) będą podzbiorami \(\displaystyle{ \{1,...,n\}}\). Dla różnych \(\displaystyle{ i,j}\) mamy \(\displaystyle{ i \in A_j \leftrightarrow j \notin A_i}\) oraz \(\displaystyle{ |A_i \cap A_j| = k}\) dla pewnej stałej \(\displaystyle{ k}\). Ponadto dla każdego \(\displaystyle{ i}\) mamy \(\displaystyle{ i \notin A_i}\). Pokazać, że wszystkie podzbiory są tego samego rozmiaru.
to nie jest prawda, kontrprzykład: n=2,k=0 \(\displaystyle{ A_1= \emptyset}\) i \(\displaystyle{ A_2 = \{1\}}\)
poza tym doszedłem do tego że podana sytuacja może zajść tylko dla
Ukryta treść:
k=0, n=3
co wydaje mi się mocno podejrzane ale nie widze błędu w moim rozwiązaniu. mógłbyś potwierdzić lub zaprzeczyć?
jednak był błąd, ale to co mam jest chyba cokolwiek warte:
Ukryta treść:
niech \(\displaystyle{ |A_i|=d_i}\)
rozpatrzmy graf \(\displaystyle{ G}\) o wierzchołkach \(\displaystyle{ v_1,v_2,...,v_n}\) taki że krawędź \(\displaystyle{ i \to j}\) istnieje wtw gdy \(\displaystyle{ j \in A_i}\). z podanych warunków otrzymujemy że G to skierowana klika, czyli dla dowolnych dwóch różnych wierzchołków i,j albo \(\displaystyle{ i \to j}\) albo \(\displaystyle{ j \to i}\).
oczywiście \(\displaystyle{ d(v_i)=d_i}\) gdzie \(\displaystyle{ d(v_i)}\) oznacza stopien wyjsciowy. Widzimy teraz że \(\displaystyle{ d_1+d_2+...+d_n = \frac{n(n-1)}{2}}\)
rozpatrzmy wektory \(\displaystyle{ w_1,...,w_n}\) takie że \(\displaystyle{ i}\)-ta wspolrzedna \(\displaystyle{ w_j}\) jest równa 1 gdy \(\displaystyle{ i \in A_j}\). w przeciwnym razie jest równa 0. \(\displaystyle{ w_i^2=d_i}\) oraz dla \(\displaystyle{ i \neq j}\)\(\displaystyle{ w_i \cdot w_j = k}\).
zauważamy że \(\displaystyle{ w_1+w_2+...+w_n =[n-1-d_1,...,n-1-d_n]}\). tak więc: \(\displaystyle{ (w_1+w_2+...+w_n)^2= \sum_{i=1}^{n}(n-1-d_i)^2=n(n-1)^2+ \sum_{i=1}^{n}d_i^2 - 2(n-1)\sum_{i=1}^{n}d_i=\sum_{i=1}^{n}d_i^2+n(n-1)^2 - (n-1)n(n-1)=\sum_{i=1}^{n}d_i^2}\)
z drugiej strony możemy to wyliczyć jako \(\displaystyle{ \sum_{i=1}^{n}w_i^2+2 \sum_{i<j}^{}w_i\cdot w_j = \sum_{i=1}^{n}d_i +n(n-1)k=n(n-1)(\frac{1}{2}+k)}\)
wobec tego stosując nierownosc miedzy srednimi otrzumujemy \(\displaystyle{ n(n-1)(\frac{1}{2}+k)= \sum_{i=1}^{n}d_i^2 \ge \frac{n(n-1)^2}{4}}\)
więc \(\displaystyle{ k \ge \frac{n-3}{4}}\)
teraz wystarczy pokazać że \(\displaystyle{ k \le \frac{n-3}{4}}\), czego jeszcze mi się nie udało zrobić (o ile to w ogole prawda)
poczyniłem wczoraj pewne postępy w tym rozwiązaniu, oto one:
poziome wektory \(\displaystyle{ v_1,...v_n}\) ustawmy sobie w macierz \(\displaystyle{ A}\)
macierz \(\displaystyle{ AA^T}\) ma na przekątnej liczby \(\displaystyle{ d_i}\) a poza przekątną wszędzie \(\displaystyle{ k}\). niniejszym teraz wysuwam Hipotezę: \(\displaystyle{ AA^T=A^TA}\)
wczoraj błędnie ją udowodniłem a na razie nie mam pomysłu na poprawny dowód. Patrząc na przykłady niewykluczone że jest ona prawdziwa: \(\displaystyle{ n=3}\): \(\displaystyle{ \left[\begin{array}{ccc}0&1&0\\0&0&1\\1&0&0\end{array}\right]}\) \(\displaystyle{ n=7}\): \(\displaystyle{ \left[\begin{array}{ccccccc}0&1&1&1&0&0&0\\0&0&1&0&1&1&0\\0&0&0&1&1&0&1\\0&1&0&0&0&1&1\\1&0&0&1&0&1&0\\1&0&1&0&0&0&1\\1&1&0&0&1&0&0\end{array}\right]}\)
zakładając że hipoteza jest prawdziwa:
po odwróceniu krawędzi w naszym grafie postulowane własności nadal są spełnione. weźmy dowolne dwa wierzchołki \(\displaystyle{ u,v}\). Niech: \(\displaystyle{ A=\{i \in V(G) | i \leftarrow v \wedge i \leftarrow u\}}\) \(\displaystyle{ B=\{i \in V(G) | i \leftarrow v \wedge i \rightarrow u\}}\) \(\displaystyle{ C=\{i \in V(G) | i \rightarrow v \wedge i \leftarrow u\}}\) \(\displaystyle{ D=\{i \in V(G) | i \rightarrow v \wedge i \rightarrow u\}}\) \(\displaystyle{ |A|=|D|=k}\) oraz \(\displaystyle{ |B|+|C|=n-2-2k}\).
Rozpatrzmy przypadek nieparzystego \(\displaystyle{ n}\) (wtedy wychodą jakieś porządne wnioski).
Jeden ze zbiorów: B,C ma moc co najmniej \(\displaystyle{ \lceil \frac{n-2-2k}{2}\rceil = \frac{n-1-2k}{2}}\) więc stopień wyjściowy jednego z wierzchołków: u,v jest równy co najmniej \(\displaystyle{ \frac{n-1}{2}}\). podobnie:
Jeden ze zbiorów: B,C ma moc co najwyzej \(\displaystyle{ \lfloor \frac{n-2-2k}{2}\rfloor = \frac{n-3-2k}{2}}\) więc stopień wyjściowy jednego z wierzchołków: u,v jest równy co najwyżej \(\displaystyle{ \frac{n-3}{2}+1=\frac{n-1}{2}}\) (dodajemy jedynke ze względu na krawędź między u i v). u i v były dowolne więc od razu mamy stąd tezę dla n nieparzystego.(przypominam ze założyłem prawdziwość hipotezy)
no cóż może jak co miesiąc będę dodawał kolejne wnioski to w końcu się uda zrobić to zadanie
jeśli teza zadania ma być prawdziwa (a jest), to musi zachodzić \(\displaystyle{ |v_i|=|A_i| = \frac{n-1}{2}}\) oraz \(\displaystyle{ k = \frac{n-3}{4}}\), więc też musi zachodzić \(\displaystyle{ A\cdot A^T = A^T\cdot A}\), bo \(\displaystyle{ [A\cdot A^T]_{ij} = v_i \cdot v_j = k}\). Z drugiej strony jeśli przez \(\displaystyle{ k_i}\) oznaczymy i-tą kolumnę \(\displaystyle{ A}\), to mamy \(\displaystyle{ k_i = 1^n -e_i - v_i}\), gdzie \(\displaystyle{ 1^n}\) to wektor złożony z samych jedynek, a \(\displaystyle{ e_i}\) to wektor z jedynką na i-tym miejscu i zerami na reszcie pozycji. Wtedy mamy dla \(\displaystyle{ i \neq j}\) mamy \(\displaystyle{ [A^T\cdot A]_{ij} = k_i \cdot k_j = (1^n -e_i - v_i)\cdot(1^n -e_j - v_j) = n - 1 - |v_j| - 1 + e_i\cdot v_j - |v_i| + v_i \cdot e_j + v_i\cdot v_j = n-2 - |v_i| - |v_j| + k + e_i\cdot v_j + v_i \cdot e_j = n - 1 - |v_i| - |v_j| + k}\), bo \(\displaystyle{ e_i\cdot v_j + v_i \cdot e_j = 1}\), z założenia. Zatem \(\displaystyle{ n - 1 - |v_i| - |v_j| + k = k}\), bo \(\displaystyle{ |v_i|=|v_j|=\frac{n-1}{2}}\). Czyli Twoja hipoteza jest na pewno prawdziwa.
