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.
Bez straty ogólności możemy założyć, że \(\displaystyle{ a\ge b\ge c}\). Gdyby było \(\displaystyle{ c>6}\), to lewa strona byłaby mniejsza od jedynki, a prawa większa. Stąd \(\displaystyle{ c\le 6}\) i pozostaje rozpatrzyć sześć przypadków.
Dla \(\displaystyle{ c=1}\) równanie jest równoważne: \(\displaystyle{ (a+1)(b+1)=2}\)
i nie ma ono rozwiązań w liczbach naturalnych.
Dla \(\displaystyle{ c=2}\) równanie jest równoważne: \(\displaystyle{ 2=3(a+b)}\)
i ono również nie ma rozwiązań w liczbach naturalnych.
Dla \(\displaystyle{ c=3}\) równanie jest równoważne: \(\displaystyle{ (a-5)(b-5)=22}\)
skąd \(\displaystyle{ a-5=22, b-5=1}\) lub \(\displaystyle{ a-5=11, b-5=2}\). Otrzymujemy więc rozwiązania \(\displaystyle{ (27,6,3)}\) i \(\displaystyle{ (16,7,3)}\).
Dla \(\displaystyle{ c=4}\) równanie jest równoważne: \(\displaystyle{ (2a-7)(2b-7)=41}\)
skąd \(\displaystyle{ 2a-7=41, 2b-7=1}\) czyli mamy rozwiązanie \(\displaystyle{ (24,4,4)}\)
Dla \(\displaystyle{ c=5}\) równanie jest równoważne: \(\displaystyle{ 9ab+8=27(a+b)}\)
i nie ma ono rozwiązań, bo lewa strona nie dzieli się przez trzy, a prawa tak.
Dla \(\displaystyle{ c=6}\) równanie jest równoważne: \(\displaystyle{ (4a-11)(4b-11)=97}\)
skąd \(\displaystyle{ 4a-11=97, 4b-11=1}\), ale wtedy \(\displaystyle{ b>c}\) więc odrzucamy (lub jak kto woli - już takie rozwiązanie uwzględniliśmy).
Ostatecznie otrzymujemy więc rozwiązania \(\displaystyle{ (27,6,3),(16,7,3),(24,4,4)}\) oraz oczywiście wszystkie ich permutacje. Jeśli zaś uznajemy, że zero jest naturalne, to dochodzi jeszcze rozwiązanie \(\displaystyle{ (1,1,0)}\) i wszystkie jego permutacje.
niech \(\displaystyle{ X}\) to środek okręgu wpisanego w \(\displaystyle{ ABD}\), \(\displaystyle{ Y,Z,T}\) to przecięcia \(\displaystyle{ EF}\) z \(\displaystyle{ AD}\), \(\displaystyle{ DF}\) i \(\displaystyle{ BC}\)
wtedy \(\displaystyle{ (B,I;Z,E) = (T,Y;F,E) = -1 = (B,I;X,E)}\) (ostatnia równość wynika z założenia o kącie \(\displaystyle{ BAC}\)) zatem \(\displaystyle{ X=Z}\) zatem skoro \(\displaystyle{ DX}\) jest dwusieczną kąta \(\displaystyle{ IDB}\), to kąt \(\displaystyle{ EDX}\) jest prosty (użyłem lematów ze strony piętnastej z tamtego pdfa)
Szukamy \(\displaystyle{ m}\) takiego, że: \(\displaystyle{ 7m^{25}\equiv 10 \pmod{83}}\)
co po pomnożeniu stronami przez \(\displaystyle{ 12}\) daje: \(\displaystyle{ m^{25}\equiv 37 \pmod{83}\quad (*)}\)
Oczywiste jest, że takie \(\displaystyle{ m}\) nie może dzielić się przez \(\displaystyle{ 83}\), tak więc z Małego Twierdzenia Fermata wiemy, że: \(\displaystyle{ m^{82}\equiv 1 \pmod{83}}\)
Po podniesieniu \(\displaystyle{ (*)}\) stronami do \(\displaystyle{ 23}\) otrzymujemy zatem: \(\displaystyle{ 37^{23}\equiv m^{25\cdot 23} = m^{7\cdot 82+1} \equiv m \pmod{83}}\)
Stąd zaś wniosek, że najmniejszym szukanym \(\displaystyle{ m}\) jest \(\displaystyle{ 37^{23}\mod 83}\)
Reszta to już tylko rachunki: \(\displaystyle{ 37^2= 1369 \equiv 41 \pmod{83} \\
37^3 \equiv 37\cdot 41 = 1517\equiv 23 \pmod{83} \\
37^4 \equiv 37 \cdot 23 = 851 \equiv 21 \pmod{83} \\
21^2 = 441 \equiv 26 \pmod{83} \\
21^4 \equiv 26^2 = 676 \equiv 12 \pmod{83}\\
21^5 \equiv 21\cdot 12 = 252\equiv 3 \pmod{83}}\)
a w takim razie: \(\displaystyle{ 37^{23} = \left( 37^4\right)^5 \cdot 37^3 \equiv 21^5 \cdot 23 \equiv 3\cdot 23 = 69 \pmod{83}}\)
czyli najmniejszą liczbą o żądanej własności jest \(\displaystyle{ 69}\).
Schematycznie. Rozważmy zbiór liczb postaci \(\displaystyle{ am+n}\) gdzie \(\displaystyle{ m}\) i \(\displaystyle{ n}\) są liczbami całkowitymi z przedziału \(\displaystyle{ \left\langle 0, \ \left[ \sqrt{p}\right] \right\rangle}\). Jest ich więcej niż \(\displaystyle{ p}\), więc pewne dwie dają te same reszty w dzieleniu przez \(\displaystyle{ p}\) - \(\displaystyle{ am+n \equiv_{p} as+t \Leftrightarrow a\left(m-s\right)\equiv_{p}t-n}\). Oznaczmy \(\displaystyle{ x=t-n}\) i \(\displaystyle{ y=m-s}\), wtedy \(\displaystyle{ ay \equiv_{p} x \Leftrightarrow x^{2} \equiv_{p} -2y^{2} \Leftrightarrow p\mid x^{2}+2y^{2} \le 3\cdot \left[ \sqrt{p}\right] ^{2}<3p}\). Skąd \(\displaystyle{ x^{2}+2y^{2}=p \vee x^{2}+2y^{2}=2p}\).
Niech \(\displaystyle{ X_i}\) będzie zmienną losową przyjmując wartość \(\displaystyle{ 1}\) jeśli \(\displaystyle{ i}\)-ty zając przeżyje i \(\displaystyle{ 0}\) w przeciwnym wypadku. W zadaniu pytamy oczywiście o wartość oczekiwaną \(\displaystyle{ \sum_{i=1}^nX_i}\). Oczywiście też: \(\displaystyle{ \mathbb{E} \left( \sum_{i=1}^nX_i\right) =\sum_{i=1}^n \mathbb{E} X_i = nX_1= n\cdot P(X_1=1)}\)
Pozostaje więc policzyć szanse przeżycia pojedynczego zająca. Wszystkich możliwości wybrania celu przez myśliwych jest \(\displaystyle{ n^n}\), a takich, że ustalony zając przeżywa \(\displaystyle{ (n-1)^n}\). Stąd żądane prawdopodobieństwo to: \(\displaystyle{ P(X_1=1)=\left( 1- \frac 1n\right)^n}\)
a zatem wartość oczekiwana liczby zajęcy które przeżyją to \(\displaystyle{ n\cdot \left( 1- \frac 1n\right)^n}\).
Warto zauważyć, że dla dużych \(\displaystyle{ n}\) przeżywa średnio mniej więcej \(\displaystyle{ \frac ne}\) zajęcy.
Oznaczmy te sfery przez \(\displaystyle{ S_{}}\),\(\displaystyle{ S_{2}}\), \(\displaystyle{ S_{3}}\), \(\displaystyle{ S_{4}}\) i rozważmy inwersję względem dowolnej sfery o środku w punkcie styczności sfer \(\displaystyle{ S_{3}}\) i \(\displaystyle{ S_{4}}\). Sfery te przejdą na równolegle płaszczyzny \(\displaystyle{ P_{3}}\) i \(\displaystyle{ P_{4}}\). Pozostałe dwie sfery będą styczne do obu tych równoległych płaszczyzn (będą zatem przystające), a ich punkty styczności z płaszczyznami wyznaczają odcinek, który jest średnicą tychże sfer i jest prostopadły do obu tych płaszczyzn. Zatem te cztery punkty styczności leżą w jednej płaszczyźnie (gdyż leżą na dwóch prostych równoległych). A skoro w tej płaszczyźnie leżą też środki tych sfer i sfery te są styczne to ich punkt styczności również na niej leży. Skoro \(\displaystyle{ 5}\) punktów po inwersji leży w jednej płaszczyźnie to przed inwersją leżały na pewnej płaszczyźnie lub sferze przechodzącej przez środek sfery inwersyjnej czyli przez szósty punkt styczności c.k.d.
Wystarczy wziąć dowolne trzy punkty niewspółliniowe oraz czwarty leżący ściśle wewnątrz ich otoczki wypukłej (np. wierzchołki trójkąta równobocznego i jego środek ciężkości). Wtedy dowolna figura wypukła mająca na brzegu trzy pierwsze punkty - czwarty punkt ma ściśle wewnątrz (bo ta figura zawiera otoczkę wypukłą trzech pierwszych punktów).
Niestety schematycznie:
bez straty ogólności niech \(\displaystyle{ a\ge b\ge c, \ x\ge y\ge z}\) (i oczywiście z założenia wszystkie te liczby są dodatnie).
Z treści zadania wiemy ponadto, że \(\displaystyle{ a+b+c=x+y+z, \ abc=xyz}\)
Istnieją takie liczby nieujemne \(\displaystyle{ d, e}\), że \(\displaystyle{ a=x+d, \ c=z-e}\). Przypuśćmy nie wprost , że \(\displaystyle{ b>y:}\) to oznacza, że istnieje taka liczba dodatnia \(\displaystyle{ f}\), iż \(\displaystyle{ b=y+f}\)
Z warunku o równych sumach mamy wtedy \(\displaystyle{ e=f+d}\). Dalej dwukrotnie korzystamy z metody zbliżeń: przy ustalonej sumie liczb dodatnich ich iloczyn rośnie w miarę zbliżania się czynników. Czyli najpierw mamy \(\displaystyle{ (x+d)(z-e)<x(z+d-e) \ (*)}\),
wszak \(\displaystyle{ (x+d)+(z-e)=x+(z+d-e)}\) oraz \(\displaystyle{ |x+d-(z-e)|=x+e+d-z>x-(z+d-e)=|x-(z+d-e)|}\)
Wobec tego otrzymaliśmy też (mnożymy udowodnioną nierówność \(\displaystyle{ (*)}\) przez liczbę dodatnią \(\displaystyle{ y+f}\)) \(\displaystyle{ (x+d)(y+f)(z-e)<x(y+f)(z+d-e) }\)
Teraz analogicznie (zbliżamy czynniki przy ustalonej sumie) otrzymujemy, że \(\displaystyle{ (y+f)(z+d-e)<yz:}\)
oczywiście jest bowiem \(\displaystyle{ (y+f)+(z+d-e)=y+z}\), co wynika z wcześniej uzyskanej własności \(\displaystyle{ e=f+d}\), a ponadto mamy \(\displaystyle{ |(y+f) -(z+d-e)|=y+f-(z+d-e)>y-z=|y-z|}\)
Oczywiście taką nierówność mnożymy stronami przez dodatnie \(\displaystyle{ x}\) z zachowaniem zwrotu.
Dostaliśmy więc taki ciąg nierówności: \(\displaystyle{ (x+d)(y+f)(z-e)<x(y+f)(z+d-e)<xyz}\)
czyli \(\displaystyle{ abc<xyz}\), a to jest sprzeczność z założeniami. Zatem musi być \(\displaystyle{ b\le y}\)
Naprawdę analogicznie (ale dla klarowności to rozdzieliłem, to chyba nieuniknione przy takim podejściu) wykluczamy też drugą możliwość, której sobie nie życzymy: Przypuśćmy nie wprost, że\(\displaystyle{ b<y}\): zatem istnieje takie \(\displaystyle{ f>0}\), iż \(\displaystyle{ b=y-f}\).
Z warunku o równych sumach dostajemy wówczas \(\displaystyle{ d-e-f=0}\), tj. \(\displaystyle{ d=e+f}\)
Najpierw zbliżanie czynników przy ustalonej sumie daje nam: \(\displaystyle{ (x+d)(y-f)<x(y+d-f)}\),
wszak \(\displaystyle{ (x+d)+(y-f)=x+(y+d-f)}\) oraz \(\displaystyle{ |(x+d)-(y-f)|=x+d-(y-f)>x-(y+d-f)}\),
a także \(\displaystyle{ |(x+d)-(y-f)|=x+d-(y-f)>(y+d-f)-x}\),
więc z pewnością \(\displaystyle{ |(x+d)-(y-f)|>|x-(y+d-f)|}\).
Następnie dokładnie tak samo uzasadniamy, że \(\displaystyle{ (y+d-f)(z-e)<yz}\)
(korzystając po drodze z równości \(\displaystyle{ d=e+f}\))
i wobec tego \(\displaystyle{ x(y+d-f)(z-e)<xyz}\)
Reasumując, i w tym przypadku otrzymujemy nierówność \(\displaystyle{ abc<xyz}\), która jest sprzeczna z warunkami zadania.
Wobec tego udowodniliśmy, że \(\displaystyle{ b=y}\) i pozostaje wykazać, że gdy \(\displaystyle{ a\ge c>0, \ x\ge z>0}\) spełniają warunki \(\displaystyle{ a+c=x+z, \ ac=xz, \ a\ge x, \ z\ge c}\), to \(\displaystyle{ a=x, \ z=c}\). Ale to natychmiast wynika ponownie z metody zbliżeń, co kończy dowód.
Dla 6 punktów (A,B,C,D,E,F) jest możliwych \(\displaystyle{ {6 \choose 2}=15 }\) odcinków między nimi oraz \(\displaystyle{ {6 \choose 3}=20 }\)trójkątów, i każdy z odcinków jest wtedy wspólną krawędzią czterech trójkątów. Aby przy 10 odcinkach (40 krawędziach) nie istniał trójkąt, to każda trójka punktów musi być połączona dokładnie dwoma odcinkami (co da 40 krawędzi i 0 trójkątów).
Jeśli (przykładowe) punkty A i B nie będą połączone, to połączonymi muszą być punkty A i C, A i D, A i E, A i F, B i C, B i D, B i E oraz B i F, jednak te połączenia sprawiają, że żadne kolejne punkty nie mogą być połączone. Ergo, dla 10 odcinków istnieją trzy tworzące trójkąt.
PS
Powyższe nie oznacza, iż największa ilość odcinków bez trójkąta to 8. Istnieje układ 9 odcinków bez trójkąta (np: A i B, A i C, A i D, B i E, B i F, C i E, C i F, D i E, D i F,).
22:
Równanie można zapisać tak: \(\displaystyle{ 133(9+43k)+43(19-133k)=2014 \ \ \text{dla} \ \ k \in \ZZ}\)
więc najbliższe punktowi P punkty kratowe leżące na prostej to sam punkt P, a kolejne to \(\displaystyle{ (9+43, 19-133)}\) oraz \(\displaystyle{ (9-43, 19+133)}\)
Może przetłumaczę to na język bardziej zrozumiały dla ludzi o mniej wyrafinowanym myśleniu:
Otóż zapiszę zadanie tak:
Mamy \(\displaystyle{ 9}\) zadań do wykonania, przyjechało \(\displaystyle{ n}\) żeby je zrobić, Każy rozwizał trzy zadania, każdych dwóch matematyków rozwiązało więcej, niż trzy zadania (ale oczywiście mniej niż siedem zadań), żadnych trzech matematyków nie rozwiązało wszystkich zadań...
Po tym przetłumaczeniu z polskiego na nasze można do tego podejść tak, znaczy opiszę pewną konstrukcję w taki sposób, żeby tych matematyków było jak najwięcej, otóż:
\(\displaystyle{ A_{i}}\) - to matematyk rozwiązujący po trzy zadania, i teraz postaram się ich stworzyć jak najwięcej będę im przydzielał zadania:
\(\displaystyle{ A_{1}=\left\{ 1,2,3\right\} }\) - jest ich.: \(\displaystyle{ 1}\)
I teraz dziewiątki już tak nie możemy dołożyć bo wyjdzie na to, że mamy trójkę co rozwiązała wszystkie dziewięć zadań a to niezgodne z treścią...
zauważmy także , że wszystkie zbiory \(\displaystyle{ A }\) są trójelementowe , czyli, że każdy matematyk rozwiązał trzy zadania, oraz są parami różne , co znaczy, że żadnych dwóch matematyków nie rozwiązało tych samych zadań, a więc warunki zadania spełniają, z tej konstrukcji wynika że matematyków było:
\(\displaystyle{ 1+3+6+10+15+21=56}\)
No może komuś wyjdzie dłuższy łańcuch ...
Mi wyszedł taki...
Dodano po 1 godzinie 31 minutach 39 sekundach:
zad.3.
Ukryta treść:
W zadaniu trzecim też posłużę się pewną konstrukcją , może podzielę się tym co zaobserwowałem a mianowicie można na tych znajomościach zbudować graf , jeżeli dwóch się zna to jest między nimi jest krawędź...
I teraz kluczowa sprawa że na każdych dziesięciu jest klika trójelementowa czyli taki trójkąt...
Co nam to daje, otóż daje mam sporo wniosków...
Mianowicie postaram się pokazać jak to wygląda w "najgorszym" przypadku a najgorszy przypadek to taki, że graf ma jak najmniej krawędzi...
Zacznę od grafu co ma \(\displaystyle{ 10}\) punktów (wierzchołków) , czyli mamy tam klikę trójelementową i jest to przykład trywialny, też spełnia warunki zadania mimo iż w zadaniu jest \(\displaystyle{ n>10}\)
Zauważmy, że w tym jedenastoelementowym zbiorze mamy prawo wyrzucić tylko jeden element (wierzchołek) , żeby ostał się zbiór dziesięcioelementowy w którym jednak powinna zostać "klika" trójelementowa... Jednak jak widać w obu przypadkach obojętnie który wierzchołek wywalimy (obojętnie w którym przypadku) za każdym razem otrzymamy zbiór \(\displaystyle{ A}\) spełniający warunek zadania, i tak:
Jak widać w obu tych przypadkach każdy element zbioru \(\displaystyle{ B}\) jest incydentny z przynajmniej jednym elementem zbioru \(\displaystyle{ A}\)
Analogicznie będzie jeżeli nasza klika \(\displaystyle{ n-7}\) - elementowa rozpadać się będzie na mniejsze rozłączne kliki, wtedy też otrzymamy taki zbiór \(\displaystyle{ A}\), konstruując analogicznie jak wyżej...
Aneks do zadania 3.: (spostrzeżenia)
Otóż w podziale na kliki zbiorów n - elementowych z podzbiorami "10 elementowymi z klikami trójelementowymi w konstrukcji co opisałem w podziale na kliki i niższych rozmiarach można zauważyć partycjonowanie:
załóżmy, że klika trójelementowa ma rangę - \(\displaystyle{ 1}\)
czteroelementowa ma rangę dwa bo klika czteroelementowa rozkłada się na dwie kliki trójelementowe (jak w zadaniu)
A klika \(\displaystyle{ n}\) elementowa (powinno być zgodnie z treścią: \(\displaystyle{ n-7}\) elementowa , ale niech tam...)
ma rangę \(\displaystyle{ n-2}\) , można to ładnie zapisać:
\(\displaystyle{ r(K_{n})=n-2}\)
I wtedy tyle jest możliwych rozkładów na kliki w naszym zadaniu ile jest partycji.:\(\displaystyle{ P(n-2)}\) , oczywiście jescze musimy odrzucać czasem takie rozkłady, które dają więcej punktów niż liczy zbiór np:
dla zbioru \(\displaystyle{ N }\)z zadania \(\displaystyle{ 14}\) elementowego mamy:
Najwiękasza klika:
\(\displaystyle{ 14-7=7}\)
A więc siedmio-elementowa (pamiętajmy, kliki są niezależne)
\(\displaystyle{ 5=1+1+1+1+1}\) - "zużywamy" \(\displaystyle{ 15}\) wierzchołków (więc o jeden więcej niż w zadaniu) więc ten przypadek musimy odrzucić...
dla \(\displaystyle{ N}\) np trzynastoelementowego mamy:
\(\displaystyle{ 13-7=6}\)
Klika będzie największa.: \(\displaystyle{ K_{6}}\)
każdy przypadek zachowuje wierzchołki , bo trzeba pamiętać, że:
\(\displaystyle{ \sum_{}^{} w(K_{i}) \le n , w(K_{i})=i}\) - rozbijanie na kliki...
Chyba jak widać, jeden przypadek mi umknął w zadaniu 3 dla \(\displaystyle{ n=13}\) bo powinno być pięc rozbić a ja chyba zrobiłem cztery, ale to nie ma do rzeczy...
Dodano po 8 godzinach 56 minutach 29 sekundach:
zad. 21.
Ukryta treść:
W tym zadaniu możemy użyć grafów skierowanych: Możemy użyć macierzy sąsiedztwa \(\displaystyle{ a_{i,j}}\)
\(\displaystyle{ a_{i,j}=1}\) jeżeli \(\displaystyle{ i}\) śledzi \(\displaystyle{ j}\)
\(\displaystyle{ a_{i,j}=0}\) jeżeli \(\displaystyle{ i}\) nie śledzi \(\displaystyle{ j}\)
Macierz nie musi być symetryczna...
Skoro dziesięciu agentów zawsze się śledzi, to każdy wiersz macierzy sąsiedztwa musi zawierać ilość jedynek większą lub równą dziewięć...
Poza tym: \(\displaystyle{ a_{i,i}=0}\) - bo zakładam , że żaden agent nie śledzi sam siebie.
Ilość ścieżek (cykli) o długości \(\displaystyle{ 10 }\) musi być z warunków zadania ilość większa niż jeden...
czyli na głównej przekątnej macierzy.: \(\displaystyle{ A^{10} , a_{i,i}>0}\) , bo zawsze z warunków zadania mamy cykl zamknięty o długości dziesięć...
Więc: \(\displaystyle{ A^{11}}\) też powinna mieć wszystkie elementy na głównej przekątnej większe od zera...A co za tym idzie istnieją cykle o długości jedenaście...
