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"

(→‎Problem and Solution)
 
(→‎Newer, simpler proof)
Line 10: Line 10:
 
permutations of these triples.
 
permutations of these triples.
  
−
Assume <math>a \leq b \leq c</math>, so that <math>ab-c = 2^m</math>, <math>ca-b = 2^n</math>,
+
Throughout the proof, we assume <math>a \leq b \leq c</math>,
−
<math>bc-a=2^p</math>, with <math>m \leq n \leq p</math>. We have <math>a>1</math> since
+
so that <math>ab-c = 2^m</math>, <math>ca-b = 2^n</math>,
−
otherwise <math>c-b</math> and <math>b-c</math> should both be positive, which is
+
<math>bc-a=2^p</math>, with <math>m \leq n \leq p</math>. Note that <math>a>1</math> since
−
impossible. We exhaust the various cases as follows:
+
otherwise <math>b-c=2^m</math>, which is impossible. Hence
 +
<math>2^n = ac-b \geq (a-1)c \geq 2</math>, i.e., <math>n</math> and <math>p</math> are positive.
  
−
<b>Case 1: </b><math>a=b</math>.  
+
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)
 +
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
 +
solution; hence  <math>a=b\geq 3</math> is infeasible. We consider the remaining cases as follows.  
  
−
Hence <math>n=p</math>, <math>a^2=2^m+c</math> and <math>a(c-1)=2^n</math>. From the second equation, <math>a=2^r</math> and <math>c=2^{n-r}+1</math>,
+
<b>Case 1: </b><math>a=2</math>. We have
−
where <math>r>0</math>. From the first, <math>2^{2r}=2^{m}+2^{n-r}+1</math>. Thus either
+
<cmath>2b-c=2^m,\; 2c-b=2^n,\; bc-2=2^p.</cmath>
−
<math>n=r</math> or <math>m=0</math> (otherwise the LHS is even and RHS is odd).  Hence either
+
From the second equation, <math>b</math> is even. From the third equation, if
−
<math>2^{2n}=2^{m}+2</math> or <math>2^{2r}=2^{n-r}+2;</math> <math>(m,n,r)</math> equals
+
<math>p=1</math>, then <math>b=c=2</math>; if <math>p>1</math>, then <math>c</math> is odd, which implies that
−
<math>(1,1,1)</math> or <math>(0,2,1).</math> This gives <math>(a,b,c) = (2,2,2)</math> or <math>(2,2,3)</math>.
+
<math>m=0</math>. Hence <math>3b=2^n+2</math> (so <math>n\geq 2</math>),
 +
<math>3c=2^{n+1}+1</math>, and <math>(2^{n-1}+1)(2^{n+1}+1)=9(2^{p-1}+1)</math>. Hence
 +
<math>1\equiv 9 \mod 2^{n-1} \implies n \leq 4</math>. Hence <math>n</math> is 2 or 4, and
 +
<math>(b,c)</math> equals <math>(2,3)</math> or <math>(6,11)</math>. Thus the solutions for <math>(a,b,c)</math>
 +
are <math>(2,2,2)</math>, <math>(2,2,3)</math> or <math>(2,6,11)</math>.
  
−
<b>Case 2: </b><math>2=a<b \leq c</math> (so <math>m\leq n<p</math>).
+
<b> Case 2: </b><math>3\leq a<b\leq c</math>.
−
 
+
Since <math>(a-1)c \leq 2^n</math>, we have <math>c\leq 2^{n-1}</math>. Hence
−
Hence <math>2b-c=2^m</math>, <math>2c-b=2^n</math>, <math>bc-2=2^p</math>. From the second
+
<cmath> b+a < 2c\leq 2^{n+1}/(a-1) \leq 2^n,</cmath>
−
equation, <math>2^n \geq c>2</math>, so <math>2^n</math> is even. Hence <math>b</math> is even. Further, <math>2^p\geq 2^{n+1}>4.</math>
+
<cmath> b-a < c \leq 2^{n-1}. </cmath>
−
From the third equation, <math>bc=2^p+2</math> is not divisible by 4, so <math>c</math> is odd and <math>b=2b_0</math>
+
Hence <math>b-a</math> is not divisible by <math>2^{n-1}</math>, and <math>b+a</math> is not divisible
−
where <math>b_0</math> is odd. From the first
+
by <math>2^{n-1}</math> for <math>a\geq 5</math>. Adding and subtracting <math>ac-b=2^n</math> and <math>bc-a=2^p</math>, we get
−
equation, <math>2^m</math> is odd and must equal 1.
 
−
Hence <math>4b_0-c=1</math>, <math>c-b_0=2^{n-1}</math>, <math>b_0c=2^{p-1}+1</math>.
 
−
Hence <math>b_0(b_0+2^{n-1})=2^{p-1}+1</math>. From the first two equations, <math>3b_0=1+2^{n-1}</math>.
 
−
Hence <math>n \geq 4</math>  (note that <math>n=2</math> would imply <math>b_0=1</math> which contradicts <math>b>a</math>).
 
−
Substituting for <math>b_0</math>, we get
 
−
<math>(1+2^{n-1})(1+2^{n+1})=9(2^{p-1}+1)</math>.
 
−
Modulo <math>2^{n-1}</math>, the LHS  <math>\equiv 1</math> and the RHS <math>\equiv 9</math> (note <math>p>n</math>).
 
−
Hence <math>9\equiv 1 \mod 2^{n-1}</math>, so <math>n=4</math>, <math>p=6</math>, <math>b=6</math>, and <math>c=11</math>.
 
