Difference between revisions of "2006 AMC 12B Problems/Problem 22"
ProbaBillity (talk | contribs) m (→Solution: Modified wording, changed "Obviously" into less-strong word, changed a! to a when needed.) |
m (→Solution) |
||
| Line 34: | Line 34: | ||
Intuition may now try to lure us to split <math>2006</math> into <math>a+b+c</math> as evenly as possible, giving | Intuition may now try to lure us to split <math>2006</math> into <math>a+b+c</math> as evenly as possible, giving | ||
| − | <math>a=b= | + | <math>a=b=669</math> and <math>c=668</math>. However, this solution is not optimal. |
To see how we can do better, let's rearrange the terms as follows: | To see how we can do better, let's rearrange the terms as follows: | ||
Revision as of 21:44, 15 October 2011
Problem
Suppose 
, 
and 
are positive integers with 
, and 
, where 
and 
are integers and is not divisible by 
. What is the smallest possible value of ?
Solution
Clearly, the power of 
that divides 
is larger or equal than the power of 
which divides
it. Hence we are trying to minimize the power of that will divide 
.
Consider 
. Each fifth term is divisible by , each 
-th one
by , and so on. Hence the total power of that divides is 
. (For any only finitely many terms in the sum
are
non-zero.)
In our case we have 
, so the largest power of that will be less than is at most
. Therefore the power of that divides 
is equal to 
. The same
is true for and .
Intuition may now try to lure us to split 
into 
as evenly as possible, giving
and 
. However, this solution is not optimal.
To see how we can do better, let's rearrange the terms as follows:
The idea is that the rows of the above equation are roughly equal to 
, 
, etc.
More precisely, we can now notice that for any positive integers 
we can write 
in the form 
, 
, 
, where all 
are integers and 
.
It follows that
![\[\Big\lfloor \frac a{k}\Big\rfloor + \Big\lfloor \frac b{k}\Big\rfloor + \Big\lfloor \frac c{k}\Big\rfloor = a_0+b_0+c_0\]](http://latex.artofproblemsolving.com/1/c/2/1c2fda95660c185cd8dac069be5dd43892d5276a.png)
and
![\[\Big\lfloor \frac {a+b+c}k\Big\rfloor = a_0 + b_0 + c_0 + \Big\lfloor \frac {a_1+b_1+c_1}k\Big\rfloor \leq a_0 + b_0 + c_0 + 2\]](http://latex.artofproblemsolving.com/1/2/6/126774d7a6b09b1310d9a9dc03931325961498db.png)
Hence we get that for any positive integers we have
![\[\Big\lfloor \frac a{k}\Big\rfloor + \Big\lfloor \frac b{k}\Big\rfloor + \Big\lfloor \frac c{k}\Big\rfloor \quad \geq \quad \Big\lfloor \frac {a+b+c}k\Big\rfloor - 2\]](http://latex.artofproblemsolving.com/3/4/1/341d9f17bcb55c1086aafae4435dc96ead2fdbc1.png)
Therefore for any the result is at least 
.
If we now show how to pick so that we'll get the result 
, we will be done.
Consider the row with 
in the denominator. We need to achieve sum 
in this row,
hence we need to make two of the numbers smaller than . Choosing 
does this, and it will give us the largest possible remainders for and in
the other three rows, so this is a pretty good candidate. We can compute
and verify that this triple gives the desired result 
.
See also
| 2006 AMC 12B (Problems • Answer Key • Resources) | |
| Preceded by Problem 21 |
Followed by Problem 23 |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
| All AMC 12 Problems and Solutions | |
