2005 PMWC Problems/Problem I15
Problem
The sum of the two three-digit integers, 
and 
, is divisible by 
. What is the largest possible product of 
and 
?
Solution
A number is divisible by 18 iff it is divisible by 2 and 9. Divisibility by 2 is already satisfied, so we need the number to be divisible by 9; the divisibility rule for 9 states that we only need the sum of the digits to be divisible by 9. The units digit is 6; so the sum, 
, of the digits of 
, satisfies 
. The only reasonable values for 
.
. It quickly becomes apparent that 
, which gives us 
.
. Suppose 
. Then 
gives either 
, and we carry over the one to 
. So the sum of the digits of 
must add up to 
, which quickly shows us that this isn't possible.
. It quickly becomes apparent that 
, which gives us 
.
. Suppose 
. Then 
gives either 
, and we carry over the one to 
. So the sum of the digits of 
must add up to 
, which quickly shows us that this isn't possible.- Hence,
. Greedy algorithm: if 
, then 
, so the sum of the digits of 
must be 12. So 
. The other possible pairs are 
.
. 
, then 
, so the sum of the digits of 
must be 12. So 
. The other possible pairs are 
.Quickly taking the product of these, we find that 
gives us the largest product of 
.
See also
| 2005 PMWC (Problems) | ||
| Preceded by Problem I14 |
Followed by Problem T1 | |
| I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 | ||
