[Rozgrzewka OM][MIX] Łańcuszek olimpijski

[Elvis]

Do kasaty. Sorry za zamieszanie.

[Dumel]

powyższe zadanie może strasznie wygląda, ale naprawdę nie jest zbyt trudne więc dziwię się że nikt go nie rozwiązał
no cóż, już drugi raz przyblokowałem temat, więc może sam wyjdę z inicjatywą jego reaktywacji zarzucając tym oto zadankiem:

znajdź wszystkie funkcje \(\displaystyle{ f: \mathbb{N}\to\mathbb{N}}\) takie że dla dowolnych \(\displaystyle{ m,n\in\mathbb{N}}\)
\(\displaystyle{ ( (f(m))^2 + f(n) )| (m^{2} + n)^{2}}\)

[Swistak]

Czy w tym równaniu nie brakuje kwadratu po lewej stronie? Bo jest jeden zbędny nawias i ładniej by wyglądało jakby jednak tam był kwadrat .

[Dumel]

wszystko ok, nie ma zbędnego nawiasu a to nie jest równanie

[Elvis]

\(\displaystyle{ m=n=x: \qquad f(x)(f(x)+1) | x^2 (x+1)^2 \quad (1)}\)
Stąd wniosek, że
\(\displaystyle{ (2) \quad f(x) \neq 0}\) dla \(\displaystyle{ x \neq 0}\)
(po lewej stronie otrzymalibyśmy zero, po prawej nie). Korzystając z tego mamy:
\(\displaystyle{ m=0, \ n=1: \qquad f(0)^2 + f(1)|1 \Rightarrow f(0)^2 + f(1) = 1 \Rightarrow f(1)=1 \\
m=1: \qquad f(n)+1 | (n+1)^2}\)
Dla \(\displaystyle{ n=p-1}\), gdzie \(\displaystyle{ p}\) to liczba pierwsza, mamy \(\displaystyle{ f(p-1)+1|p^2}\), co daje trzy przypadki:
1. \(\displaystyle{ f(p-1)+1=1}\), co jest sprzeczne z (2).
2. \(\displaystyle{ f(p-1)+1=p^2}\), co podstawiamy do (1):
\(\displaystyle{ (p^2 - 1)p^2 | (p-1)^2 p^2 \Rightarrow p+1 | p-1}\) - sprzeczność
3. Musi być więc \(\displaystyle{ f(p-1) = p-1}\).

Wskazaliśmy więc dowolnie duże \(\displaystyle{ m}\) takie, że \(\displaystyle{ f(m)=m}\), co podstawieniu do wyjściowej równości daje \(\displaystyle{ m^2+f(n) | (m^2 + n)^2}\). Po uwzględnieniu
\(\displaystyle{ (m^2 + n)^2 = ((m^2 + f(n)) + (n-f(n)))^2 = \\
= (m^2 + f(n))^2 + 2 (m^2 + f(n))(n-f(n)) + (n-f(n))^2}\)
mamy \(\displaystyle{ m^2+f(n) | (n-f(n))^2}\). Jak wspomniałem, \(\displaystyle{ m}\) może być dowolnie duże, więc \(\displaystyle{ (n-f(n))^2 = 0 \Rightarrow f(n)=n}\).

Pozostaje sprawdzić, że funkcja tożsamościowa spełnia warunki.

Nowe:
Dowieść, że jeśli \(\displaystyle{ p}\) jest liczbą pierwszą dzielącą n-tą liczbę Fermata, to \(\displaystyle{ p = 2^{n+1}k + 1}\) dla pewnego \(\displaystyle{ k}\) naturalnego.
\(\displaystyle{ F_n = 2^{2^n}+1}\) - n-ta liczba Fermata

[tkrass]

Dumel, czy uznajesz 0 za liczbę naturalną? Jeśli nie Elvis, to nie możesz sobie podstawiać 0.

[Elvis]

Jeśli nie, to zamiast tego można:
\(\displaystyle{ m=n=1: \qquad f(1)(f(1)+1)|4}\)
Daje to trzy przypadki, jedynym rozsądnym jest \(\displaystyle{ f(1)=1}\). Sprawdzałeś, czy wszystko poza tym jest dobrze?

[tkrass]

Właściwie to nie czytałem rozwiązania, a zadanie tylko raz przeczytałem i też doszedłem do tego, że \(\displaystyle{ f(1)=1}\), a że nie miałem kartki pod ręką, to na tym poprzestałem. Jeśli korzystasz z zera tylko przy dowodzie tego faktu, to oczywiście nie mam zastrzeżeń.

[limes123]

Uwaga do nowego zadania.
Po udowodnieniu tego faktu mozna pokazac, ze \(\displaystyle{ F_n}\) ma dzielnik pierwszy wiekszy niz \(\displaystyle{ 2^{n+2}(n+1)}\) (ale to juz trudniejsze cwiczenie).

[tkrass]

Nowe:
Dowieść, że jeśli \(\displaystyle{ p}\) jest liczbą pierwszą dzielącą n-tą liczbę Fermata, to \(\displaystyle{ p = 2^{n+1}k + 1}\) dla pewnego \(\displaystyle{ k}\) naturalnego.
\(\displaystyle{ F_n = 2^{2^n}+1}\) - n-ta liczba Fermata

