Difference between revisions of "1992 AIME Problems/Problem 2"

(Solution)
 
(6 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
A positive integer is called ascending if, in its decimal representation, there are at least two digits and each digit is less than any digit to its right. How many ascending positive integers are there?
+
A [[positive integer]] is called ascending if, in its [[decimal representation]], there are at least two digits and each digit is less than any digit to its right. How many ascending positive integers are there?
  
== Solution ==
+
== Solution 1 ==
First, we line up the nine digits that may be used: <math>\displaystyle 1,2,3,4,5,6,7,8,9.</math> Note that each digit may be present or may not be present. Hence, there are <math>\displaystyle 2^9=512</math> working numbers.
+
Note that an ascending number is exactly determined by its [[digit]]s: for any [[set]] of digits (not including 0, since the only position for 0 is at the leftmost end of the number, i.e. a leading 0), there is exactly one ascending number with those digits.
  
Subtracting off the one-digit numbers and the null set, our answer is <math>\displaystyle 512-10=502.</math>
+
So, there are nine digits that may be used: <math>1,2,3,4,5,6,7,8,9.</math>  Note that each digit may be present or may not be present. Hence, there are <math>2^9=512</math> potential ascending numbers, one for each [[subset]] of <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9\}</math>.
  
== See also ==
+
However, we've counted one-digit numbers and the [[empty set]], so we must subtract them off to get our answer, <math>512-10=\boxed{502}.</math>
* [[1992 AIME Problems]]
+
 
 +
== Solution 2 ==
 +
We see that we can express the number of ways for a 2 digit number as <math>\binom{8}{1}+\binom{7}{1}...\binom{1}{1}</math> and a 3 digit number as <math>\binom{8}{2}+\binom{7}{2}+...\binom{2}{2}</math> this is because once we choose the first number the next two numbers can be any two of the numbers above it. Using the hockey stick identity repeatedly we can get <math>\binom{9}{2}+\binom{9}{3}+...+\binom{9}{9}</math>. We know that <math>\binom{n}{0}+\binom{n}{1}+...\binom{n}{n}=2^n</math> this can be proved easily by story. If you have n people and you want to know how many ways you can make a group of any size you could do this <math>2</math> ways. You could count everyone is binary in or out so <math>2^n</math> or you could count each case individually: <math>\binom{n}{0}+\binom{n}{1}+...\binom{n}{n}</math> so the 2 statements are equivalent. Therfore we have <math>2^9-\binom{9}{1}-\binom{9}{0}=\boxed{502}</math>
 +
Note how you could have skipped the hockey stick step by choosing all the numbers first.
 +
 
 +
{{AIME box|year=1992|num-b=1|num-a=3}}
 +
{{MAA Notice}}

Latest revision as of 00:05, 5 December 2018

Problem

A positive integer is called ascending if, in its decimal representation, there are at least two digits and each digit is less than any digit to its right. How many ascending positive integers are there?

Solution 1

Note that an ascending number is exactly determined by its digits: for any set of digits (not including 0, since the only position for 0 is at the leftmost end of the number, i.e. a leading 0), there is exactly one ascending number with those digits.

So, there are nine digits that may be used: $1,2,3,4,5,6,7,8,9.$ Note that each digit may be present or may not be present. Hence, there are $2^9=512$ potential ascending numbers, one for each subset of $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

However, we've counted one-digit numbers and the empty set, so we must subtract them off to get our answer, $512-10=\boxed{502}.$

Solution 2

We see that we can express the number of ways for a 2 digit number as $\binom{8}{1}+\binom{7}{1}...\binom{1}{1}$ and a 3 digit number as $\binom{8}{2}+\binom{7}{2}+...\binom{2}{2}$ this is because once we choose the first number the next two numbers can be any two of the numbers above it. Using the hockey stick identity repeatedly we can get $\binom{9}{2}+\binom{9}{3}+...+\binom{9}{9}$. We know that $\binom{n}{0}+\binom{n}{1}+...\binom{n}{n}=2^n$ this can be proved easily by story. If you have n people and you want to know how many ways you can make a group of any size you could do this $2$ ways. You could count everyone is binary in or out so $2^n$ or you could count each case individually: $\binom{n}{0}+\binom{n}{1}+...\binom{n}{n}$ so the 2 statements are equivalent. Therfore we have $2^9-\binom{9}{1}-\binom{9}{0}=\boxed{502}$ Note how you could have skipped the hockey stick step by choosing all the numbers first.

1992 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 1
Followed by
Problem 3
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. AMC logo.png

Invalid username
Login to AoPS