3
$\begingroup$

I've been preparing for Mathcounts competition, but this one question confused me a bit.

If a stairstep number is defined as a number whose digits are strictly increasing in value from left to right, how many positive integers containing two or more digits are stairstep numbers?

So what I did was to do casework (separating it into "2 digits', "3 digits", "4 digits"... and so on till "9 digits" which obviously would be the last possible one and has only 1 number that meets the requirements). And each time I focused on the units digit - so for example for 4-digit number like 123a, there'd be 6 a's possible. And for 134a, there would be 5 a's possible and that's how I went on to add up all the nubmers and I got 243 total (I doublechecked the whole process).

But the answer's supposed to be 502. Where did I go wrong or what other ways are there to solve this?

$\endgroup$
3
  • $\begingroup$ A stairstep number is determined by the set of its digits. How many possible sets are there? $\endgroup$
    – Daniel Fischer
    Commented Feb 22, 2016 at 17:57
  • $\begingroup$ To add to the comment by Daniel Fischer, there are $2^9$ subsets of the set $\{1,2,\dots,9\}$, of which $10$ (the empty set and the $9$ one-element sets) are forbidden. $\endgroup$
    – André Nicolas
    Commented Feb 22, 2016 at 18:04
  • $\begingroup$ Thinking of an elevator instead of stairs, the stairstep numbers correspond to the ways of taking an up elevator from the $0$th floor of a building to the $10$th floor making at least two stops. The digits of the stairstep number are the floors at which the elevator stops, and each way of doing this is determined by the set of intermediate floors at which the elevator stops. $\endgroup$
    – Steve Kass
    Commented Feb 22, 2016 at 18:07

2 Answers 2

Reset to default
3
$\begingroup$

Take a stairstep number $n$. The digit $1$ either appears or not in $n$: this gives two possibilities. The same holds for each other digit $2,3,\ldots,9$. In total, there are $$2^9 = 512$$ possibilities. But this includes the "$0$-digit" number, which should not be counted, and $1$-digit numbers, which are not part of the definition. We must subtract them from the count of $512$; what does this give?

$\endgroup$
2
$\begingroup$

Note that the stairstep numbers that have $k$ digits correspond one-to-one with subsets of $\{1,2,\dots,9\}$ that have $k$ elements.

So for fixed $k\in\{2,3,\dots,9\}$ there are exactly:

$$\binom9k$$

stairstep numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .