Loading [MathJax]/jax/output/SVG/jax.js

Математикадан 58-ші халықаралық олимпиада, 2017 жыл, Рио-де-Жанейро


Натурал сандардан тұратын осындай жиындарды нәзік деп атайық: егер жиынының ішінде кемінде екі элемент болса, және оның әрбір элементі жиынының басқа бір элементпен ортақ жай бөлгіші болса. P(n)=n2+n+1 болсын. Егер төмендегі шарт орындалса, b натурал санының ең кіші болатын мәні кандай? {P(a+1),P(a+2),,P(a+b)} жиыны нәзік болатын a теріс емес бүтін саны табылады.
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   1
2 года назад #

Решение: Заметим, чтоgcd(P(n1),P(n))=gcd(n2n+1,n2+n+1)=gcd(n2n+1,2n)=gcd(n,n2n+1,n)=1(1)p|P(a+2),P(a)p|a2+a+1,2a+3p|(2a+1)2+322+3=77|a2(2)Из (1) следует, что искомое b2,3, из (2) имеем b4. Если b=5, то некоторые 3 числа из {P(a+1),P(a+2),...,P(a+5)} имеют общий простой делитель, иначе 5 чисел можно разбить на пары не взаимнопростых, т.е. 5 - чётное. Из (1) эти 3 числа P(a+1),P(a+3),P(a+5), откуда из (2) 7|a1,a+1 - противоречие, поэтому b6.

p|P(a),P(a+3)p|6a+12,a2+a+13|a2p|P(a),P(a+4)p|8a+20,a2+a+1p|2a+5,(2a)2+4a+41919|a7Теперь докажем существование такого a, чтоgcd(P(a+1),P(a+5))=19,gcd(P(a+2),P(a+4))=7,gcd(P(a+3),P(a+6))=3Из доказанного выше это равносильно 19|a6,7|a,3|a2, очевидно такой существует по китайской теореме об остатках.

Ответ: 6