PUMaC 2022 · 团队赛 · 第 15 题

PUMaC 2022 — Team Round — Problem 15

Subsets S of the first 35 positive integers { 1 , 2 , 3 , ..., 35 } are called contrived if S has size 4 and the sum of the squares of the elements of S is divisible by 7. Find the number of contrived sets. Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Your input I (for bonus points): 2

解析

Subsets S of the first 35 positive integers { 1 , 2 , 3 , ..., 35 } are called contrived if S has size 4 and the sum of the squares of the elements of S is divisible by 7. Find the number of contrived sets. Proposed by Sunay Joshi Answer: 8605 2 2 2 There are four distinct quadratic residues modulo 7, namely 0 , 1 , 2 , 4, with 0 ≡ 0, 1 , 6 ≡ 1, 2 2 2 2 3 , 4 ≡ 2, and 2 , 5 ≡ 4. There are five 4-tuples ( a , a , a , a ) with a < a < a < a 1 2 3 4 1 2 3 4 and a ∈ { 0 , 1 , 2 , 4 } satisfying a + a + a + a ≡ 0, namely (0 , 0 , 0 , 0), (0 , 1 , 2 , 4), (1 , 1 , 1 , 4), i 1 2 3 4 (1 , 2 , 2 , 2), and (2 , 4 , 4 , 4). Among the first 35 positive integers, there are 5 numbers x with 2 2 2 2 x ≡ 0, 10 numbers with x ≡ 1, 10 numbers with x ≡ 2, and 10 numbers with x ≡ 4. Thus 3 5 5 10 10 10 10 10 10 10 each 4-tuple corresponds to , , , , and subsets, respectively. 4 1 1 3 1 3 1 3 1 3 Our answer is therefore 5 + 5 · 10 + 120 · 10 + 120 · 10 + 120 · 10 = 8605. 8