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

HMMT February 2023 — Guts Round — Problem 11

[13] The Fibonacci numbers are defined recursively by F = 0, F = 1, and F = F + F for i ≥ 2. 0 1 i i − 1 i − 2 Given 15 wooden blocks of weights F , F , . . . , F , compute the number of ways to paint each block 2 3 16 either red or blue such that the total weight of the red blocks equals the total weight of the blue blocks.

解析

[13] The Fibonacci numbers are defined recursively by F = 0, F = 1, and F = F + F for i ≥ 2. 0 1 i i − 1 i − 2 Given 15 wooden blocks of weights F , F , . . . , F , compute the number of ways to paint each block 2 3 16 either red or blue such that the total weight of the red blocks equals the total weight of the blue blocks. Proposed by: Albert Wang Answer: 32 Solution: Partition the blocks into sets { F , F , F } , { F , F , F } , . . . , { F , F , F } . 2 3 4 5 6 7 14 15 16 We can show by bounding that F belongs on the opposite side as F and F , and, in general, 16 15 14 that F is on the opposite side as F and F . Hence, it suffices to choose which side each of 3 k +1 3 k 3 k − 1 5 F , F , . . . , F go. This gives 2 = 32 ways. 4 7 16