[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

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.
binaj
Użytkownik
Użytkownik
Posty: 547
Rejestracja: 20 lis 2007, o 15:03
Płeć: Mężczyzna
Lokalizacja: Bielsko-Biała
Podziękował: 37 razy
Pomógł: 120 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: binaj »

Może zmienimy temat na rozgrzewka przed LXI OM?
limes123 pisze: Dla kazdego naturalnego k>1 istnieje r takie, ze \(\displaystyle{ k|[r^n]+1}\) dla kazdego n naturalnego.
Rozważmy ciąg \(\displaystyle{ (A_n)}\)dany wzorem: \(\displaystyle{ A_n=k^na^n+ \frac{1}{a^{n}}}\)

Zauważmy, ze dla \(\displaystyle{ n \ge 3}\) \(\displaystyle{ A_n=A_{1}A_{n-1}-kA_{n-2}}\)

Niech \(\displaystyle{ A_1=k^2}\), jako równanie ze zmienną \(\displaystyle{ a}\) ma 2 rozwiązania, jedno (nazwijmy go \(\displaystyle{ X}\)) jest na pewno większe od \(\displaystyle{ 1}\), zatem \(\displaystyle{ 0<\frac{1}{X^{n}}<1}\) dla każdego \(\displaystyle{ n}\)

czyli \(\displaystyle{ [k^{n}X^{n}]+1=k^{n}X^{n}+\frac{1}{X^{n}}=A_n}\)

Zauważmy, że liczba \(\displaystyle{ r=kX}\) spełnia warunki zadania, bowiem sprawdzając dla \(\displaystyle{ n=2}\) a następnie indukcyjnie wykorzystując wzór rekurencyjny dla \(\displaystyle{ n \ge 3}\) : \(\displaystyle{ A_n=A_{1}A_{n-1}-kA_{n-2}=k^{2}A_{n-1}-kA_{n-2}}\)

dostajemy, że dla każdego \(\displaystyle{ n}\):

\(\displaystyle{ k|A_{n}=[k^{n}X^{n}]+1}\) czego należało dowieść

co do pierwszego zadania limesa to w tym pliku
(zad 6.) jest rozwiązanie

Teraz 2 zadanka:

1. Niech \(\displaystyle{ x,y,z}\) będą takimi liczbami całkowitymi dodatnimi, że liczba \(\displaystyle{ \frac{x+1}{y} + \frac{y+1}{z} + \frac{z+1}{x}}\) jest calkowita. Udowodnić, że \(\displaystyle{ NWD(x,y,z) \le \sqrt[3]{xy+yz+zx}}\)

2. Udowodnić, że ciąg:

\(\displaystyle{ {2009 \choose 2009}, {2010 \choose 2009}, {2011 \choose 2009} ...}\)

jest okresowy modulo \(\displaystyle{ 2009}\).
Awatar użytkownika
smigol
Użytkownik
Użytkownik
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: smigol »

1. Pawłowski? czy mi się wydaje?
Ukryta treść:    
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Swistak »

W Pawłowskim było to zadanie, ale tylko dla dwóch zmiennych. Bodajże zad. nr. 1.11 z Rosji.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

IMO troche za proste na I etap, ale w temacie cicho więc nie zaszkodzi wrzucić :
znaleźć wszystkie liczby pierwsze \(\displaystyle{ 5 \le p<q<r}\) spełniające układ nierówności:
\(\displaystyle{ 2p^2-r^2 \ge 49}\)
\(\displaystyle{ 2q^2-r^2 \le 193}\)
Django
Użytkownik
Użytkownik
Posty: 200
Rejestracja: 25 sty 2009, o 13:37
Płeć: Mężczyzna
Lokalizacja: Częstochowa/Kraków
Podziękował: 30 razy
Pomógł: 12 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Django »

Dumel pisze:IMO troche za proste na I etap, ale w temacie cicho więc nie zaszkodzi wrzucić :
znaleźć wszystkie liczby pierwsze \(\displaystyle{ 5 \le p<q<r}\) spełniające układ nierówności:
\(\displaystyle{ 2p^2-r^2 \ge 49}\)
\(\displaystyle{ 2q^2-r^2 \le 193}\)
Nie jestem w 100% pewien rozwiązania, ale to chyba będzie tak:
Mnożąc przez -1 drugą z nierówności i dodając stronami mamy:
\(\displaystyle{ 2p^2 - 2q^2 \ge -146}\)
Równoważnie:
\(\displaystyle{ (q-p)(q+p) \le 73}\)
I teraz bawimy się w zgadywanie co to za liczby pierwsze p i q, które spełniają tę nierówność. Są to następujące pary \(\displaystyle{ (p,q)}\):
\(\displaystyle{ (5,7);(7,11);(11,13);(17,19)}\)
Teraz pozostaje nam sprawdzić, czy istnieje \(\displaystyle{ r > q > p}\), które spełnia układ nierówności wraz z daną parą. Sprawdzamy pierwszą:
\(\displaystyle{ 50 - r^2 \ge 49}\)
\(\displaystyle{ r \le 1}\)
Czyli r do tej pary nie istnieje, pierwszą parę zatem wykluczamy.
Sprawdzamy drugą:
\(\displaystyle{ 98 - r^2 \ge 49}\)
\(\displaystyle{ r \le 7}\)
Ponownie sprzeczność, bo zgodnie z założeniem \(\displaystyle{ p<q<r}\), a tu mamy \(\displaystyle{ 7<11<7}\)
Sprawdzamy trzecią:
\(\displaystyle{ 242 - r^2 \ge 49}\)
\(\displaystyle{ r \le \sqrt{193}}\)
Sprzeczność, bo \(\displaystyle{ r \le 13}\), a zgodnie z założeniem \(\displaystyle{ p<q<r}\), a tu mamy \(\displaystyle{ 11<13<13}\)
Ostatnia para:
\(\displaystyle{ 578 - r^2 \ge 49}\)
\(\displaystyle{ r \le 23}\)
Tu już nie ma sprzeczności, sprawdzamy zatem, czy trójka \(\displaystyle{ (17, 19, 23)}\) spełnia układ nierówności:
\(\displaystyle{ 2 \cdot 289 - 529 \ge 49 \Leftrightarrow 49 \ge 49}\)
\(\displaystyle{ 2 \cdot 362 - 529 \le 193 \Leftrightarrow 193 \le 193}\)
Zatem jedyna trójka liczb pierwszych spełniająca układ nierówności to \(\displaystyle{ (17, 19, 23)}\)
Pzdr
frej

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: frej »

Udowodnij, że wielomian \(\displaystyle{ W(x)=(x-a_1)^2(x-a_2)^2 \cdot \ldots \cdot (x-a_n)^2+1 \quad a_1, a_2, \ldots ,a_n \in \mathbb{Z}}\) nie jest iloczynem dwóch wielomianów o współczynnikach całkowitych dodatniego stopnia.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: patry93 »

Przepraszam za głupie pytanie
frej - to zadanie umieściłeś z myślą o przygotowanie się do II et. czy już finału (na co by nazwa wątku wskazywała )?
rozw.:    
-- 7 grudnia 2009, 18:02 --Przy okazji...
Piotr Rutkowski pisze: Niech \(\displaystyle{ r=ord_{3}p}\)
Co to oznacza?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: arek1357 »

Najlepiej chyba zrobić ze względu na indukcję po n dla n=1 wielomian jest nierozkładalny a dla n+1też
frej

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: frej »

patry93 pisze:Przepraszam za głupie pytanie
frej - to zadanie umieściłeś z myślą o przygotowanie się do II et. czy już finału (na co by nazwa wątku wskazywała )?
Raczej żeby odświeżyć temat, nie wydaje mi się, żeby te zadanie było zbyt trudne...
patry93 pisze: Niech \(\displaystyle{ r=ord_{3}p}\)
Co to oznacza?
To oznacza, że \(\displaystyle{ r}\) jest rzędem \(\displaystyle{ 3}\) modulo \(\displaystyle{ p}\), czyli najmniejszą taką liczbą \(\displaystyle{ d}\), że \(\displaystyle{ 3^d\equiv 1 \pmod{p}}\)
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Ponewor »

Trochę zadań się nazbierało w tym temacie
Dumel pisze:niech \(\displaystyle{ p>5}\) bedzie liczba pierwsza. pokazać ze w zbiorze \(\displaystyle{ \{p-n^2:n^2<p \}}\)
istnieja różne liczby \(\displaystyle{ a,b>1}\) takie ze \(\displaystyle{ a|b}\)
Ukryta treść:    
limes123 pisze:Niech A bedzie skonczonym zbiorem liczb pierwszych, a - liczba calkowita wieksza niz 1. Udowodnij, ze istnieje tylko skonczona liczba calkowitych dodatnich n takich, ze wszystkie dzielniki pierwsze \(\displaystyle{ a^n-1}\) sa w A.
Piotr Rutkowski pisze:Zwardoń 2007 - Na dwudziestu uczestników było 19 zer i jedna piątka za to zadanie...
Aż się wierzyć nie chce, że były problemy z zadaniem w którym można tak głośno huknąć z armaty.
Ukryta treść:    
szablewskil pisze:Udowdnij że dla dowolnych liczb naturalnych m,n jeżeli mn+1 jest podzielne przez 24 to m+n również jest podzielne przez 24
Ukryta treść:    
Zostało jeszcze parę zadań:
szablewskil pisze:Niech a,b będą takimi liczbami naturalnymi że \(\displaystyle{ a|b+1}\) oraz \(\displaystyle{ b|a^{2}-2}\). Udowodnij że liczba \(\displaystyle{ \frac{b+1}{2}}\) jest kwadratem pewnej lcizby całkowitej
limes123 pisze:Niech \(\displaystyle{ n\geq a_1>a_2>...>a_k}\) beda liczbami calkowitymi dodatnimi spelniajacymi \(\displaystyle{ NWW(a_i,a_j)\leq n}\) dla dowolnych roznych i,j z zbioru {1,2,...,k}. Udowodnij, ze \(\displaystyle{ ia_i\leq n}\) dla i=1,2,...,k.
binaj pisze:Udowodnić, że ciąg:

\(\displaystyle{ {2009 \choose 2009}, {2010 \choose 2009}, {2011 \choose 2009} ...}\)

jest okresowy modulo \(\displaystyle{ 2009}\).
Dumel pisze:znalezc wszystkie wielomiany \(\displaystyle{ P(x)}\) o wsp. rzeczywistych spelniajace dla kazdego \(\displaystyle{ x}\):
\(\displaystyle{ (x+1)^3P(x-1)-(x-1)^3P(x+1)=4(x^2-1)P(x)}\)
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 747 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: mol_ksiazkowy »

Wrzucajcie jakies ciekawe zadania, lematy, twierdzenia itd.
Wykazać, że jeżeli żadna z liczb \(\displaystyle{ a, a+d, a+2d, ….a+(n-1)d}\) nie dzieli się przez \(\displaystyle{ n}\), to \(\displaystyle{ d}\) i \(\displaystyle{ n}\) nie są względnie pierwsze.

i

Udowodnić, że: \(\displaystyle{ \sum_{i=2}^{n^k} \frac{1}{i} \geq k\sum_{i=2}^{n} \frac{1}{i}}\)
Zostało jeszcze parę zadań:
szablewskil napisał(a):
Niech a,b będą takimi liczbami naturalnymi że \(\displaystyle{ \frac{b+1}{a}}\) oraz \(\displaystyle{ \frac{a^2-2}{b}}\) sa całkowite. Udowodnij że liczba \(\displaystyle{ \frac{b+1}{2}}\) jest kwadratem pewnej liczby całkowitej.
Ukryta treść:    
Ostatnio zmieniony 30 lip 2013, o 16:08 przez mol_ksiazkowy, łącznie zmieniany 1 raz.
Awatar użytkownika
Msciwoj
Użytkownik
Użytkownik
Posty: 229
Rejestracja: 18 lut 2012, o 22:21
Płeć: Mężczyzna
Lokalizacja: Londyn
Podziękował: 4 razy
Pomógł: 36 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Msciwoj »

binaj pisze: Udowodnić, że ciąg:

\(\displaystyle{ {2009 \choose 2009}, {2010 \choose 2009}, {2011 \choose 2009} ...}\)

jest okresowy modulo 2009.
Ukryta treść:    
Z tym twierdzeniem:
mol_ksiazkowy pisze:Wykazać, że jeżeli żadna z liczb\(\displaystyle{ a, a+d, a+2d, ….a+(n-1)d}\) nie dzieli się przez \(\displaystyle{ n}\), to \(\displaystyle{ d}\) i \(\displaystyle{ n}\) są względnie pierwsze.
też jest coś nie tak... Tam jest coś na odwrót.

W tej postaci:
Ukryta treść:    
Ostatnio zmieniony 30 lip 2013, o 15:38 przez Msciwoj, łącznie zmieniany 1 raz.
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Ponewor »

Ad. Mściwój:    
Awatar użytkownika
Msciwoj
Użytkownik
Użytkownik
Posty: 229
Rejestracja: 18 lut 2012, o 22:21
Płeć: Mężczyzna
Lokalizacja: Londyn
Podziękował: 4 razy
Pomógł: 36 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Msciwoj »

Coś mam pecha do zadań dzisiaj, dwa próbowałem zrobić i oba nieprawdziwe, idę poczytać książkę.

Ponewor, dzięki, nie znałem tego. To oczywiście nie jest tak, że to wystarcza do zniszczenia tego zadania, trzeba jeszcze pokazać, że
Ukryta treść:    

I właśnie dlatego taki długi ten mój post był.
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Ponewor »

z tym, że się przejechałem ostro, bo okazuje się, że \(\displaystyle{ 2009}\) nie jest pierwsze, więc muszę to jakoś przerobić

-- 30 lip 2013, o 17:38 --

edit
och no dobrze, to jest prawdą dla wszystkich naturalnych.
Ukryta treść:    
-- 30 lip 2013, o 17:57 --
Ukryta treść:    
ODPOWIEDZ