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.
Dany jest wielomian \(\displaystyle{ W(x)}\) o współczynnikach całkowitych oraz ściśle rosnący ciąg liczb naturalnych \(\displaystyle{ a _{n}}\) taki że \(\displaystyle{ a _{n} \le W(n)}\) dla każdego \(\displaystyle{ n}\). Wykaż, że zbiór liczb pierwszych które dzielą jakikolwiek wyraz \(\displaystyle{ a _{n}}\) jest nieskończony.
Załóżmy, że mamy tylko skończenie wiele liczb pierwszych \(\displaystyle{ p_1, p_2, ..., p_k}\) dzielących wyrazy tego ciągu. Każdemu wyrazowi \(\displaystyle{ a_n}\) przyporządkujmy ciąg \(\displaystyle{ k}\)-elementowy liczb całkowitych nieujemnych \(\displaystyle{ ( \alpha_{n1}, \alpha_{n2}, ... \alpha_{nk})}\), odpowiadający przedstawieniu \(\displaystyle{ a_n = \prod_{i=1}^{k} p_i ^{ \alpha_{ni}}}\). Ciąg jest ściśle rosnący, więc różnym wyrazom odpowiadają różne ciągi. Zauważmy, że takich różnych ciągów, które sumują się do jakiegoś \(\displaystyle{ m}\), na pewno nie jest więcej niż \(\displaystyle{ m^k}\). Wobec tego wśród pierwszych \(\displaystyle{ m^k+1}\) wyrazów istnieje taki \(\displaystyle{ a_s}\), któremu odpowiada ciąg o sumie większej niż \(\displaystyle{ m}\). Jednak wtedy \(\displaystyle{ a_s = \prod_{i=1}^{n} p_i ^ { \alpha_{si}} \ge 2^m}\). Oznaczmy \(\displaystyle{ b_i = a_1+...+a_i}\), \(\displaystyle{ P(x) = x^k + 1}\). Wtedy \(\displaystyle{ b_{P(m)} \ge 2^m}\). Z drugiej strony, \(\displaystyle{ b_{P(m)} \le \sum_{i=1}^{P(m)} W(i) \le P(m)W(P(m))}\) (możemy wybrać taki wielomian ograniczający ciąg z góry, który jest ściśle rosnący). Stąd \(\displaystyle{ 2^m \le P(m)W(P(m))}\), co w granicy się sypie.