프로젝트 오일러 113번

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 133468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As \(n\) increases, the proportion of bouncy numbers below \(n\) increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below \(10^{10}\).

How may numbers below a googol \(\left (10^{100} \right )\) are not bouncy?

---

133468 처럼 왼쪽에 위치한 자릿수가 오른쪽에 위치한 자릿수보다 작거나 같은 수를 증가수(increasing number)라고 한다. 반대로 66420 처럼 왼쪽에 위치한 자릿수가 오른쪽에 위치한 자릿수보다 크거나 같은 수를 감소수(decreasing number)라고 한다. 

또한 155349 처럼 증가수도 아니고 감소수도 아닌 자연수를 바운시 수(bouncy number) 라고 하자. 

\(n\) 이 증가함에 따라 \(n\) 미만의 바운시 수 비율은 점점 커지게 된다. 예를 들어, \(10^6\) 미만의 수 중 바운시 수가 아닌 것들의 개수는 12951개 이고, \(10^{10}\) 미만의 수 중 바운시 수가 아닌 것들의 개수는 277032개 이다.

그렇다면 \(10^{100}\) 미만의 수 중 바운시 수가 아닌 것의 개수는 몇 개일까?   

사실 이 문제는 고2 과정에서 배우게 되는 중복조합에 대한 개념만 있다면 프로그래밍이 필요없는 문제다.

먼저 increasing number를 생각해 보자.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 의 10개의 숫자로 \(n\) 자리 숫자를 만들면서 increasing이 되게 하려면 10개의 숫자에서 중복조합으로 \(n\) 개의 숫자를 뽑으면 된다. 조합이라는 것은 순서 없이 뽑겠다는 것인데, 일단 숫자들이 뽑히면 증가하는 순으로 나열할 것이기 때문에 순서를 고려할 필요가 없다. 우리는 단지 중복으로 \(n\) 개의 숫자를 뽑기만 하면 된다. 예를 들어, 4자리 수를 만드는데 1, 1, 4, 9 가 뽑혔다고 한다면 자연스럽게 1149라는 수가 만들어진다. 또는 0, 0, 1, 7 이 뽑혔다면 0017로 나열될 것이고, 이는 그냥 두 자리 숫자 17로 생각하면 된다. 즉, 4자리 까지의 increasing number를 만들려면 \(_{10} {\rm H} _4\) 를 해 주면 되는 것이다. 이렇게 하면 자연스럽게 1자리 수부터 4자리 수까지 increasing number 들의 개수를 알아낼 수 있다. 다만 모든 자리가 0으로 채워지는 경우도 포함되기 때문에 1을 빼줘야 한다. \[_{10} {\rm H} _n =\; _{10+n-1} {\rm C}_n =\;  _{9+n} {\rm C}_n\]이므로 \(10^n\) 미만의 수 중 increasing number 의 개수는  \(_{9+n}{\rm C}_n -1\) 이 된다.

이제 decreasing number를 생각해 보자.

단순하게 생각하면 decreasing은 increasing의 역순이므로 increasing의 경우와 그 개수가 똑같을 것 같지만, 조금만 더 생각해보면 그렇지 않다는 것을 알 수 있다. 여기서는 다음의 두 가지를 주의해야 한다.

첫 째, increasing 에서 4자리 수를 만들 때, 0, 0, 1, 7이 뽑히면 17이라는 두 자리 수로 생각하자고 했었다. 이것의 역순은 7100이 되는 것인가 아니면 두 자리 수 71이 되는 것인가? 여기서는 이 두 가지를 구분해야 한다. 이를 위해서는 각 자리수 별로 중복조합을 적용하여야 한다. 예를 들어, \(10^n\) 미만의 수 중 decreasing number의 개수를 알고 싶으면 1자리 수, 2자리 수, \(\cdots\), \(n\)자리 수 까지의 decreasing number를 각각 따로 고려해야 한다.

둘 째, 같은 숫자로만 이루어진 수들은 이미 increasing에서 고려 했으므로 decreasing에서는 제외하여야 한다. 즉, 모든 자리의 숫자가 \(i \;( i= 1,\; 2,\; \cdots,\; 9)\) 로 이루어진 수들은 모두 제외하여야 한다. 또한 \(0\) 으로만 이루어진 수 들도 increasing 에서와 마찬가지로 제외해야 한다.

위 두 가지 조건을 생각하면서 \(10^n\) 미만의 수 중 decreasing number 의 개수를 계산하면 \[(_{10}{\rm H}_1 -10) + ( _{10}{\rm H}_2 - 10) + ( _{10}{\rm H}_3 -10) + \cdots + ( _{10}{\rm H}_n -10)\] 이 된다. 각각에서 \(10\)을 빼 주는 이유는 앞에서 설명했듯이 모든 자리의 수가 \(i\; ( i=0. \;1,\; 2,\; 3,\; \cdots, \; 9)\) 로 이루어진 경우를 빼줘야 하기 때문이다. \(_n{\rm H}_r = _{n+r-1}{\rm C}_r\) 이므로  위 식을 정리하면 \[ _{10}{\rm C}_1 + {_{11}} {\rm C}_2 + {_{12}}{\rm C}_3 + \cdots + {_{9+n}}{\rm C}_n -(10 \times n)\] 이 된다. 또한 \(_n{\rm C}_{r-1} + {_n}{\rm C}_r = {_{n+1}}{\rm C}_r\) 이므로  \(_{10}{\rm C}_0\)을 한 번 더해주고 빼 준 후, 위 식을 변형하면 \[ _{10}{\rm C}_0 +{_{10}}{\rm C}_1 + {_{11}} {\rm C}_2 + {_{12}}{\rm C}_3 + \cdots + {_{9+n}}{\rm C}_n -(10 \times n) - {_{10}}{\rm C}_0\]\[_{11}{\rm C}_1 +   {_{11}} {\rm C}_2 + {_{12}}{\rm C}_3 + \cdots + {_{9+n}}{\rm C}_n -(10 \times n) - 1\]\[{_{12}} {\rm C}_2 + {_{12}}{\rm C}_3 + \cdots + {_{9+n}}{\rm C}_n -(10 \times n) - 1\]\[{_{13}}{\rm C}_3 + \cdots + {_{9+n}}{\rm C}_n -(10 \times n) - 1\]\[\vdots\]\[_{10+n}{\rm C}_n -10n -1\]이 된다. 결국 \(10^n\) 미만의 decreasing number의 개수는 \[_{10+n}{\rm C}_n -10n -1\] 개가 된다. 따라서 우리가 구하는 수는 increasing number와 decreasing number의 개수를 더한 \[ _{9+n}{\rm C}_n +{_{10+n}}{\rm C}_n -10n -2\] 가 된다.

이 문제의 정답은 \(n\) 대신에 \(100\)을 대입하여 얻을 수 있다.