Problem:
A positive integer is stacked if has the same number of digits as and the digits of are multiples of the corresponding digits of . For example, is stacked because , and are multiples of , respectively. Compute the number of stacked integers less than .
Solution
Solution:
We do casework on the number of digits of .
One digit. There are one-digit stacked integers: .
Two digits. Suppose is a two-digit integer. If and , then the digits of are double the respective digits of , so is stacked; there are such . Otherwise, since , we still must have , so . Then the last digit of is , so , which implies that . Then the first digit of is , which must divide, so . Thus, the only stacked with is . Adding that to the stacked numbers with gives us two-digit stacked integers.
Three digits. Suppose is a three-digit integer. If , and are all less than , then the digits of are double the respective digits of , so is stacked; there are such . Otherwise, since , we must have . We now casework on which of and are at least .
- If and , then the digits of are , and in order. Thus, , , and , which implies , , and . Thus is the only stacked number in this case.
- If only, then has first digit and last two digits , so is stacked if and only if to be stacked. Since , as proved before, the only such stacked is , so we get stacked numbers in this case: , and .
- If only, then has last digit and first two digits , so is stacked if and only if to be stacked. As , similar to the previous case, the only such stacked is , so we get stacked numbers in this case: , and .
Summing over all cases, there are three-digit stacked integers.
Our final answer is .