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. | ||
− | + | 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>. | + | so that <math>ab-c = 2^m</math>, <math>ca-b = 2^n</math>, |
− | otherwise <math>c-b</math> and <math> | + | <math>bc-a=2^p</math>, with <math>m \leq n \leq p</math>. Note that <math>a>1</math> since |
− | + | 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> | + | 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. | ||
− | + | <b>Case 1: </b><math>a=2</math>. We have | |
− | + | <cmath>2b-c=2^m,\; 2c-b=2^n,\; bc-2=2^p.</cmath> | |
− | <math>n | + | From the second equation, <math>b</math> is even. From the third equation, if |
− | <math>2^{ | + | <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>( | + | <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> | + | <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 | |
− | + | <cmath> b+a < 2c\leq 2^{n+1}/(a-1) \leq 2^n,</cmath> | |
− | + | <cmath> b-a < c \leq 2^{n-1}. </cmath> | |
− | + | Hence <math>b-a</math> is not divisible by <math>2^{n-1}</math>, and <math>b+a</math> is not divisible | |
− | + | 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 | |
− | |||
− | |||
− | |||
− | Hence | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<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> |
− | + | From the latter equation, <math>c+1</math> is divisible by <math>4</math>. Hence <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 | + | Hence <math>a \leq 4</math> and <math>b+a=2^{n-1}</math>. |
− | |||
− | <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>. | |
− | + | Hence <math>2^{n-1}-3=3.2^{m-3}+2^{n-3}</math>, or | |
− | <math> | + | <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> | ||
− | |||
− | <math> | ||
− | + | Finally, consider <math>a=4</math>, <math>4c-b=2^n</math>, | |
− | + | <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^{ | + | <math>2^{n-3} \leq 3</math> and <math>a<b</math> implies <math>2^{n-3}>2</math>. Hence there are no |
− | + | solutions with <math>a=4</math>. | |
− | <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 such that each of the numbers
is a power of 2.
(A power of 2 is an integer of the form where
is a non-negative integer ).
Solution
The solutions for are
,
,
,
, and
permutations of these triples.
Throughout the proof, we assume ,
so that
,
,
, with
. Note that
since
otherwise
, which is impossible. Hence
, i.e.,
and
are positive.
Now if , we get
, so
and
are (even and)
powers of
. Hence
is odd and
. Hence
is also a
power of
, which implies
. But
is not a
solution; hence
is infeasible. We consider the remaining cases as follows.
Case 1: . We have
From the second equation,
is even. From the third equation, if
, then
; if
, then
is odd, which implies that
. Hence
(so
),
, and
. Hence
. Hence
is 2 or 4, and
equals
or
. Thus the solutions for
are
,
or
.
Case 2: .
Since
, we have
. Hence
Hence
is not divisible by
, and
is not divisible
by
for
. Adding and subtracting
and
, we get
From the latter equation,
is divisible by
. Hence
is not
divisible by
, which implies that
is a multiple of
.
Hence
and
.
Consider , which implies
,
,
.
Hence
, or
. Hence
,
,
and
.
Finally, consider ,
,
. Hence
. But
implies
and
implies
. Hence there are no
solutions with
.
We obtain as the only solution with
.
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 |