−
We conclude that <math>(a,b,c)=(2,6,11)</math> is the only solution.
 
−
 
 
−
<b> Case 3: </b> <math>3\leq a<b \leq c</math>.  
 
−
 
 
−
The following simple lemma is used in the proof below:
 
−
<i> If <math>i</math> and <math>j</math> are odd integers, then exactly one of the two (even) integers <math>i+j</math> and <math>i-j</math> is divisible by <math>4</math>.</i>
 
−
 
 
−
For, if <math>i+j\equiv k \mod 4</math> and <math>i-j\equiv k \mod 4</math>, we would have
 
−
<math>k=0</math> or <math>k=2</math> (since <math>i+j</math> and <math>i-j</math> are even). But then
 
−
<math>2i \equiv 0 \mod 4</math> which contradicts the hypothesis that <math>i</math> is odd.
 
−
 
 
−
From <math>ac-b=2^n</math>, we get
 
−
<math>2^n\geq 2c > 6</math>, so <math>n\geq 3</math> and <math>2^n</math> is even. Write the last
 
−
two equations as
 
 
<cmath> (c-1)(b+a) = 2^p+2^n, </cmath>
 
<cmath> (c-1)(b+a) = 2^p+2^n, </cmath>
−
<cmath> (c+1)(b-a) = 2^p-2^n. </cmath>
+
<cmath>(c+1)(b-a) = 2^p-2^n.</cmath>
−
If <math>c</math> is even, <math>2^n</math> should divide <math>b-a<b\leq c \leq 2^{n-1}</math>, which
+
From the latter equation, <math>c+1</math> is divisible by <math>4</math>. Hence <math>c-1</math> is not  
−
is impossible. Hence <math>c</math> is odd, and one of <math>c+1</math> and <math>c-1</math> is not
+
divisible by <math>4</math>, which implies that <math>b+a < 2^n</math> is a multiple of <math>2^{n-1}</math>.
−
divisible by 4 (from the lemma above). Hence one of <math>b+a</math> and <math>b-a</math> is
+
Hence <math>a \leq 4</math> and <math>b+a=2^{n-1}</math>.  
−
an odd multiple of <math>2^{n-1};</math> since <math>b-a < 2^{n-1}</math>, this must be
 
−
<math>b+a</math>. But <math>b+a<2b \leq 2.2^{n-1}</math>, so in fact <math>b+a=2^{n-1}</math>.
 
−
Hence <math>c-1=2^{p-n+1}+2</math>, and <math>(2^{p-n+1}+4)(2^{n-1}-2a)=2^p-2^n</math>.  
 
  
−
If <math>a</math> and <math>b</math> were even, we would have <math>m=1</math>
+
Consider <math>a=3</math>, which implies <math>3b-c=2^m</math>, <math>3c-b=2^n</math>, <math>b=2^{n-1}-3</math>.
−
and <math>c+1=2^{p-n+1}+4=ab \geq 3(4)=12</math>. Hence <math>2^{p-n+1} \geq 8</math> and
+
Hence <math>2^{n-1}-3=3.2^{m-3}+2^{n-3}</math>, or
−
<math>ab=2^{p-n+1}+4</math> is not divisible by <math>8</math>. Hence <math>a=2a_0</math> where <math>a_0</math> is odd, and
+
<math>2^{n-3}=2^{m-3}+1</math>. Hence <math>m=3</math>, <math>n=4</math>, <math>b=5</math> and <math>c=7</math>.
−
<math>(2^{p-n-1}+1)(2^{n-3}-a_0)=2^{p-4}-2^{n-4}</math>. The LHS is odd and so must be the RHS, i.e.,  
 
−
<math>n=4</math>. We get <math>(2^{p-5}+1)(2-a_0)=2^{p-4}-1</math>. For the LHS to
 
−
be positive, we need <math>a_0=1,</math> i.e., <math>a=2</math> which is contrary to the hypothesis that
 
−
<math>a\geq 3</math>.
 
  
−
Thus <math>a</math> and <math>b</math> are odd. We have
+
Finally, consider <math>a=4</math>, <math>4c-b=2^n</math>,
−
<math>(2^{p-n-1}+1)(2^{n-2}-a)=2^{p-3}-2^{n-3}</math>. If
+
<math>b=2^{n-1}-4</math>. Hence <math>c=3.2^{n-3}-1</math>. But <math>b \leq c</math> implies
−
<math>2^{p-n-1}</math> were even, the LHS would be odd, so <math>n=3</math> and
+
<math>2^{n-3} \leq 3</math> and <math>a<b</math> implies <math>2^{n-3}>2</math>. Hence there are no
−
<math>a<2^{n-2}=2.</math> This is impossible. Hence <math>p-n-1=0</math>, and
+
solutions with <math>a=4</math>.
−
<math>c=2^{p-n+1}+3=7</math>. Also <math>(2^{n-2}-a)=2^{p-4}-2^{n-4}</math>, so <math>n=4</math>,
 
−
<math>p=5</math>, <math>a=3</math>,  <math>b=ac-2^{n}=5</math>. Hence the only solution in this case
 
−
is <math>(a,b,c)=(3,5,7)</math>.
 
  
 +
We obtain <math>(a,b,c)=(3,5,7)</math> as the only solution with
 +
<math>3 \leq a < b \leq c</math>.
  
 
==See Also==
 
==See Also==

Revision as of 22:50, 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.

Now 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=72495"