Problem:
Call a positive integer fair if no digit is used more than once, it has no s, and no digit is adjacent to two greater digits. For example, , and are fair, but , and are not. How many fair positive integers are there?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Claim. The smallest digit must appear on one of its ends.
Proof. Let be a set of digits, and let denote the smallest element of the set.
Assume, for the sake of contradiction, that is not positioned at either end of a fair arrangement.
Then would have two neighbors, both of which must be greater than , since it is the smallest digit in .
This violates the definition of a fair arrangement, which prohibits any digit from being adjacent to two larger digits.
Therefore, the smallest digit must always occupy one of the end positions. This completes the proof of the claim.
Once the smallest digit has been placed at an end, we must verify that the remaining digits continue to form a fair arrangement.
This is achieved by repeating the same logic on the reduced set , where we again identify and place the smallest remaining digit at one of the ends.
To visualize this process, imagine constructing the arrangement step by step.
Begin with the smallest digit, then sequentially insert each next-smallest digit at either the left end or the right end of the current sequence.
If there are digits in total, the first digit can be placed in either end position ( options).
At each subsequent step, the next-smallest digit can again be placed on either the left or right end.
This continues until all but one digit is placed, leaving a single remaining position for the final digit.
Hence, for a set with digits, the total number of fair arrangements is
Now, we will count all fair integers. Choose the digits (no ) in ways and arrange them fairly in ways. Summing over ,
Multiply both sides by and add :
Thus
Since , the total number of fair positive integers is
The problems on this page are the property of the MAA's American Mathematics Competitions