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.
Zauważmy, że wystarczy wykazać, że pewne kolejne liczby na okręgu sumują się do \(\displaystyle{ 100}\) lub \(\displaystyle{ 200}\) (jeśli jakieś sumują się do stu, to reszta do dwustu). Jeśli więc będziemy rozpatrywać sumy składające się z od jednego do stu składników, to wystarczy pokazać, że pewna jest podzielna przez \(\displaystyle{ 100}\) (co oznacza właśnie, że jest równa \(\displaystyle{ 100}\) lub \(\displaystyle{ 200}\)).
Ustalmy dowolną liczbę \(\displaystyle{ a_1}\) na okręgu i ponumerujmy pozostałe liczby zgodnie ze wskazówkami zegara \(\displaystyle{ a_1, a_2, \ldots , a_{100}, a_{101}}\). Rozpatrzmy sumy: \(\displaystyle{ a_1\\ a_1+ a_2\\ a_1+ a_2+ a_3\\ \ldots\\ a_1+ a_2 +\ldots +a_{100}}\)
Jeśli każda z nich daje inną resztę z dzielenia przez \(\displaystyle{ 100}\), to jedna jest podzielna przez \(\displaystyle{ 100}\) czyli koniec. Jeśli zaś pewne dwie sumy dają tę samą resztę, to ich różnica jest podzielna przez \(\displaystyle{ 100}\) oraz oczywiście ich różnica też jest sumą kolejnych liczb - czyli też koniec.
Gdyby natomiast liczb było tylko \(\displaystyle{ 100}\), to teza nie byłaby prawdziwa - wystarczy rozpatrzeć przypadek gdy wszystkie liczby są trójkami.
Gracz pierwszy ma strategię wygrywającą, tą strategią jest mówienie liczby o \(\displaystyle{ 11}\) większej niż podawał poprzednio. W \(\displaystyle{ 19}\) kolejce wygrywa. Schemat: \(\displaystyle{ 1\to [2,11]\to 12\to [13,22]\to 23\to [24,33]\to 34\to [35,44]\to 45\to [46,55]\to 56\to [57,66]\to 67\to [68,77]\to 78\to [79.88]\to 89\to [90,99]\to 100.}\)
Nie.
Pomalujmy na czerwono diagonale szachownicy (notacja analogiczna do szachowej): \(\displaystyle{ a7-d10, a3-h10, c1-j8, g1-j4}\)
Nietrudno policzyć, że czerwonych pól jest \(\displaystyle{ 24}\), nietrudno też zauważyć, że każdy prostokąt \(\displaystyle{ 4\times 1}\) pokrywa dokładnie jedno czerwone pole. Stąd wniosek, że na szachownicy zmieszczą się co najwyżej \(\displaystyle{ 24}\) takie prostokąty, co nie wystarczy do jej całkowitego pokrycia.
przemaluję koła i będę dowodził twierdzenia dla kół czarno-białych: 51 pól czarnych, 49 białych. ustalmy uwagę na wybranym czarnym sektorze wybranego koła. obracajmy to koło raz za razem o 1 sektor, 100 razy - podczas tego ruchu wybrany sektor napotka 51 czarnych sektorów drugiego koła i w 101 ruchu wróci na miejsce. ta sama obserwacja dotyczy 51 pozostałych sektorów, a zatem łączna liczba spotkań to \(\displaystyle{ 51 \cdot 51}\). z drugiej strony, liczba ta jest równa sumie \(\displaystyle{ w_1+w_2+\ldots +w_{100}}\), gdzie \(\displaystyle{ w_i}\) to sumaryczna liczba spotkań podczas jednego obrotu (tj. łączna liczba pasujących do siebie sektorów czarnych w i-tym ustawieniu). ponieważ \(\displaystyle{ 51^2>2600}\), musi istnieć takie \(\displaystyle{ i}\), że \(\displaystyle{ w_i>27}\). oznacza to, że przy pewnym ustawieniu kół co najmniej 27 sektorów czarnych pasuje do siebie. ale jeżeli pasuje do siebie dokładnie \(\displaystyle{ 27+k}\) sektorów czarnych, to pozostałe \(\displaystyle{ 24-k}\) sektory czarne naszego koła muszą odpowiadać sektorom białym na drugim kole. jednak wówczas \(\displaystyle{ 25+k}\) sektorów białych drugiego koła musi odpowiadać takiej liczbie sektorów na naszym kole. łącznie pasuje do siebie co najmniej \(\displaystyle{ 52+2k}\) sektory
\(\displaystyle{ n = 100}\) Wystarczy dowieść, że \(\displaystyle{ \frac{1}{20} \ge \frac{ \sqrt{n} }{100+n}}\) czyli \(\displaystyle{ 100+n \ge 20 \sqrt{n}}\) a to daje \(\displaystyle{ (100-n)^{2} \ge 0}\)
Mala popraweczka, powinno być \(\displaystyle{ (10-\sqrt{n})^{2} \ge 0}\)
Zauważmy, że w zbiorze nie może być dwóch kolejnych liczb, ponieważ dla \(\displaystyle{ a=n+1,b=n}\) mamy: \(\displaystyle{ \frac{a+b}{a-b}= 2n+1 \in \mathbb{Z}}\)
Nie może też być liczb różniących się o dwa, bo dla \(\displaystyle{ a=n+2, b=n}\) mamy: \(\displaystyle{ \frac{a+b}{a-b} =n+1\in \mathbb{Z}}\)
Stąd wniosek, że różnice między kolejnymi liczbami zbioru są równe co najmniej \(\displaystyle{ 3}\), skąd morał, że zbiór liczy co najwyżej \(\displaystyle{ \left\lfloor \frac{100}{3} \right\rfloor =33}\) elementów. Nietrudno wskazać dobry zbiór o tej liczbie elementów, jest to na przykład: \(\displaystyle{ \left\{ 3k+1: \ k=1,2,\ldots 33\right\}}\)
Istotnie, mamy bowiem dla \(\displaystyle{ a=3k+1, b=3l+1}\): \(\displaystyle{ \frac{a+b}{a-b} = \frac{3(k+l)+2}{3(k-l)}\notin \mathbb{Z}}\)
niech W oznacza zdanie "wśród każdej czwórki osób jest taka, która zna trzy pozostałe". pokażę, że
a) istnieje co najmniej jedna osoba, która zna wszystkie osoby
b) niemożliwe jest, by liczba osób, znających wszystkie osoby, była mniejsza od 97 ad a) załóżmy, że takiej osoby nie ma. wobec tego, istnieją dwie różne osoby A, B, które nie znają się wzajemnie. weźmy teraz pod uwagę dowolną trzecią osobę C, różną od A i B. albo wśród pozostałych osób (różnych od A i B) istnieje osoba D, której C nie zna, albo nie. w pierwszym przypadku mamy sytuację: A i B nie znają się wzajemnie (relacja "x zna y" jest symetryczna), C i D nie znają się wzajemnie. to jednak jest sprzeczne z W - wśród naszych czterech osób nie ma takiej, która znałaby trzy pozostałe.
w drugim przypadku mamy sytuację taką: C zna wszystkie osoby różne od A i B. ponieważ C nie zna wszystkich osób, musi nie znać A lub B. załóżmy, dla ustalenia uwagi, że nie zna A. rozważamy wszystkie osoby różne od A, B, C - ponieważ każda z nich zna C (bo C je zna), to któraś z nich (ba! każda) musi nie znać A lub B. ale to znów przeczy W.
pokazuje to, że musi istnieć osoba, która zna wszystkie ad b) załóżmy, że liczba osób, które znają wszystkie osoby, nie przekracza 96 - grupę tych osób oznaczmy Z. istnieją zatem co najmniej cztery osoby, które nie znają wszystkich pozostałych - grupę tych osób oznaczmy N. weźmy dowolną osobę A z grupy N - istnieje osoba B, której A nie zna. B też musi być w grupie N - w przeciwnym wypadku znałaby A. weźmy osobę C z grupy N, różną od A i B. albo w grupie N istnieje osoba D różna od A i B, której C nie zna, albo nie. w pierwszym przypadku, podobnie jak w a) mamy sprzeczność z W. w drugim, sytuacja jest taka: w grupie N istnieją osoby A i B, które nie znają się wzajemnie oraz osoba C, która zna wszystkie osoby z N różne od A i B. zatem C musi nie znać A lub B. załóżmy, że nie zna A. weźmy dowolną osobę D z grupy N, inną niż A i B - D zna wszystkie osoby z Z (bo one znają D) oraz D zna C. zatem C musi nie znać A lub B. ale to znów przeczy W. dowodzi to, że liczba osób, które znają wszystkie osoby musi być równa co najmniej 97.
Podzielmy prostokąt na cztery części osiami symetrii równoległtmi do boku. Podzielą go na cztery prostokąty podobne w skali \(\displaystyle{ k=2}\). jako,że żądane koła też reprezentują wyjściowe w tej samej skali podobieństwa, wystarczy skopiować te pokrycia z wyjściowej sytuacji czterokrotnie.
Tak samo otrzymamy dla trójkątów, bo te też możemy podzielić na cztery równe części łącząc odcinkami równoległymi do odpowiednich boków przechodzącymi przez środki pozostałych boków, co wynika z tw. Talesa.
Przyjrzyjmy się algorytmowi jej wypełnienia. Po wpisaniu dwójek do drugiej kolumny trzeba było sprawdzić ile w tej kolumnie pojawi się trójek. W tym celu patrzymy na wiersz zaczynający się trójką i widać, że szukana liczba wystąpień trójki to \(\displaystyle{ 5-3=2}\) czyli numer ostatniego pojawienia się trójki minus numer ostatniego pojawienia się dwójki.
W ogólności robimy to tak samo: zastanawiamy się ile w drugiej kolumnie pojawi się liczb \(\displaystyle{ k}\), a w tym celu patrzymy na wiersz zaczynający się od \(\displaystyle{ k}\) i od ostatniej liczby w tym wierszu odejmujemy ostatnią liczbę w wierszu wyżej. Wpisujemy żądaną ilość liczb \(\displaystyle{ k}\) do drugiej kolumny i uzupełniamy trzecią kolumnę dodając w każdym miejscu liczbę z lewej i liczbę powyżej (z oczywistych względów).
ponieważ \(\displaystyle{ 10^{100}+1=(10^4)^{25}+1=((10^4)^{24}-\ldots+1)}\) i \(\displaystyle{ 10^4+1=73\cdot 137}\) widać, że wystarczy zbadać, czy któraś z liczb pierwszych mniejszych od 73 nie jest dzielnikiem badanej liczby. mozolne badanie z wykorzystaniem MTF(ermata) oraz kongruencji pokazuje, że nie, tj. 73 jest najmniejszym dzielnikiem pierwszym liczby \(\displaystyle{ 10^{100}+1}\). faktoryzacja z wykorzystaniem środowiska sage (sagemath.org) to potwierdza
Oczywiście musi zachodzić dla pewnego naturalnego \(\displaystyle{ a}\) równość \(\displaystyle{ 10a=z}\). Mnożąc równanie pierwsze przez \(\displaystyle{ 2}\) i odejmując to równanie stronami od drugiego otrzymujemy, że \(\displaystyle{ 19a=100+3y}\). Wynika stąd, że \(\displaystyle{ a \ge 6}\) a z pierwszych dwóch równań mamy, że \(\displaystyle{ a \le 9}\). Rozpatrując kolejno \(\displaystyle{ a=6,7,8,9}\) widzimy, że dla \(\displaystyle{ a=7}\) istnieje jedynie rozwiązanie. \(\displaystyle{ x=19, y=11, z=70}\)
Podzielmy sobie podkreślone liczby na trzy sumy. Pierwsza - A - to liczby podkreślone za pierwszym razem, druga - B - to liczby podkreślone za drugim razem i trzecia - C - to liczby podkreślone za trzecim razem. Sumy te są rozłączne, to znaczy nie zawierają tych samych liczb - jeżeli liczba została już podkreślona za drugim razem, to nie podkreślamy jej ponownie za trzecim razem, nawet jeśli spełnia warunek.
Spójrzmy na liczby z sumy C. Jeżeli jakaś liczba się tam znajduje, to dwie następujące po niej na pewno są w którejś z dwóch pozostałych. Udowodnię ten fakt.
Weźmy dowolną liczbę \(\displaystyle{ c}\) z sumy C. Jest ona ujemna - bo liczby wypisane są albo dodatnie, albo ujemne, a dodatnie są w sumie A. Następna po niej liczba \(\displaystyle{ x}\) może być oczywiście albo dodatnia albo ujemna. Jednakże suma \(\displaystyle{ x+c}\) nie jest dodatnia - inaczej \(\displaystyle{ c}\) byłoby podkreślone za drugim razem. Wynika z tego, że kolejna po tych dwóch liczbach liczba musi być dodatnia \(\displaystyle{ a}\), tak aby suma \(\displaystyle{ c+x+a}\) była dodatnia. Oznacza to, że \(\displaystyle{ a}\) jest podkreślone za pierwszym razem. Ale ponieważ wspomniana suma jest dodatnia, a liczba \(\displaystyle{ c}\) jest ujemna, to liczba \(\displaystyle{ x}\) musiała być podkreślona za drugim lub pierwszym razem, gdyż suma \(\displaystyle{ a+x}\) jest dodatnia. Co kończy dowód tego faktu.
Dla każdej liczby z sumy C dwie następujące po niej przerzucamy teraz do sumy C i dodajemy je do tych właśnie liczb, po których stoją. Łączymy więc trójki. Widzimy teraz, że suma C jest dodatnia, ponieważ wszystkie liczby, które się teraz w niej znajdują, są dodatnie.
Uszczupliliśmy trochę sumy A i B. Weźmy teraz liczby z sumy B. Te, które zostały - o ile jakieś zostały. Liczby stojące przed nimi są dodatnie - co jest w miarę oczywiste. Znajdują się więc w sumie A. Robimy więc jeszcze raz to samo - wywalamy je z sumy A i wrzucamy do B, dodając do tych liczb które stoją przed nimi. Znowu dostajemy sumę dodatnich liczb, która musi być dodatnia, o ile zawiera jakieś liczby.
Jeżeli w sumie A zostały jakieś liczby, to są one dodatnie, a więc suma też musi być dodatnia. Jeżeli w sumie A nie ma żadnych liczb, to tylko dlatego, że wyjęliśmy je przy którymś z poprzednich kroków, co z kolei oznacza, że w którejś z pozostałych sum są jakieś liczby. Wynika z tego, że przynajmniej jedna z sum A, B, C jest dodatnia, a pozostałe są nieujemne. Oznacza to, że A+B+C jest dodatnie.
