PUMaC 2022 · 组合（A 组） · 第 3 题
PUMaC 2022 — Combinatorics (Division A) — Problem 3
题目详情
- Randy has a deck of 29 distinct cards. He chooses one of the 29! permutations of the deck and then repeatedly rearranges the deck using that permutation until the deck returns to its original order for the first time. What is the maximum number of times Randy may need to rearrange the deck? n
解析
- Randy has a deck of 29 distinct cards. He chooses one of the 29! permutations of the deck and then repeatedly rearranges the deck using that permutation until the deck returns to its original order for the first time. What is the maximum number of times Randy may need to rearrange the deck? 1 Proposed by Aditya Gollapudi and Owen Yang Answer: 2520 Every permutation can be decomposed into disjoint cycles, so the number of times Randy shuffle the deck for a given permutation is equal to the least common multiple of the lengths of these cycles. Thus, we want to maximize the LCM of these lengths under the constraint that the lengths sum to 29. Since length 1 cycles do not increase the LCM, we may instead assume that the lengths are greater than one and have sum at most 29 (which we can compensate for by creating many cycles of length 1). We may also assume that these lengths are relatively prime, since removing a common factor from one of the lengths does not change the LCM and decreases the total sum. If we have three cycle lengths that are not equal to 1, say a, b, c , then by AM-GM we have a + b + c 3 3 lcm( a, b, c ) = abc ≤ ( ) < 10 = 1000. Similar proofs show that we cannot have only 3 one or two cycle lengths. On the other hand, if we have five cycle lengths not equal to 1, then the set of 5 relatively prime numbers with smallest sum is 2 , 3 , 5 , 7 , 11 which has sum 28, which has LCM 2310. Any other set of 5 relatively prime numbers has a sum larger than 29. Furthermore, the smallest sum of 6 or more relatively prime numbers is more than 29. Thus, we need only consider sets of four cycle lengths; call them a, b, c, d . Note that 5 + 7 + 8 + 9 = 29 and these four numbers have LCM 2520. Since a ̸ = b ̸ = c ̸ = d and each number is as close 29 to the mean as possible, the only other possible maximum is at { a, b, c, d } = { 5 , 6 , 8 , 10 } , 4 which gives a smaller LCM. Thus, the answer is 2520. n