HMMT 二月 2024 · COMB 赛 · 第 10 题
HMMT February 2024 — COMB Round — Problem 10
题目详情
- A peacock is a ten-digit positive integer that uses each digit exactly once. Compute the number of peacocks that are exactly twice another peacock.
解析
- A peacock is a ten-digit positive integer that uses each digit exactly once. Compute the number of peacocks that are exactly twice another peacock. Proposed by: Albert Wang Answer: 184320 Solution: We begin with the following observation: Claim 1. Let x be a peacock. Then, 2 x is a peacock if and only if: • the multiplication x · 2 uses five carries, • each of the pairs of digits (0 , 5) , (1 , 6) , (2 , 7) , (3 , 8) , (4 , 9) receives exactly one carry. • The leading digit is not 5 , 6 , 7 , 8 , 9 . Proof. After the multiplication of x · 2 , we will have a ten digit number. Let’s first consider the output without carrying. It consists of the digits 0 , 2 , 4 , 6 , 8 twice each, occupying positions where pairs of digits (0 , 5) , (1 , 6) , (2 , 7) , (3 , 8) , (4 , 9) were in x . However, we guaranteed that one digit from each pair received a carry, meaning all ten digits are present after adding in the carries. We will now biject all peacocks to the following combination of objects: • a queue of low digits 0 , 1 , 2 , 3 , 4 , in any order with the constraint that 0 is not first, • a queue of high digits 5 , 6 , 7 , 8 , 9 , in any order, and • of each of the pairs of digits (0 , 5) , (1 , 6) , (2 , 7) , (3 , 8) , (4 , 9) mark one of them to receive a carry, except we are not allowed to mark the final digit in the high queue. We construct a correspondence from these objects to peacocks by accumulating digits to an initially empty string. We’ll say that we poll a queue by popping its front entry and appending it to the end of this string. First, poll the low queue. Then, if we have just polled a marked digit, poll the high queue; otherwise, poll the low queue. We repeat this until all queues are emptied. As an example of this process, let our low queue be 1 , 4 , 0 , 2 , 3 , our high queue be 8 , 5 , 9 , 6 , 7 , and mark the digits 0 , 1 , 2 , 3 , 9 marked to receive a carry. Our steps are as follows: • Poll the low queue, so that our string is now 1 . • Since 1 was marked to receive a carry, we poll the high queue, making our string 18 . • Since 8 was not marked, we poll the low queue to reach 184 . • Since 4 was not marked, we poll the low queue to reach 1840 . • Since 0 was marked, we poll the high queue to reach 18405 . • etc. In the end, we will construct the peacock 1840529637 , which is the one shown earlier to work. Claim 2. Any string of digits x constructed through this process will be a peacock that satisfies the constraints outlined in Claim 1 . Low queue 1 4 0 2 3 High queue 8 5 9 6 7 The order in which digits get polled to construct 1840529637; note the 4 connected components in the high queue. The circled digits are those that have been marked for carrying. Proof. We first argue that all digits end up being polled. In particular, if a high digit is marked, let’s connect it by an edge to the digit on its right (using the requirement that the last digit is not marked). If h of the high digits are marked, then we will have 5 − h connected components among these high digits. However, we then have 5 − h marked digits in the low queue, and every time we poll a marked low digit we will end up polling all digits from the next connected component in the high queue. So, all digits end up being polled. Notice that our marked digits will always be followed immediately by a high digit, satisfying the first and second conditions of the claim. As we do not start with a high digit, the third constraint is satisfied. Therefore any peacock x output by this process will also have 2 x a peacock. Since we always use all the digits, this process is evidently injective. To map from peacocks back to these sequences of digits, we can just let the queues be the order of appearances of the low and high digits in the peacock, and mark the carried digits accordingly. Indeed, we notice that this mapping is also injective. Using this bijection, we just need to find the number of initial settings of the queues and marked digits. There are 4 · 4! ways to order the low number queue. There are then 5! ways to order the high number 4 queue. Finally, of each of the four pairs of digits not inluding the final high digit, there are 2 ways to mark them. This gives an answer of 4 4 · 4! · 5! · 2 = 184320 .