HMMT 二月 2023 · 冲刺赛 · 第 12 题

HMMT February 2023 — Guts Round — Problem 12

[13] The number 770 is written on a blackboard. Melody repeatedly performs moves , where a move consists of subtracting either 40 or 41 from the number on the board. She performs moves until the number is not positive, and then she stops. Let N be the number of sequences of moves that Melody b could perform. Suppose N = a · 2 where a is an odd positive integer and b is a nonnegative integer. Compute 100 a + b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2023, February 18, 2023 — GUTS ROUND Organization Team Team ID# b d

解析

[13] The number 770 is written on a blackboard. Melody repeatedly performs moves , where a move consists of subtracting either 40 or 41 from the number on the board. She performs moves until the number is not positive, and then she stops. Let N be the number of sequences of moves that Melody b could perform. Suppose N = a · 2 where a is an odd positive integer and b is a nonnegative integer. Compute 100 a + b . Proposed by: Albert Wang Answer: 318 Solution: Notice that if we use the 41 move nine times or less, we will have to make a total of ⌈ ⌉ ⌊ ⌋ 770 770 = 20 moves, and if we use it ten times or more, we will have to make a total of = 19 40 40 moves. So, doing casework on the number of 40s we use gives ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 20 19 19 19 19 20 20 20 10

- - · · · + + + + + · · · + . 0 1 2 9 2 11 11 20 ︸︷︷︸︸︷︷︸ 19 moves 20 moves 19 20 2 2 18 Using the row sums of Pascal’s triangle we have this sum equal to + = 3 · 2 . The answer is 318. 2 2 b d