Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 IMO Problems/Problem 4"

m (Fixed italics)
(→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
==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?
 
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 $P(n)=n^2+n+1$. What is the least possible positive integer value of $b$ such that there exists a non-negative integer $a$ for which the set $\{P(a+1),P(a+2),\ldots,P(a+b)\}$ is fragrant?

Solution

Consider $P(x)$ and $P(x+y)$. We note that in order to $p \mid P(x)$ and $p \mid P(x+y)-P(x)$ we must have $p \mid x^2+x+1$ and $p \mid y(2x+y+1)$. It is obvious that $p \equiv 1 \pmod{6}$ since $p \mid n^2+n+1 \mid (2n+1)^2+3$ or $\left( \tfrac{-3}{p} \right)=1$.

If $y=1$ then $p \mid 2x+2$ implies $p \mid x+1$. WLOG, we can let $x=p-1$ and see that $p \nmid x^2+x+1$. So there doesn't exists $x$ so that $\gcd \left( P(x),P(x+1) \right)>1$.

If $y=2$, we find $p \mid 2x+3$ and we let $x=\tfrac{p-3}{2}$. Hence, from $p \mid x^2+x+1$ we get $p=7$. So there is one prime $p=7$ such that $\gcd \left( P(x),P(x+2) \right)>1$.

If $y=3$, it is obvious that $p=3$ satisfy and is the only answer.

If $y=4$, we do the similar thing and get $p \mid 2x+5$ and $p \mid x^2+x+1$ so $p=19$. ___________________________ Now, back to the problem, since there doesn't exists any prime $p$ for $y=1$ so $b \ge 3$. The only prime for $y=2$ is $p=7$ so if we choose $7 \mid P(x+1), 7 \mid P(x+3)$ then there will be a number $7 \nmid P(x+2)$ remains. This means $b \ge 5$ since we need a prime $p \mid P(x+2)$ and $p \mid P(x+y)$ but $y \ge 5$ since $p \ne 7$.

If $b=5$, we consider two cases, where there are two numbers that are divisible by $19$ (which means $19 \mid P(x+1), 19 \mid P(x+5)$), the middle-three numbers $P(x+2),P(x+3),P(x+4)$ we can't find a way make each two of them have common prime factor. If no two are divisible by $19$ then they can only be divisible by $7,3$, but it can't cover all $5$ "consecutive" numbers.

If $b=6$ then we can pick $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)$.

So the final answer is $b=6$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_IMO_Problems/Problem_4&oldid=217429"