51-я Международная Математическая Oлимпиада
Казахстан, Астана, 2010 год
Комментарий/решение:
Предположим существует такое простое p, что p|g(n+1)−g(n). Легко видеть, что существует такое k, что vp(g(n+1)+k)=vp(g(n)+k)=1. Поскольку (g(n)+k)(g(k)+n) является точным квадратом p|g(k)+n. Аналогично p|g(k)+n+1, откуда p|1 - противоречие. Поэтому g(n+1)−g(n)=±1. Если g(n+1)=g(n)−1, то (g(n)+n+1)(g(n+1)+n)=(g(n)+n)2−1 является полным квадратом - противоречие. В итоге g(n+1)=g(n)+1, значит g(n)=n+C для некоторой постоянной C, а это подходит.
Ох! Действительно. При p>2 это верно, но не при p=2. К счастью, данную дыру легко залатать. При g(n+1)\equiv g(n)\pmod4 такое k найдётся. Значит g(n+1)=g(n)\pm2. Случай g(n+1)=g(n)+2 простой. Если g(n)=g(n+1)+2, то (g(n)+n+1)(g(n+1)+n)=(g(n+1)+n+3)(g(n+1)+n) квадрат, то есть x(x+3) квадрат для x=g(n+1)+n\ge2. Это невозможно. При x не делящихся на 3 мы имеем, что x,x+3 взаимно просты, то бишь они оба являются квадратами - противоречие для x>1. При x=3s выходит, что s(s+1) квадрат - также невозможно
Также g(n+1) \ne g(n) в силу инъективности. Она доказывается следующим образом:
Пусть g(a)=g(b), a \ne b тогда возьмем такое n, чтобы g(a)+n \in P. Тогда P(a,n):
(g(a)+n)(a+g(n) = x^2;
(g(b)+n)(b+g(n) = y^2
Тогда a+g(n) делится на p, b+g(n) делится на p, то есть a-b делится на p, хотя p можно взять сколь угодно большим, противоречие.
P.S. случай g(n+1)=g(n) разбирать необязательно, оказывается
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.