Difference between revisions of "2003 AIME I Problems/Problem 13"
m |
(solution) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let <math> N </math> be the number of positive integers that are less than or equal to 2003 and whose base-2 representation has more 1's than 0's. Find the remainder when <math> N </math> is divided by 1000. | + | Let <math> N </math> be the number of positive integers that are less than or equal to <math>2003</math> and whose base-<math>2</math> representation has more <math>1</math>'s than <math>0</math>'s. Find the [[remainder]] when <math> N </math> is divided by <math>1000</math>. |
== Solution == | == Solution == | ||
| − | {{ | + | In base-<math>2</math> representation, all positive numbers have a leftmost digit of <math>1</math>. Thus there are <math>{n \choose k}</math> numbers that have <math>n+1</math> digits in base <math>2</math> notation, with <math>k+1</math> of the digits being <math>1</math>'s. |
| + | |||
| + | In order for there to be more <math>1</math>'s then <math>0</math>'s, we must have <math>k+1 > \frac{d+1}{2} \Longrightarrow k > \frac{d-1}{2} \Longrightarrow k \ge \frac{d}{2}</math>. Therefore, the number of such numbers corresponds to the sum of all numbers on or to the right of the vertical line of symmetry in [[Pascal's Triangle]], from rows <math>0</math> to <math>10</math> (as <math>2003 < 2^{11}-1</math>). Since the sum of the elements of the <math>r</math>th row is <math>2^r</math>, it follows that the sum of all elements in rows <math>0</math> through <math>10</math> is <math>2^0 + 2^1 + \cdots + 2^{10} = 2^{11}-1 = 2047</math>. The center elements are in the form <math>{2i \choose i}</math>, so the sum of these elements is <math>\sum_{i=0}^{5} {2i \choose i} = 1 + 2 +6 + 20 + 70 + 252 = 351</math>. | ||
| + | |||
| + | The sum of the elements on or to the right of the line of symmetry is thus <math>\frac{2047 + 351}{2} = 1199</math>. However, we also counted the <math>44</math> numbers from <math>2004</math> to <math>2^{11}-1 = 2047</math>. Indeed, all of these numbers have at least <math>6</math> <math>1</math>'s in their base-<math>2</math> representation, as all of them are greater than <math>1984 = 11111000000_2</math>, which has <math>5</math> <math>1</math>'s. Therefore, our answer is <math>1199 - 44 = 1155</math>, and the remainder is <math>\boxed{155}</math>. | ||
| + | |||
== See also == | == See also == | ||
| − | + | {{AIME box|year=2003|n=I|num-b=12|num-a=14}} | |
| − | + | ||
| − | + | [[Category:Intermediate Combinatorics Problems]] | |
Revision as of 14:20, 11 June 2008
Problem
Let 
be the number of positive integers that are less than or equal to 
and whose base-
representation has more 
's than 
's. Find the remainder when is divided by 
.
Solution
In base- representation, all positive numbers have a leftmost digit of . Thus there are 
numbers that have 
digits in base notation, with 
of the digits being 's.
In order for there to be more 's then 's, we must have 
. Therefore, the number of such numbers corresponds to the sum of all numbers on or to the right of the vertical line of symmetry in Pascal's Triangle, from rows to 
(as 
). Since the sum of the elements of the 
th row is 
, it follows that the sum of all elements in rows through is 
. The center elements are in the form 
, so the sum of these elements is 
.
The sum of the elements on or to the right of the line of symmetry is thus 
. However, we also counted the 
numbers from 
to 
. Indeed, all of these numbers have at least 
's in their base- representation, as all of them are greater than 
, which has 
's. Therefore, our answer is 
, and the remainder is 
.
See also
| 2003 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 12 |
Followed by Problem 14 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
