HMMT 二月 2018 · 冲刺赛 · 第 32 题
HMMT February 2018 — Guts Round — Problem 32
题目详情
- [ 17 ] How many 48-tuples of positive integers ( a , a , . . . , a ) between 0 and 100 inclusive have the 1 2 48 property that for all 1 ≤ i < j ≤ 48, a 6 ∈ { a , a + 1 } ? i j j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2018, February 10, 2018 — GUTS ROUND Organization Team Team ID#
解析
- [ 17 ] How many 48-tuples of positive integers ( a , a , . . . , a ) between 0 and 100 inclusive have the 1 2 48 property that for all 1 ≤ i < j ≤ 48, a 6 ∈ { a , a + 1 } ? i j j Proposed by: Mehtaab Sawhney 48 Answer: 54 (With Ashwin Sah) The key idea is write the elements of the sequence in increasing order. These sets are in bijection with solutions to d + . . . + d = 48 and a + . . . + a = 53 with d ≥ 1, a ≥ 1 for 1 k 1 k +1 i i ( ) 54 2 ≤ I ≤ k , and a , a ≥ 0. Notice that there are solutions to the second equation and then 1 k +1 k 48! there are solutions for each { d } set. Then this gives that the answer is i d ! ··· d ! 1 k ( ) ∑ ∑ 54 48! ∏ k k d ! i i =1 1 ≤ k ≤ 48 d + ... + d =48 1 k ( ) ∑ 54 48 x k = 48![ x ] ( e − 1) k 1 ≤ k ≤ 48 ( ) ∑ 54 48 x k = 48![ x ] ( e − 1) k 0 ≤ k ≤ 54 48 x 54 = 48 48 = 54 .