PUMaC 2022 · 团队赛 · 第 6 题
PUMaC 2022 — Team Round — Problem 6
题目详情
- A sequence of integers x , x , ... is double-dipped if x = ax + bx for all n ≥ 1 and 1 2 n +2 n +1 n some fixed integers a, b . Ri begins to form a sequence by randomly picking three integers from the set { 1 , 2 , ..., 12 } , with replacement. It is known that if Ri adds a term by picking another 1 element at random from { 1 , 2 , ..., 12 } , there is at least a chance that his resulting four-term 3 sequence forms the beginning of a double-dipped sequence. Given this, how many distinct three-term sequences could Ri have picked to begin with? 2 1 2 2 1 2
解析
- A sequence of integers x , x , ... is double-dipped if x = ax + bx for all n ≥ 1 and 1 2 n +2 n +1 n some fixed integers a, b . Ri begins to form a sequence by randomly picking three integers from the set { 1 , 2 , ..., 12 } , with replacement. It is known that if Ri adds a term by picking another 1 element at random from { 1 , 2 , ..., 12 } , there is at least a chance that his resulting four-term 3 sequence forms the beginning of a double-dipped sequence. Given this, how many distinct three-term sequences could Ri have picked to begin with? Proposed by Austen Mazenko Answer: 84 The main idea is that for a sequence a , a , a , a fourth term a is double-dipped only when 1 2 3 4 2 a is a particular residue modulo | a − a a | . Thus, for there to be at least 4 such values of 4 1 3 2 a , this absolute value must equal 1 , 2, or 3; this gives casework. 4 2 If x ± 1 = x x : (double at end to reverse them) (1 , 1 , 2), (1 , 2 , 3), (1 , 2 , 5), (1 , 3 , 8), (2 , 3 , 4), 1 3 2 (1 , 3 , 10), (2 , 3 , 5), (3 , 4 , 5), (2 , 5 , 12), (3 , 5 , 8), (4 , 5 , 6), (5 , 6 , 7), (6 , 7 , 8), (4 , 7 , 12), (5 , 7 , 10), (7 , 8 , 9), (8 , 9 , 10), (9 , 10 , 11), (10 , 11 , 12). 2 If x ± 2 = x x : (double at end to reverse them) (1 , 1 , 3), (1 , 2 , 2), (1 , 2 , 6), (2 , 2 , 3), (1 , 3 , 7), 1 3 2 (1 , 3 , 11), (2 , 4 , 7), (2 , 4 , 9), (3 , 4 , 6), (3 , 5 , 9), (6 , 8 , 11). 2 If x ± 3 = x x : (double at end to reverse them) (1 , 1 , 4), (2 , 1 , 2), (1 , 2 , 1), (1 , 2 , 7), (1 , 3 , 6), 1 3 2 (2 , 3 , 3), (1 , 3 , 12), (2 , 3 , 6), (3 , 3 , 4), (2 , 5 , 11), (4 , 5 , 7), (3 , 6 , 11), (7 , 9 , 12). In sum, we get 84 (note that (2 , 1 , 2) and (1 , 2 , 1) in the last case are irreversible). 1 1 2 2 2 2