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 1 , a 2 , . . . , a 48 ) between 0 and 100 inclusive have the
property that for all 1 ≤ i < j ≤ 48, a i 6 ∈ { a j , a j + 1 } ?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
Answer: 5448
(With Ashwin Sah) The key idea is write the elements of the sequence in increasing order. These setsare 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
( )
2 ≤ I ≤ k , and a , a ≥ 0. Notice that there are solutions to the second equation and then 54
1 k +1
48!kthere are solutions for each { d } set. Then this gives that the answer isd ! ··· d !i
1 k
( )
∑ ∑
54 48!
∏
d !kkii =1
1 ≤ k ≤ 48 d + ... + d =48
1 k
( )
∑
48 x k 54 = 48![ x ] ( e − 1)
1 ≤ k ≤ 48 k
( )
∑
48 x k 54 = 48![ x ] ( e − 1)
0 ≤ k ≤ 54 k
48 x 54 = 48! x (e) = 54 .48