Skip to main content
OlympiadHQ

Browse · MathNet

Print

Japan Mathematical Olympiad

Japan counting and probability

Problem

Let us call a positive integer a good number if the digit appears more frequently than the digit , and a bad number if the digit appears more frequently than the digit . For example, is a good number because the digit appears twice and the digit once, and is neither a good number nor a bad number because the digit appears once and the digit once. Find the difference between the number of good numbers less than or equal to and the number of bad numbers less than or equal to .
Solution


For a positive integer , let us define the changed number of as the number obtained by switching each digit in to , and each digit in to . By this definition, if is the changed number of , then the changed number of is itself. For a good number and a bad number , we call a nice pair if is the changed number of .

Let be a good number. Let (respectively, ) be the number of times the digit (respectively, ) appears in . Then, we have . Let denote the changed number of . Then, the number of times the digit appears in is , and the number of times the digit appears in is . Hence, is a bad number. Furthermore, if , then we have . Note that a number cannot be both a good number and a bad number. These observations show that each good number less than or equal to is contained in exactly one nice pair. Similarly, each bad number less than or equal to is contained in exactly one nice pair. Therefore, the number of good numbers less than or equal to and the number of bad numbers less than or equal to are both equal to the number of nice pairs.

In addition, among the integers between and , there are good numbers (excluding and ) and no bad numbers. Thus, the answer is .
Final answer
22

Techniques

Recursion, bijectionCounting two ways