Difference between revisions of "2016 IMO Problems/Problem 4"
(Created page) |
(→Solution) |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | A set of | + | ==Problem== |
+ | |||
+ | A set of positive integers is called ''fragrant'' if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let <math>P(n)=n^2+n+1</math>. What is the least possible positive integer value of <math>b</math> such that there exists a non-negative integer <math>a</math> for which the set <math>\{P(a+1),P(a+2),\ldots,P(a+b)\}</math> is fragrant? | ||
+ | |||
+ | ==Solution== | ||
+ | Consider <math>P(x)</math> and <math>P(x+y)</math>. We note that in order to <math>p \mid P(x)</math> and <math>p \mid P(x+y)-P(x)</math> we must have <math>p \mid x^2+x+1</math> and <math>p \mid y(2x+y+1)</math>. It is obvious that <math>p \equiv 1 \pmod{6}</math> since <math>p \mid n^2+n+1 \mid (2n+1)^2+3</math> or <math>\left( \tfrac{-3}{p} \right)=1</math>. | ||
+ | |||
+ | If <math>y=1</math> then <math>p \mid 2x+2</math> implies <math>p \mid x+1</math>. WLOG, we can let <math>x=p-1</math> and see that <math>p \nmid x^2+x+1</math>. So there doesn't exists <math>x</math> so that <math>\gcd \left( P(x),P(x+1) \right)>1</math>. | ||
+ | |||
+ | If <math>y=2</math>, we find <math>p \mid 2x+3</math> and we let <math>x=\tfrac{p-3}{2}</math>. Hence, from <math>p \mid x^2+x+1</math> we get <math>p=7</math>. So there is one prime <math>p=7</math> such that <math>\gcd \left( P(x),P(x+2) \right)>1</math>. | ||
+ | |||
+ | If <math>y=3</math>, it is obvious that <math>p=3</math> satisfy and is the only answer. | ||
+ | |||
+ | If <math>y=4</math>, we do the similar thing and get <math>p \mid 2x+5</math> and <math>p \mid x^2+x+1</math> so <math>p=19</math>. | ||
+ | ___________________________ | ||
+ | Now, back to the problem, since there doesn't exists any prime <math>p</math> for <math>y=1</math> so <math>b \ge 3</math>. The only prime for <math>y=2</math> is <math>p=7</math> so if we choose <math>7 \mid P(x+1), 7 \mid P(x+3)</math> then there will be a number <math>7 \nmid P(x+2)</math> remains. This means <math>b \ge 5</math> since we need a prime <math>p \mid P(x+2)</math> and <math>p \mid P(x+y)</math> but <math>y \ge 5</math> since <math>p \ne 7</math>. | ||
+ | |||
+ | If <math>b=5</math>, we consider two cases, where there are two numbers that are divisible by <math>19</math> (which means <math>19 \mid P(x+1), 19 \mid P(x+5)</math>), the middle-three numbers <math>P(x+2),P(x+3),P(x+4)</math> we can't find a way make each two of them have common prime factor. If no two are divisible by <math>19</math> then they can only be divisible by <math>7,3</math>, but it can't cover all <math>5</math> "consecutive" numbers. | ||
+ | |||
+ | If <math>b=6</math> then we can pick <math>19 \mid P(x+2),P(x+6), 3 \mid P(x+1), P(x+4), 7 \mid P(x+3), 7 \mid P(x+5)</math>. | ||
+ | |||
+ | So the final answer is <math>b=6</math>. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2016|num-b=3|num-a=5}} |
Latest revision as of 04:18, 26 March 2024
Problem
A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let . What is the least possible positive integer value of
such that there exists a non-negative integer
for which the set
is fragrant?
Solution
Consider and
. We note that in order to
and
we must have
and
. It is obvious that
since
or
.
If then
implies
. WLOG, we can let
and see that
. So there doesn't exists
so that
.
If , we find
and we let
. Hence, from
we get
. So there is one prime
such that
.
If , it is obvious that
satisfy and is the only answer.
If , we do the similar thing and get
and
so
.
___________________________
Now, back to the problem, since there doesn't exists any prime
for
so
. The only prime for
is
so if we choose
then there will be a number
remains. This means
since we need a prime
and
but
since
.
If , we consider two cases, where there are two numbers that are divisible by
(which means
), the middle-three numbers
we can't find a way make each two of them have common prime factor. If no two are divisible by
then they can only be divisible by
, but it can't cover all
"consecutive" numbers.
If then we can pick
.
So the final answer is .
See Also
2016 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |