Matematyka.pl

Już po raz piąty odbyły się wrześniowe warsztaty matematyczne organizowane przez Naukowe Koło Matematyczne Funkcjonał. Sam tym razem miałem przyjemność robić dłuższy wykład o nierównościach . Oto większa część zadanek (pozostałe pojawiły się już na forum bądź są nieatrakcyjne, albo znalazły się w nich małe pomyłki, więc ich nie zamieszczałem), poziom trudności był zróżnicowany, osobiście wolałbym nieco trudniejsze, chociaż poziom i tak znacznie wzrósł w porównaniu do zeszłego roku:



* 1. dzień

1. Dane są dwa ułamki nieskracalne (\(\displaystyle{ a,b,c,d}\) całkowite dodanie): \(\displaystyle{ 1 \lbrace 1,2,\ldots,n \rbrace}\) na wszystkich polach k-tego wiersza i k-tej kolumny występują wszystkie liczby 1,2,...,n. Udowodnij, że w przypadku n nieparzystego każda z liczb 1,2,...,n jest napisana w ostatnim polu pewnego wiersza.


5. Rozważmy graf nieskierowany, którego krawędzie oznaczono znakiem + lub -. Dopuszczalny ruch polega na wybraniu wierzchołka i zamianie na przeciwne znaków wszystkich krawędzi, które wychodzą z tego wierzchołka. Wykaż równoważność następujących warunków:
(a) każdy cykl w grafie zawiera parzystą liczbę ujemnych krawędzi,
(b) za pomocą dopuszczalnych ruchów można ustawić znak wszystkich krawędzi na dodatni.

6. Na wolnych polach kwadratowej planszy o rozmiarach \(\displaystyle{ n n}\) dwaj gracze na przemian stawiają pionki (nierozróżnialne). Wygrywa gracz, po którego ruchu znajdą się cztery pionki na dowolnych czterech polach będących narożnikami prostokąta o bokach równoległych do krawędzi planszy. Rozstrzygnąć (w zależności od n), który z graczy ma strategię zwycięską - rozpoczynający czy jego przeciwnik.

7. Obliczyć \(\displaystyle{ 2^{2^{2^{2^2}}} \ (mod \ 21)}\).

8. Rozważamy rodzinę prostokątnych szachownic o następujących właściwościach:
* boki prostokąta są równe co najmniej 2.
* liczba pól usuniętych z szachownicy może być równa 0,1,2.
* na każdej szachownicy liczba pól białych i czarnych jest jednakowa (po odliczeniu pól usuniętych).
Udowodnij, że każdą taką szachownicę można ściśle wypełnić klockami domina przykrywającymi dwa sąsiednie pola szachownicy. Klocki nie pokrywają pól usuniętych.

9. Udowodnij, że środek sfery opisanej na czworościanie foremnym ma ze wszystkich punktów przestrzeni najmniejszą sumę odległości od wierzchołków czworościanu.

10. Danych jest \(\displaystyle{ n}\) kartoników, każdy z jednej strony pomalowany na czerwono, z drugiej na niebiesko. Kartoniki te rozkładamy dowolnie na okręgu. Jeden ruch polega na odwróceniu dowolnych trzech leżących obok siebie kartoników na drugą stronę. Wyznaczyć wszystkie takie wartości \(\displaystyle{ n}\), dla których z dowolnego początkowego układu kolorów da się dojść do każdego innego. Odpowiedź uzasadnij.

11. Wykonujemy serię rzutów symetryczną monetą. Obliczyć prawdopodobieństwo, że dwa orły pod rząd pojawią się po raz pierwszy w k-tym rzucie (k=2,3,...).




* 5. dzień:

1. Udowodnij, że istnieje nieskończenie wiele trójkątów pitagorejskich, których boki wyrażają się liczbami trójkątnymi.

2. Dany jest sześciokąt foremny \(\displaystyle{ A B C D E F}\) wpisany w okręg. Punkt P leży na okręgu. Udowodnij, że: \(\displaystyle{ AP^2+CP^2+EP^2=BP^2+DP^2+FP^2}\).

