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.
Zbadamy iloczyn \(\displaystyle{ x \cdot y = x(2310-x) = 2310x-x^2}\)
Jeżeli iloczyn ten miałby byc podzielny przez \(\displaystyle{ 2310}\) to \(\displaystyle{ \exists_{k \in Z^+} k=\frac{2310x-x^2}{2310}}\)
Skoro jeden z elementów różnicy jest podzielny przez 2310 to i drugi element musi też być podzielny aby całość była podzielna. Czyli \(\displaystyle{ 2310|x^2,}\) ale \(\displaystyle{ 2310=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11}\) wobec tego \(\displaystyle{ x=2310 \cdot t}\) dla każdego \(\displaystyle{ t}\) całkowitego dodatniego, \(\displaystyle{ y}\) wychodzi ujemny lub równy 0, co stoi w sprzeczności z początkowym założeniem
\(\displaystyle{ a > b}\), więc \(\displaystyle{ a-1 \ge b}\), \(\displaystyle{ 4a-4 \ge 4b}\)
\(\displaystyle{ a^2 - (a-2)^2 = 4a - 4 \ge 4b = a^{2} - p^{2}}\)
To daje \(\displaystyle{ p^{2} \ge (a-2)^{2}}\)
Oczywiście, również \(\displaystyle{ p^{2} < a^{2}}\)
Daje to nam przypadki \(\displaystyle{ p = a-1}\) i \(\displaystyle{ p = a-2}\), czyli \(\displaystyle{ a^{2} - 2a + 1 = a^{2} - 4b \\
a - 2b = 0,5}\) co jest niemożliwe, i \(\displaystyle{ a^{2} - 4a + 4 = a^{2} - 4b\\
a - b = 1}\) \(\displaystyle{ q^{2} = b^{2} - 4a = b^{2} - 4(b+1) = (b-2)^{2} - 8}\) \(\displaystyle{ (b-2-q)(b-2+q) = 8}\), a ponieważ czynniki są tej samej parzystości, zaś prawy jest nieujemny, to \(\displaystyle{ b-2-q = 2}\) i \(\displaystyle{ b-2+q = 4}\), co daje parę \(\displaystyle{ b = 5, a=6}\), która jak sprawdzamy spełnia założenia.
21:
Najpierw przykład dla \(\displaystyle{ n=4}\):
Spełniają zbiory \(\displaystyle{ A,B,C,D}\) takie, że \(\displaystyle{ A = \{1,2,3,4,1+16,2+16,3+16,4+16,...\}}\) \(\displaystyle{ B = \{5,6,7,8,...\}}\) \(\displaystyle{ C = \{...\}}\) \(\displaystyle{ D = \{...\}}\).
Pokażemy, że dla \(\displaystyle{ 3}\) rozmieszczenie nie istnieje.
Będziemy w kolejnych krokach rozmieszczać liczby w trzech zbiorach \(\displaystyle{ A,B,C}\). Zawsze będziemy to robić na jedyny możliwy sposób lub na jeden z równoważnych (np. na początku \(\displaystyle{ 1}\) BSO może wylądować gdziekolwiek). Nie będę się rozpisywał dokładnie z czego korzystam bo to za długo zajmie a lubimy krótkie rozwiązania, a to zawsze łatwo zobaczyć.
I tak: \(\displaystyle{ A: 0 \\
B: 5 \\
C: 12 \\
B: 7 \\
A: 17}\)
Teraz przerwijmy na chwilę i zaobserwujmy, że dla każdego \(\displaystyle{ k \in \{A \cup B \cup C \}}\) potrafimy wskazać jedyny słuszny zbiór dla \(\displaystyle{ k+2}\), a także będzie on taki sam jak dla \(\displaystyle{ k}\):
\(\displaystyle{ A: 19 \\
C: 14 \\
A: 2 \\
B: 9}\)
Wszystko się przesunęło o \(\displaystyle{ 2}\) do przodu, a więc można to powtórzyć i powtarzać dowolnie dużą ilość razy. Dostalibyśmy jednak na przykład w pewnym momencie, że \(\displaystyle{ 12}\) należy do zbioru \(\displaystyle{ A}\), a to jest sprzeczne z obecnością tam \(\displaystyle{ 19}\).
Zaprzeczenie tym bardziej działa dla mniejszych \(\displaystyle{ n}\).
W miejscu zwinięcia do \(\displaystyle{ 5!}\) można było zwinąć od razu do \(\displaystyle{ 8!}\) od razu (wykorzystując liczbę \(\displaystyle{ 48}\)) ale zdecydowałem się na metode małych kroków
Nie wiem czy o to chodziło autorowi zadania czy może o sposób bardziej "magiczny"...
Prosty fakt: Jeśli pewne \(\displaystyle{ 2}\) liczby z naszego zbioru nie są względnie pierwsze, to można je podzielić przez NWD i tak powstałe liczby wstawić zamiast nich. Więc zakładamy że są, a to już 1a.
Z \(\displaystyle{ k \equiv 4 \pmod{5}}\) mamy \(\displaystyle{ n=100l+42}\), albo \(\displaystyle{ n=100l+92}\) i w tym drugim przypadku dostaniemy rozumując analogicznie \(\displaystyle{ n=192}\)
to tylko wstep...
Takie \(\displaystyle{ n}\) to bedzie \(\displaystyle{ n > 9}\) bo w rozkładzie \(\displaystyle{ \{1, 2, 3, 4, 5, 6, 7, 8, 9 \}= \{ 1, 3, 5, 7, 9 \} \cup \{ 2, 4, 6, 8 \}}\) w zadnym z podzbiorów nie ma (!?? ) takiej pary.
Ale np gdy \(\displaystyle{ n \geq 180}\), to jeden ze składników ma dwa elementy z tych: \(\displaystyle{ 60 , \ 60 \cdot 2, \ 60 \cdot 3}\)
a co no to komputer.... ?
\(\displaystyle{ n\le 60}\) , bo liczby \(\displaystyle{ 15,30,60}\) parami spełniają własność.
Jeśli \(\displaystyle{ n<60}\) to już się robi problem, bo trzeba z pomocą komputera próbować. Rozważmy graf o \(\displaystyle{ 59}\) wierzchołkach ponumerowanych od \(\displaystyle{ 1}\) do \(\displaystyle{ 59}\). Kiedy liczby \(\displaystyle{ a,b<60}\) spełniają własność to łączymy krawędzią wierzchołki o numerach \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Z pomocą komputera sprawdzam (Excel wystarczy ), które wierzchołki są połączone i rysujemy graf: . Nie zamieściłem wierzchołków, które nie są połączone z żadnym innym wierzchołkiem. Widać, że graf jest dwudzielny (można podzielić na dwa podzbiory tak, aby krawędzie łączyły wierzchołki z różnych podzbiorów), bo wszystkie cykle są nieparzystej długości
