Given an integer $ k > 1.$ We call a $ k -$digits decimal integer $ a_{1}a_{2}\cdots a_{k}$ is $ p -$monotonic, if for each of integers $ i$ satisfying $ 1\le i\le k - 1,$ when $ a_{i}$ is an odd number, $ a_{i} > a_{i + 1};$ when $ a_{i}$ is an even number, $ a_{i}<a_{i + 1}.$ Find the number of $ p -$monotonic $ k -$digits integers.
Problem
Source: Chinese TST 2007 3rd quiz P2
Tags: combinatorics proposed, combinatorics
goodar2006
10.04.2011 17:47
I solved it using a lot of brutal force by solving $6$ recurrence relations. does anyone have a better way for solving this problem?
math_explorer
15.04.2011 03:35
Relabel the digit $a_i$ as a pair $(x_i, y_i)$ where $2x_i + y_i = a_i$, $x_i \in \{0, 1, 2, 3, 4\}$, and $y_i \in \{0, 1\}$. Clearly, there's exactly one relabeling for each digit. Now, suppose we're given arbitrary values (from $\{0, 1, 2, 3, 4\}$) for $x_i$. We find that $y_k$ can be chosen arbitrarily, but once that happens $a_k$ is determined and there is exactly one choice for $y_{k-1}$. Similarly this determines $a_{k-1}$, there's exactly one choice for $y_{k-2}$. So, choosing the values of $x_i$ and $y_k$ uniquely determines such a $k$-digit number, so we have $2\cdot 5^k$ such numbers. If $a_1 = 0$ is prohibited, just note that chopping off the $0$ corresponds our number to a $k-1$-digit number which doesn't begin with $0$, and use PIE.
FinalSix
20.06.2013 07:18
I really think that it is an ACM(I mean program competition) problem. If you know dp(dynamic programming),it will be easy a lot.
P-H-David-Clarence
30.10.2016 04:54
Beautiful! The solution is so fantastic!