3. Dane sa liczby całkowite \(\displaystyle{ m n}\) szerzy się epidemia. Sąsiednie pola to te, które stykają się bokami. Na początku zarażonych jest \(\displaystyle{ k}\) pól - ognisk epidemii. Epidemia rozprzestrzenia się w kolejnych taktach. Jeżeli co najmniej dwóch sąsiadów niezarażonego pola jest zarażonych, to ono również staje się zarażone. Znajdź najmniejsze \(\displaystyle{ k}\) takie, że zarażona może zostać cała szachownica.




Powodzenia!
P.S. Kolorem czerwonym będę oznaczał numery zadań, które zostały (zostaną) poniżej rozwiązane.

Dzień 4 / 2
Zauwazmy, ze \(\displaystyle{ (10,q)=1}\)
Ponadto:
\(\displaystyle{ \underbrace{99 \ldots 9}_s=10^{s}-1}\)
Rozwazmy:
\(\displaystyle{ 10^{s}-1\equiv 0 \mod{q}}\)
Stad:
\(\displaystyle{ 10^{s}\equiv 1 \mod{q}}\)
Niech:
\(\displaystyle{ s:=q-1}\)
Przy powyzszych zalozeniach kongruencja:
\(\displaystyle{ 10^{s}\equiv 1 \mod{q}}\) dla \(\displaystyle{ s:=q-1}\)
zachodzi wowczas, gdy \(\displaystyle{ q\in \mathbb{P} \backslash \{2,5\}}\)

q nie musi być pierwsze, można zrobić z Dirichleta coś na wzór tego: viewtopic.php?t=77655 , bądź z twierdzenia Eulera mamy, że: \(\displaystyle{ 10^{\phi(q)} \equiv 1 \ (mod \ q)}\), co praktycznie kończy zadanie.

