Problem:
Define an upno to be a positive integer of or more digits where the digits are strictly increasing moving left to right. Similarly, define a downno to be a positive integer of or more digits where the digits are strictly decreasing moving left to right. For instance, the number is an upno and is a downno. Let equal the total number of upnos and equal the total number of downnos. What is ?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Note that an upno is completely determined by the selection of 2 or more elements from the set . Because a set with 9 elements has subsets, including the empty set and 9 one-element subsets, there are upnos, so . By similar logic using the set , there are downnos, so . Thus .
For every upno, there is a corresponding downno formed by reversing the digits. The downnos that are not created in this way must end in 0 . There are non-empty subsets of , each of which corresponds to a unique downno ending in 0 . Thus .
The problems on this page are the property of the MAA's American Mathematics Competitions