3
$\begingroup$

Question: Call a positive integer monotonous if it is a one-digit number or its digits, when read from left to right, form either a strictly increasing or decreasing sequence. For example, 3, 23578, and 987620 are monotonous, but 88, 7434, and 23557 are not. How many monotonous positive integers are there?

I attempted to solve the following problem by finding out how many 2-digit and 3-digit monotonous numbers there are and then finding the pattern within them and applying them all the way to the max number of digits in a monotonous number - 9. I figured that when the tens digit is 0, there are 9 possible combinations for the ones digit, when the tens digit is 1, there are 8 possible combinations, and so forth. Thus with 1+2+3+4+5+6+7+8+9 I arrived at 45 increasing monotonous numbers for 2-digit numbers. Then as there is one decreasing monotonous number for every increasing monotonous number, I multiplied it by 2 to get 90 total 2-digit monotonous numbers. However I can not figure out how to accomplish this for 3-digit numbers. Can someone please help me with this, or if there is a more efficient method, could you please explain it? Thanks a lot!

$\endgroup$
  • $\begingroup$ Why is $23557$ non monotonous? Isn't it increasing from left to right? Also, why is $323578$ a monotonous number? $\endgroup$ – S.C.B. Feb 16 '17 at 1:46
  • $\begingroup$ It cannot have repetitions of any digits. Additionally the second example does not count as a monotonous number as it doesn't decrease continuously with all the digits. $\endgroup$ – celestialwayfarer Feb 16 '17 at 1:48
  • $\begingroup$ I don't have a solution but I can see that it would be useful to note that all strictly monotonous 3 digit numbers have strictly monotonous 2 digit prefixes. $\endgroup$ – Q the Platypus Feb 16 '17 at 1:52
  • $\begingroup$ "I figured that when the tens digit is 0, there are 9 possible combinations for the ones digit,": Are you counting $01, 02,03$, etc., as separate from $1,2,3,$ etc.? $\endgroup$ – Jonas Meyer Feb 16 '17 at 2:00
  • $\begingroup$ No those would be counted the same. That is why I started counting with the 2-digit numbers as the 1-digit numbers would already be included within this set. $\endgroup$ – celestialwayfarer Feb 16 '17 at 2:02
4
$\begingroup$

Consider the string $9876543210$. We can choose or ignore each digit from this string to get decreasing monotonous numbers for a total of $2^{10}=1024$ options. Since that includes ignoring all of the digits and only choosing $0$, there are $1022$ valid choices that yield positive numbers.

Similarly we can choose from the string $123456789$ to get $2^9-1=511$ options for increasing monotonous numbers.

Finally, noting that the $9$ single-digit numbers belong to both groups, the total count of different monotonous numbers is $1022+511-9=1524$.

$\endgroup$
1
$\begingroup$

There are $10$ digits and $10 \choose n$ ways to choose $n$ distinct digits (which must be distinct to preserve strict monotonicity). There is exactly one way to arrange those $n$ digits in decreasing order. Thus there are \begin{align*} {10\choose1}+\dots+{10\choose10}&={10\choose0}1^01^{10-0}+\dots+{10\choose10}1^{10}1^{10-10}-1\\ &=(1+1)^{10}-1\\ &=2^{10}-1\\ &=1023\\ \end{align*} strictly decreasing non-negative integers. This counted the number $0$, so subtract one from our result for $1022$ strictly decreasing positive integers.

Next consider increasing integers. Anything with $1$ digit has already been counted, so we only want numbers with $2$ or more digits. Additionally, none of these integers will have the digit $0$, since it would be the first digit, yielding a result with a smaller number of digits. We similarly find \begin{align*} {9\choose2}+\dots+{9\choose9}&=2^9-10\\ &=502\\ \end{align*} additional strictly increasing positive integers.

Adding these two results together yields $\boxed{1524}$ total monotonous positive integers.

$\endgroup$
  • $\begingroup$ $1023+502=1525$ so why is the answer $1524$? $\endgroup$ – Old Peter Jun 12 '18 at 18:53
  • 1
    $\begingroup$ The original question asked about positive integers, and the $1023$ count included the number $0$. Just afterward, you'll notice we subtracted $1$ to get a total of $1022$ instead, yielding the desired result of $1022+502=1524$. $\endgroup$ – Hans Musgrave Jun 12 '18 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.