1.6.
Z jednomonotoniczności ciągów \(\displaystyle{ ( \frac{1}{a^{3}},\frac{1}{b^{3}}),(\sqrt{b},\sqrt{a}),((\sqrt{\frac{1}{a}}, \sqrt{ \frac{1}{b} } )}\) wynika teza.

2.1.
Na mocy nierówności Cauchyego-Schwarza:
\(\displaystyle{ ab^{2}+bc ^{2}+ca ^{2}\leqslant \sqrt{( a^{4}+b ^{4}+c ^{4})(a ^{2} +b ^{2}+c ^{2} )}= { a^{4}+b ^{4}+c ^{4}}}\)

1.7.
Operacja dodawania cyfr zachowuje podzielność przez 9, ponieważ dodatkowo szukana liczba jest dodatnia, więc jest nią 9.

3.4.
Wykonujemy klasyczne podstawienie, po czym korzystamy z nierówności \(\displaystyle{ \frac{4}{x+y} \leqslant \frac{1}{x} + \frac{1}{y}}\), prawdziwej dla dowolnych liczb rzeczywisych \(\displaystyle{ a,b}\).

[ Komentarz dodany przez: Sylwek: 1 Października 2008, 20:15 ]
Przypomnę: klasyczne podstawienie w nierównościach trygonometrycznych, czyli: a=x+y, b=y+z, c=z+x

IV day zad2 . \(\displaystyle{ x_n^2=x_{n-1}^2+2 +\frac{1}{x_{n-1}^2}}\) tj \(\displaystyle{ x_n^2 -x_{n-1}^2 >2}\) sumujac to dla n=1,,,.k mamy \(\displaystyle{ x_k^2 >2k+x_0^2}\) i kladziemy k=2016020, stad teza


II day zad 11 Jest to niemozliwe. Co drugie drzewo pomalujmy na biało a co drugie na czarno , tj biale i czarne drzewa sa naprzemian. Skok małp sprawia ze oba kolory drzew sa jednakowo obstawione.

Sylwek pisze: 6. Mamy daną liczbę \(\displaystyle{ 7^{2007}}\). W kolejnych krokach usuwamy pierwszą cyfrę aktualnej liczby i dodajemy ją do liczby złożonej z pozostałych cyfr. Postępujemy tak dotąd, aż dostaniemy liczbę dziesięciocyfrową. Udowodnij, że ta liczba ma co najmniej dwie takie same cyfry.

Zauważmy, że operacja nie zmienia reszty z dzielenia przez 9 tej liczby. \(\displaystyle{ 7^{2007}}\) nie dzieli się przez 9. Liczba 10 cyfrowa mająca wszystkie cyfry różne ma sumę cyfr równą 45, zatem dzieli się przez 9. Liczba, którą otrzymamy nie może mieć wszystkich cyfr różnych, więc przynajmniej dwie się powtarzają.

Sylwek pisze:7. Obliczyć \(\displaystyle{ 2^{2^{2^{2^2}}} \ (mod \ 21)}\).

Dowodzimy najpierw, że \(\displaystyle{ 2^{2k} \equiv 4 (mod 6)}\)
Czyli \(\displaystyle{ 2^{2^{2^{2^2}}}=2^{2^{16}}=2^{6n+4}}\) dla pewnego n. Zauważmy, że \(\displaystyle{ 2^6=64\equiv 1 (mod 21) 2^{6n}\equiv 1 (mod 21)}\) skąd \(\displaystyle{ 2^{6n+4}\equiv 2^4 \equiv 16 (mod 21)}\)

Zadania całkiem ciekawe, aczkolwiek większość z nich dość standardowa (Sylwek, myślałem, że jak prowadzisz nierówności to dasz jakiś większy hardkor). Może zrobię małego offtopa. Jako że te warsztaty odbywają się tylko dla woj. świętokrzyskiego to mam 2 pytanka:
a)czy wyskoczycie na drugi obóz w styczniu?
b)jeśli tak, to czy przyjmiecie 2-3 maruderów z łódzkiego?
P.S.żeby skończyć z nierównościami, to dodam:
1.5 Cauchy-Schwarz w formie Engela i samo wychodzi
P.S.2:
Nie zauważyłem 4.5, ale zdaje się, że tam będzie zwykła suma kwadratów (choć nie chce mi się sprawdzać )
P.S.3 Matko, ślepy jestem, zostało jeszcze 1.4 i 2.2
1.4 jest oczywiste (suma 2 nierówności AM-GM trzech zmiennych)
2.2 jest dość interesujące, zrobię jak będę miał chwilę

5. Dana jest kwadratowa szachownica \(\displaystyle{ k k}\). Na narożnym polu tej szachownicy stoi wieża. Wykaż, że jeśli ta wieża może przejść ze swojego rogu do rogu przeciwległego, przechodząc przez każde pole szachownicy dokładnie raz, to \(\displaystyle{ k}\) jest liczbą nieparzystą.

Niech k będzie parzyste, wieża startuje z białego pola, pole przeciwległe też jest białe
(możemy założyć ze jest białe nie zmniejszając straty ogólności), gdy wieża wykonuje przesunięcie o parzystą liczbę pól znajdzie się na białym polu, a żeby przejść do rogu wieża musi przejść przez \(\displaystyle{ k^2-1}\) pól, czyli nieparzystą ilość, więc nie będzie mogła znaleźć się na białym polu- sprzeczność

teraz tylko pozostaje podać jakiś przykład przejścia dal szachownicy gdzie k jest nieparzyste, co jest dosyć proste

7. Załóżmy, że gatunek ludzki nigdy nie wymrze (ale ludzie są śmiertelni). Wykaż, że żyje obecnie kobieta, która w każdym następnym pokoleniu będzie miała potomka płci żeńskiej.

Dowod nie wprost , dla j=1..n (teraz zyje n kobiet ) niech \(\displaystyle{ x_j}\) to bedzie nr pokolenia w ktorym zyl ostatni potomek zenski j tej kobiety. Tak wiec w pokoleniu \(\displaystyle{ 1+max_{j} \ x_j}\) braknie kobiet

