Difference between revisions of "2003 AIME I Problems/Problem 13"
Minediamonds (talk | contribs) m (→Solution 3) |
|||
(11 intermediate revisions by 7 users not shown) | |||
Line 2: | Line 2: | ||
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>. | 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 1 == |
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 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 | + | In order for there to be more <math>1</math>'s than <math>0</math>'s, we must have <math>k+1 > \frac{n+1}{2} \implies k > \frac{n-1}{2} \implies k \ge \frac{n}{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>. | 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>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | We seek the number of allowed numbers which have <math> k</math> 1's, not including the leading 1, for <math> k=0, 1, 2, \ldots , 10</math>. | ||
+ | |||
+ | For <math> k=0,\ldots , 4</math>, this number is | ||
+ | |||
+ | <math> \binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{2k}{k}</math>. | ||
+ | |||
+ | By the Hockey Stick Identity, this is equal to <math> \binom{2k+1}{k+1}</math>. So we get | ||
+ | |||
+ | <math> \binom{1}{1}+\binom{3}{2}+\binom{5}{3}+\binom{7}{4}+\binom{9}{5}=175</math>. | ||
+ | |||
+ | For <math> k=5,\ldots , 10</math>, we end on <math> \binom{10}{k}</math> - we don't want to consider numbers with more than 11 digits. So for each <math> k</math> we get | ||
+ | |||
+ | <math> \binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{10}{k}=\binom{11}{k+1}</math> | ||
+ | |||
+ | again by the Hockey Stick Identity. So we get | ||
+ | |||
+ | <math> \binom{11}{6}+\binom{11}{7}+\binom{11}{8}+\binom{11}{9}+\binom{11}{10}+\binom{11}{11}=\frac{2^{11}}{2}=2^{10}=1024</math>. | ||
+ | |||
+ | The total is <math> 1024+175=1199</math>. Subtracting out the <math> 44</math> numbers between <math> 2003</math> and <math> 2048</math> gives <math> 1155</math>. Thus the answer is <math> 155</math>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | We will count the number of it <math>< 2^{11}=2048</math> instead of <math>2003</math> (In other words, the length of the base-2 representation is at most <math>11</math>. If there are even digits, <math>2n</math>, then the leftmost digit is <math>1</math>, the rest, <math>2n-1</math>, has odd number of digits. In order for the base-2 representation to have more <math>1</math>'s, we will need more <math>1</math> in the remaining <math>2n-1</math> than <math>0</math>'s. Using symmetry, this is equal to | ||
+ | <math>\frac{2^9+2^7+..+2^1}{2}</math> | ||
+ | Using similar argument where there are odd amount of digits. The remaining even amount of digit must contains the number of <math>1</math>'s at least as the number of <math>0</math>'s. So it's equal to | ||
+ | <math>\frac{\binom{10}{5}+2^{10}+\binom{8}{4}+2^8+\binom{6}{3}+2^6+...+\binom{0}{0}+2^0}{2}</math> | ||
+ | Summing both cases, we have <math>\frac{2^0+2^1+..+2^{10}+\binom{0}{0}+..+\binom{10}{5}}{2} = 199</math>. There are <math>44</math> numbers between <math>2004</math> and <math>2047</math> inclusive that satisfy it. So the answer is <math>199-44=\boxed{155}</math> | ||
+ | |||
+ | ~minor edits by minediamonds | ||
== See also == | == See also == |
Latest revision as of 18:42, 7 October 2023
Contents
[hide]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 1
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 than '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 .
Solution 2
We seek the number of allowed numbers which have 1's, not including the leading 1, for .
For , this number is
.
By the Hockey Stick Identity, this is equal to . So we get
.
For , we end on - we don't want to consider numbers with more than 11 digits. So for each we get
again by the Hockey Stick Identity. So we get
.
The total is . Subtracting out the numbers between and gives . Thus the answer is .
Solution 3
We will count the number of it instead of (In other words, the length of the base-2 representation is at most . If there are even digits, , then the leftmost digit is , the rest, , has odd number of digits. In order for the base-2 representation to have more 's, we will need more in the remaining than 's. Using symmetry, this is equal to Using similar argument where there are odd amount of digits. The remaining even amount of digit must contains the number of 's at least as the number of 's. So it's equal to Summing both cases, we have . There are numbers between and inclusive that satisfy it. So the answer is
~minor edits by minediamonds
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.