HMMT 十一月 2024 · GEN 赛 · 第 10 题

HMMT November 2024 — GEN Round — Problem 10

专题: Discrete Math / 离散数学
难度: L3
来源: HMMT

题目详情

Let S = { 1 , 2 , 3 , . . . , 64 } . Compute the number of ways to partition S into 16 arithmetic sequences such that each arithmetic sequence has length 4 and common difference 1 , 4 , or 16 .

解析

Let S = { 1 , 2 , 3 , . . . , 64 } . Compute the number of ways to partition S into 16 arithmetic sequences such that each arithmetic sequence has length 4 and common difference 1, 4, or 16. Proposed by: Isabella Zhu Answer: 203 Solution: The key observation is the following: Claim 1. No partition can contain all three common differences. Proof. Indeed, suppose the sequences x , x + 16, x + 32, x + 48 and y , y + 4, y + 8, y + 12 are both present for some x and y in S . Without loss of generality, assume y ≤ 26; otherwise, we can take our partition and replace each number n with 65 − n , resulting in the sequence 53 − y , 57 − y , 61 − y , 65 − y instead. Note that y ̸ ≡ x mod 4, as otherwise one of y , y + 4, y + 8, or y + 12 would be equivalent to x modulo 16 and the two sequences would intersect. Hence, there exists a number z strictly between y and y + 4 which is equivalent to x modulo 4. The same argument above tells us z cannot be in a difference-4 sequence; it also cannot be in a difference-1 sequence, as such a sequence would contain either y or y + 4. Thus z is in a difference-16 sequence. Similarly, as z + 4 lies between y + 4 and y + 8, and z + 8 lies between y + 8 and y + 12, both z + 4 and z + 8 are in difference-4 sequences. Since we assumed y ≤ 26, we know y + 32 ∈ S . Note that y + 20 cannot be part of a difference-16 sequence, as such a sequence would also contain y + 4. Furthermore, y + 20 lies between z + 16 and z + 20, both of which are in difference-4 sequences; hence, y + 20 cannot be part of a difference-1 sequence. Thus y + 20 is in a difference-4 sequence. This sequence must contain either y + 16 or both y + 28 and y + 32. If the sequence contains y + 16, then since z + 12 lies strictly between y + 12 and y + 16, the same argument as before tells us z + 12 is in a difference-16 sequence. If the sequence contains y + 28 and y + 32, then z + 28 lies strictly between the two, so z + 28 is in a difference-16 sequence; this sequence contains z + 12. In either case, z + 12 is in a difference-16 sequence. Now, we know z , z + 4, z + 8, and z + 12 are all in difference-16 sequences. These sequences contain all 16 numbers in the same residue class as z modulo 4. Any difference-1 sequence would have to contain a value in this residue class; thus, no difference-1 sequences can be present. We casework on which types of sequences are present. Case 1: Only sequences of common difference 1 and 16 appear. Observe that each sequence of common difference 1 has one number of each residue class modulo 4, while each sequence of common difference 16 has four numbers in the same residue class. Since S has an equal number of elements in each residue class, there must be an equal number of difference-16 sequences in each residue class, so the number of difference-16 sequences is a multiple of 4. Say there are 4 x of them. Then, among the numbers 1 through 16, there are 4 x of them that lie in difference-16 sequences, so the remaining 16 − 4 x lie in 4 − x difference-1 sequences. Conversely, if we are given how the numbers from 1 through 16 are split between difference-1 and difference-16 sequences, we can uniquely recover the whole partition on S . Indeed, the difference-16 sequences are fixed, which in turn fixes the difference-1 sequences. Thus, the number of sequences in this case is the number of ordered partitions of 16 into 4 x 1s and 4+3 x 4 − x 4s, which is . Summing over all x , the total for this case is 4 − x 16 13 10 7 4

- - - = 95 . 0 1 2 3 4 Case 2: Only sequences of common difference 4 and 16 appear. Within the multiples of 4, any difference-4 and difference-16 sequence intersect, so the 16 multiples of 4 must be covered with either four difference-4 sequences or four difference-16 sequences. The same goes for each residue class mod 4, and we can make each choice independently. Thus the number of 4 partitions in this case is 2 = 16. Case 3: Only sequences of common difference 1 and 4 appear. Observe that if x and x + 4 are in a difference-4 sequence, then x + 1, x + 2, and x + 3 must also be in difference-4 sequences, so the difference-4 sequences form contiguous blocks of length 4 · 4 = 16. The difference-1 sequences are themselves contiguous blocks of length 4, so the number of sequences in this case is the number of ordered partitions of 64 into 4s and 16s. This is the same as the number of ordered partitions of 16 into 1s and 4s, which we calculated in Case 1; there are 95 of them. Summing over all cases, we get 95 + 16 + 95 = 206. However, we overcount any partition with only one type of sequence, of which there are three (one for each type). Thus, the answer is 206 − 3 = 203 .