polskimisiek pisze:Sylwek, myślałem, że jak prowadzisz nierówności to dasz jakiś większy hardkor

Nie było sensu, skoro były osoby na tych warsztatach, co nie znały nierówności pomiędzy średnimi. Nierówności były ciekawe, aczkolwiek nie wybitnie trudne, bo drugie nie wszystkie nierówności do serii zadaniowych były proponowane przeze mnie. Tylko 2.2. sprawiło mi większe problemy, ale się udało (powodzenia, bo na prawdę jest interesujące).

mol_ksiazkowy pisze:Skok małp sprawia ze oba kolory drzew sa jednakowo obstawione.

Tu raczej chodziło o niezmiennik w postaci (nie)parzystości liczby małp na białych/czarnych drzewach

polskimisiek pisze:jeśli tak, to czy przyjmiecie 2-3 maruderów z łódzkiego

To nie ode mnie zależy, aczkolwiek takie sprawy na PW.

P.S. Nie cytujcie treści zadań, tylko podawajcie dzień i numer, to pozwoli zachować przejrzystość tematu.

Day 2, zadanie 2Mamy experyment , tj Generujemy losowo macierz \(\displaystyle{ n \ x \ m}\) (tj n wierszy ,m kolum); zero- jedynkowa, przy czy prawdopodobienstwo pojawienia sie 1 wynosi p, zas 0 , wynosi q. tj \(\displaystyle{ p+q=1}\). Niech \(\displaystyle{ A}\) to zdarzenie, iz "w kazdym wierszu pojawia sie choc raz jedynka", zas \(\displaystyle{ B}\) to "w kazdej kolumnie pojawia sie choc raz zero". wtedy
\(\displaystyle{ p(A)+p(B)= (1-q^m)^n + (1-p^n)^m = p(A \cup B) + p(A \cap B) >1}\) bo \(\displaystyle{ p(A \cup B)=1}\)

[ Dodano: 2 Października 2008, 01:37 ]
Day 3 zad 1
punkt O to po prostu srodek ciezkosci trojkata ABC, stad ta rownosc wektorowa
sic

[ Dodano: 2 Października 2008, 02:02 ]
Dany 4 zad 11
W oparciu o lemat > Liczba ciagow zero-jedynkowych dlugosci n, t ze dwa zera nie stoja obok siebie wynosi \(\displaystyle{ F_{n+2}}\) ciag Fibonacciego,
tj p= \(\displaystyle{ \frac{F_{k+1}}{2^{k+1}}}\)

[ Dodano: 2 Października 2008, 14:23 ]
Day 2 zad 4Jesli wyciagnieto x par "biala z czarna", y par "biala z czerwona" i z par " czarna z czerwona" i w urnie tylko jedna kula to musi
byc ktorys z trzech ukladow

\(\displaystyle{ 1410- x-y+z=1}\)
\(\displaystyle{ 1789- x-z+y=0}\)
\(\displaystyle{ 1410- y-z+x=0}\)
lub

\(\displaystyle{ 1410- x-y+z=0}\)
\(\displaystyle{ 1789- x-z+y=1}\)
\(\displaystyle{ 1410- y-z+x=0}\)

lub
\(\displaystyle{ 1410- x-y+z=0}\)
\(\displaystyle{ 1789- x-z+y=0}\)
\(\displaystyle{ 1410- y-z+x=1}\)

tylko ten pierwszy uklad ma rozwiazanie całkowito liczbowe (\(\displaystyle{ x=1599 \ y=1708 \ z=1898}\))
Odp zostala w urnie biala kula

[ Dodano: 2 Października 2008, 14:50 ]
Day 1 zad 2
\(\displaystyle{ \frac{5}{4}, \ -\frac{1}{4} , \ -\frac{7}{4}}\)