Temat umiera, trzeba go ratować!

Niech r będzie rzędem 2 modulo p. Mamy \(\displaystyle{ 2^{2^n} \equiv -1 (modp)}\) i \(\displaystyle{ 2^{2^{n+1}} \equiv 1 (modp)}\), więc \(\displaystyle{ r=2^{n+1}}\). Z małego Fermata r jest dzielnikiem p-1, co jest równoważne tezie.

Nowe:
Liczby naturalne m i n spełniają równość:
\(\displaystyle{ 3n^2+n=4m^2+m}\). Udowodnić, że \(\displaystyle{ n-m}\) jest kwadratem liczby naturalnej.

[XMaS11]

\(\displaystyle{ 3n^2+n=4m^2+m \Leftrightarrow \\
m^2=(n-m)(3(m+n)+1) \ (1) \Leftrightarrow \\
n^2=(n-m)(4(m+n)+1) \ (2)}\).
Mnożąc stronami \(\displaystyle{ (1)}\) z \(\displaystyle{ (2)}\) dostajemy, ze \(\displaystyle{ (3(m+n)+1)(4(m+n)+1)}\) jest kwadratem, jako że nawiasy te są względnie pierwsze, to każdy z nich jest kwadratem, co w razem z \(\displaystyle{ 1}\) daje, że \(\displaystyle{ n-m}\) również jest kwadratem.

Nowe
Na płaszczyźnie dany jest skończony zbiór punktów o całkowitych współrzędnych. Czy można pokolorować pewne punkty tego zbioru na czerwono, a pozostałe na biało tak, że dla każdej prostej \(\displaystyle{ L}\) równoległej do jednej z osi współrzędnych wartość bezwzględna różnicy pomiędzy liczbą punktów białych i czerwonych leżących na \(\displaystyle{ L}\) jest nie większa niż 1 ?

[Dumel]

jasne. posortujmy je od lewej do prawej, przy czym jeśli punkty są na tej samej prostej pionowej to "mniejszy" jest ten który jest wyżej.
teraz co drugi punkt kolorujemy na czerwono, a reszte na bialo. dowód poprawności tego kolorowania jest trywialny

Dana jest liczba naturalna \(\displaystyle{ n ­\le 2}\). Tablica \(\displaystyle{ n \ \times \ n}\) jest wypełniona
liczbami 0 i 1 w ten sposób, że każdy podzbiór n pól, z których żadne 2 nie leżą w jednej kolumnie ani w jednym wierszu zawiera co najmniej
jedno pole z liczbą 1. Dowieść, że istnieje i wierszy i j kolumn, gdzie
\(\displaystyle{ i + j ­\ge n + 1}\) takich, że na przecięciu każdego wiersza i każdej kolumny
jest liczba 1.

[XMaS11]

Miało nie być dwóch z rzędu z tego samego działu : <

-- 17 kwietnia 2010, 18:51 --

Poza tym przecież to kolorowanie nie działa..
Weźmy punkty (1,1), (1,2), (2,1) (2,2) i prosta y=2 ..

[limes123]

Do zadania XMaSa:
Mozna indukcyjnie. W kroku rozwazmy takie dwa przypadki:
1) istnieje prosta rownolegla do jednej z osi zawierajaca tylko jeden punkt. Wtedy go usuwamy, dla reszty stosujemy zalozenie indukcyjne i koloujemy "dobrze". Pozniej dodajemy usuniety punkt tak, zeby powstale kolorowanie tez bylo dobre (oczywiscie jest to mozliwe, bo roznice sa na wartosc bezwzgledna mniejsze lub rowne 1).
2) kazda taka prosta zawiera 0 lub wiecej niz jeden punkt. Skoro kazda zawiera wiecej niz 1, to mozemy wybrac sobie cykl punktow dlugosci parzystej (nieparzystej dlugosci tez moze byc, niewiele to zmieni dowod) i kolorujemy na czarna o bialo na zmiane. Pozniej dla zbioru punktow bez naszego cyklu stosujemy zalozenie i dostajemy dobre kolorowanie.
Do zadania Dumla:
to jest Zwardon 2008 i chyba nie ma sensu zeby tutaj pisac rozwiazania (bo dowod, nawet jesli zmieniony, i tak bedzie przeformułowaniem dowodu tw. Halla lub tylko powolaniem sie na nie). W kazdym razie po odpowiednich spostrzezeniach teza wynikac bedzie z zaprzeczenia tw. Halla.


Zadanie.
Pokazac, ze zbior dzielnikow pierwszych niestalego wielomianu w wspolczynnikach calkowitych jest nieskonczony.


[Edit]
I tresc zadania Dumla jest chyba zle przepisana (chodzi o nierownosc).

[Dumel]

Poza tym przecież to kolorowanie nie działa..
Weźmy punkty (1,1), (1,2), (2,1) (2,2) i prosta y=2 ..

zapomniałem że proste poziome też mogą być :/ i do tego robiłem że wartość bezwzględna ilości punktów leżących na lewo i na prawo jest co najwyżej 1 wiec zupełnie inne zadanie

[Edit]
I tresc zadania Dumla jest chyba zle przepisana (chodzi o nierownosc).

tak, była w złą stronę