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 "2015 IMO Problems/Problem 2"

(→‎Newer, simpler proof)
(→‎Solution)
 
Line 16: Line 16:
 
<math>2^n = ac-b \geq (a-1)c \geq 2</math>, i.e., <math>n</math> and <math>p</math> are positive.
 
<math>2^n = ac-b \geq (a-1)c \geq 2</math>, i.e., <math>n</math> and <math>p</math> are positive.
  
−
Now if <math>a=b\geq 3</math>, we get <math>a(c-1)=2^n</math>, so <math>a</math> and <math>c-1</math> are (even and)
+
Observe that if <math>a=b\geq 3</math>, we get <math>a(c-1)=2^n</math>, so <math>a</math> and <math>c-1</math> are (even and)
 
powers of <math>2</math>. Hence <math>c</math> is odd and <math>a^2-c=2^m=1</math>. Hence <math>c+1=a^2</math> is also a
 
powers of <math>2</math>. Hence <math>c</math> is odd and <math>a^2-c=2^m=1</math>. Hence <math>c+1=a^2</math> is also a
 
power of <math>2</math>, which implies <math>c=3</math>. But <math>a=b=c=3</math> is not a
 
power of <math>2</math>, which implies <math>c=3</math>. But <math>a=b=c=3</math> is not a

Latest revision as of 21:51, 16 October 2015

Problem

Determine all triples of positive integers $(a,b,c)$ such that each of the numbers \[ab-c,\; bc-a,\; ca-b\] is a power of 2.

(A power of 2 is an integer of the form $2^n$ where $n$ is a non-negative integer ).

Solution

The solutions for $(a,b,c)$ are $(2,2,2)$, $(2,2,3)$, $(2,6,11)$, $(3,5,7)$, and permutations of these triples.

Throughout the proof, we assume $a \leq b \leq c$, so that $ab-c = 2^m$, $ca-b = 2^n$, $bc-a=2^p$, with $m \leq n \leq p$. Note that $a>1$ since otherwise $b-c=2^m$, which is impossible. Hence $2^n = ac-b \geq (a-1)c \geq 2$, i.e., $n$ and $p$ are positive.

Observe that if $a=b\geq 3$, we get $a(c-1)=2^n$, so $a$ and $c-1$ are (even and) powers of $2$. Hence $c$ is odd and $a^2-c=2^m=1$. Hence $c+1=a^2$ is also a power of $2$, which implies $c=3$. But $a=b=c=3$ is not a solution; hence $a=b\geq 3$ is infeasible. We consider the remaining cases as follows.

Case 1: $a=2$. We have \[2b-c=2^m,\; 2c-b=2^n,\; bc-2=2^p.\] From the second equation, $b$ is even. From the third equation, if $p=1$, then $b=c=2$; if $p>1$, then $c$ is odd, which implies that $m=0$. Hence $3b=2^n+2$ (so $n\geq 2$), $3c=2^{n+1}+1$, and $(2^{n-1}+1)(2^{n+1}+1)=9(2^{p-1}+1)$. Hence $1\equiv 9 \mod 2^{n-1} \implies n \leq 4$. Hence $n$ is 2 or 4, and $(b,c)$ equals $(2,3)$ or $(6,11)$. Thus the solutions for $(a,b,c)$ are $(2,2,2)$, $(2,2,3)$ or $(2,6,11)$.

Case 2: $3\leq a<b\leq c$. Since $(a-1)c \leq 2^n$, we have $c\leq 2^{n-1}$. Hence \[b+a < 2c\leq 2^{n+1}/(a-1) \leq 2^n,\] \[b-a < c \leq 2^{n-1}.\] Hence $b-a$ is not divisible by $2^{n-1}$, and $b+a$ is not divisible by $2^{n-1}$ for $a\geq 5$. Adding and subtracting $ac-b=2^n$ and $bc-a=2^p$, we get \[(c-1)(b+a) = 2^p+2^n,\] \[(c+1)(b-a) = 2^p-2^n.\] From the latter equation, $c+1$ is divisible by $4$. Hence $c-1$ is not divisible by $4$, which implies that $b+a < 2^n$ is a multiple of $2^{n-1}$. Hence $a \leq 4$ and $b+a=2^{n-1}$.

Consider $a=3$, which implies $3b-c=2^m$, $3c-b=2^n$, $b=2^{n-1}-3$. Hence $2^{n-1}-3=3.2^{m-3}+2^{n-3}$, or $2^{n-3}=2^{m-3}+1$. Hence $m=3$, $n=4$, $b=5$ and $c=7$.

Finally, consider $a=4$, $4c-b=2^n$, $b=2^{n-1}-4$. Hence $c=3.2^{n-3}-1$. But $b \leq c$ implies $2^{n-3} \leq 3$ and $a<b$ implies $2^{n-3}>2$. Hence there are no solutions with $a=4$.

We obtain $(a,b,c)=(3,5,7)$ as the only solution with $3 \leq a < b \leq c$.

See Also

2015 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_IMO_Problems/Problem_2&oldid=72496"