Dzień I, zadanie 3. Czwórki interpretujemy jako współrzędne wektora, a ich iloczyn skalarny jest zerowy, gdy są prostopadłe (albo zerowe). Cztery czwórki o własności z zadania to:
\(\displaystyle{ (a,b,c,d) \\
(-c,d,a,-b) \\
(b,-a,d,-c) \\
(-d,-c,b,a)}\)

[ Dodano: 2 Października 2008, 14:50 ]
Dzień 4, zadanie 5.
To grupujemy (x-a)(x-d) i (x-b)(x-c), otrzymując po lewej:
\(\displaystyle{ (x^2 - (b+c)x + ad)(x^2 - (b+c)x + bc) + \left(\frac{ad-bc}{2}\right)^2 = (x^2 - (b+c)x)^2 + \\ (bc+ad)(x^2 - (b+c)x) + abcd + \left( \frac{ad-bc}{2}\right)^2 = (x^2 - (b+c)x)^2 + \\ (bc+ad)(x^2 - (b+c)x) + \left(\frac{ad+bc}{2}\right)^2 = \left(x^2 - (b+c)x + \frac{ad+bc}{2}\right)^2 \geqslant 0}\)
Dzień 5, zadanie 3.
Stosuję wzór rekurencyjny dla symbolu Newtona:
\(\displaystyle{ \sum_{k=m+1}^{n} {k \choose m+1} = \sum_{k=m+1}^{n} {k-1 \choose m} + \sum_{k=m+1}^{n} {k-1 \choose m+1} = \sum_{k=m}^{n} {k \choose m} - {n\choose m} + \sum_{k=m+1}^{n} + \underbrace{{m \choose m+1}}_{0} - {n\choose m+1} \\
\sum_{k=m}^{n} {k \choose m} = {n\choose m} + {n\choose m+1} = {n+1 \choose m+1}}\)

mol_ksiazkowy pisze:Day 2, zadanie 2

Gratuluję, u nas nikt tego nie zrobił (niby ja zrobiłem, ale dopiero jak następnego dnia dostaliśmy do rozwiązania 3.7, to zauważyłem powiązanie ).

Wasilewski pisze:Czwórki interpretujemy jako współrzędne wektora

po co

mol_ksiazkowy pisze:Dany 4 zad 11

dokładniej to: \(\displaystyle{ P(k)=\frac{F_{k-1}}{2^k}}\), ale idea jasna

mol_ksiazkowy pisze:Day 3 zad 1
punkt O to po prostu srodek ciezkosci trojkata ABC, stad ta rownosc wektorowa

Inaczej: można poprowadzić prostą prostopadłą do jednego z wektorów przechodzącą przez O i zrzutować dwa pozostałe wektory, tą operację powtórzyć 3 razy, dalej z górki.

Żeby pokazać, że nazwa "prostopadłe" jest sensowna. Oczywiście nie korzystałem z tego przy wymyślaniu tych czwórek.
Dzień 1, zadanie 1.
\(\displaystyle{ \frac{a+c}{b+d} = \frac{ \frac{a}{b} (b+d) + \frac{bc - ad}{b}}{b+d} = \frac{\frac{a(b+d)-1}{b}}{b+d}}\)
Wystarczy pokazać, że:
\(\displaystyle{ ( a(b+d) - 1, b+d) = 1}\)
A to jest oczywiste, bo gdyby miały wspólny dzielnik większy od jedynki, to również różnica by się przez niego dzieliła (stosujemy a razy), zatem również liczba:
\(\displaystyle{ a(b+d) - 1 - a(b+d) = -1}\)
Czyli podany ułamek jest nieskracalny.

1. Zalozmy, ze NWD(a+c,b+d)=D, wtedy dla pewnych calkowitych, wzglednie pierwszych k,l mamy a+c=kD oraz b+d=lD, czyli
1=ad-bc=ab+ad-ba-bc=a(b+d)-b(a+c)=alD-bkD=D(al-bk), czyli D|1 => ulamek jest nieskracalny.