Problem: n n
⌊ 2 1 ⌋ + ⌊ 2 2 ⌋ + ⌊ 2 3 ⌋ + ⋯ + ⌊ 2 n ⌋ = 1994 ⌊ log 2 1 ⌋ + ⌊ log 2 2 ⌋ + ⌊ log 2 3 ⌋ + ⋯ + ⌊ log 2 n ⌋ = 1 9 9 4
(For real x , ⌊ x ⌋ x , ⌊ x ⌋ ≤ x ≤ x
Solution:
Let
S n = ⌊ 2 1 ⌋ + ⌊ 2 2 ⌋ + ⌊ 2 3 ⌋ + ⋯ + ⌊ 2 n ⌋ S n = ⌊ log 2 1 ⌋ + ⌊ log 2 2 ⌋ + ⌊ log 2 3 ⌋ + ⋯ + ⌊ log 2 n ⌋
Note that, for nonnegative integer k k 2 k 2 k x x ⌊ 2 x ⌋ = k ⌊ log 2 x ⌋ = k x = 2 k , 2 k + 1 , … , 2 k + 1 − 1 x = 2 k , 2 k + 1 , … , 2 k + 1 − 1 r r
S 2 r − 1 = 0 + ( 1 + 1 ) + ( 2 + 2 + 2 + 2 ) + ⋯ + ( ( r − 1 ) + ( r − 1 ) + ⋯ + ( r − 1 ) ⏟ 2 r − 1 terms ) S 2 r − 1 = 0 + ( 1 + 1 ) + ( 2 + 2 + 2 + 2 ) + ⋯ + ( 2 r − 1 terms ( r − 1 ) + ( r − 1 ) + ⋯ + ( r − 1 ) )
The right side of this expression has
2 r − 2 1 terms ≥ 1 2 r − 2 2 terms ≥ 2 2 r − 2 3 terms ≥ 3 2 r − 2 r − 2 terms ≥ r − 2 2 r − 2 r − 1 terms = r − 1. 2 r − 2 1 terms ≥ 1 2 r − 2 2 terms ≥ 2 2 r − 2 3 terms ≥ 3 ⋮ 2 r − 2 r − 2 terms ≥ r − 2 2 r − 2 r − 1 terms = r − 1 .
It follows that
S 2 r − 1 = ( 2 r − 2 1 ) + ( 2 r − 2 2 ) + ( 2 r − 2 3 ) + ⋯ + ( 2 r − 2 r − 1 ) = ( r − 1 ) 2 r − ( 2 r − 2 ) = ( r − 2 ) 2 r + 2 S 2 r − 1 = ( 2 r − 2 1 ) + ( 2 r − 2 2 ) + ( 2 r − 2 3 ) + ⋯ + ( 2 r − 2 r − 1 ) = ( r − 1 ) 2 r − ( 2 r − 2 ) = ( r − 2 ) 2 r + 2
Taking r = 8 r = 8 S 255 = 1538 < 1994 S 2 5 5 = 1 5 3 8 < 1 9 9 4 r = 9 r = 9 S 511 = 3586 > 1994 S 5 1 1 = 3 5 8 6 > 1 9 9 4 S n = 1994 S n = 1 9 9 4 255 = 2 8 − 1 < n < 2 9 − 1 2 5 5 = 2 8 − 1 < n < 2 9 − 1
1994 = S n = S 255 + ( n − 255 ) 8 = 8 n − 502 1 9 9 4 = S n = S 2 5 5 + ( n − 2 5 5 ) 8 = 8 n − 5 0 2
and this yields n = 312 n = 3 1 2
The problems on this page are the property of the MAA's American Mathematics Competitions