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

m
Line 5: Line 5:
 
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.
 
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.
  
So, there are 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, one for each subset of <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9\}</math>.
+
So, there are 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> potential ascending numbers, one for each [[subset]] of <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9\}</math>.
  
 
However, we've counted one-digit numbers and the [[empty set]], so we must subtract them off to get our answer, <math>\displaystyle 512-10=502.</math>
 
However, we've counted one-digit numbers and the [[empty set]], so we must subtract them off to get our answer, <math>\displaystyle 512-10=502.</math>
  
 
== See also ==
 
== See also ==
* [[1992 AIME Problems]]
 
 
* [[1992_AIME_Problems/Problem_1 | Previous problem]]
 
* [[1992_AIME_Problems/Problem_1 | Previous problem]]
 
* [[1992_AIME_Problems/Problem_3 | Next problem]]
 
* [[1992_AIME_Problems/Problem_3 | Next problem]]
 +
* [[1992 AIME Problems]]

Revision as of 23:22, 14 September 2006

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

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: $\displaystyle 1,2,3,4,5,6,7,8,9.$ Note that each digit may be present or may not be present. Hence, there are $\displaystyle 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, $\displaystyle 512-10=502.$

See also