Question

An integer is called parity-monotonic if its decimal representation $a_1 a_2 a_3 \ldots a_k$ satisfies $a_i \lt a_{i+1}$ if $a_i$ is odd, and $a_i \gt a_{i+1}$ if $a_i$ is even. How many four-digit parity-monotonic integers are there?

Answer

Solution:

A digit $a_i$ may immediately precede $a_{i+1} = d$ exactly when $a_i$ is odd and less than $d,$ or even and greater than $d.$ Checking each $d$ from $0$ to $9,$ this always allows exactly $4$ digits: for example, $d = 0$ allows $2, 4, 6, 8;$ $d = 4$ allows $1, 3, 6, 8;$ $d = 9$ allows $1, 3, 5, 7.$ (Raising $d$ by $1$ trades odd choices for even ones, keeping the total at $4.$ ) Note that $0$ is never an allowed predecessor, since $0$ is even but exceeds no digit.

So choose the last digit $a_4$ in $10$ ways, then each of $a_3,$ $a_2,$ $a_1$ in $4$ ways; the leading digit is automatically nonzero. The count is $4^3 \cdot 10 = 640.$

2007 AIME II Problem 6

Solution:

Problem 6 in Other Years