HMMT 十一月 2023 · 冲刺赛 · 第 32 题

HMMT November 2023 — Guts Round — Problem 32

[17] Compute X a ! , b ! c !( a − b − c )! a + b + c =12 a ≥ 6 , b,c ≥ 0 where the sum runs over all triples of nonnegative integers ( a, b, c ) such that a + b + c = 12 and a ≥ 6.

解析

[17] Compute X a ! , b ! c !( a − b − c )! a + b + c =12 a ≥ 6 , b,c ≥ 0 where the sum runs over all triples of nonnegative integers ( a, b, c ) such that a + b + c = 12 and a ≥ 6. Proposed by: Rishabh Das Answer: 2731 Solution: We tile a 1 × 12 board with red 1 × 1 pieces, blue 1 × 2 pieces, and green 1 × 2 pieces. Suppose we use a total pieces, b blue pieces, and c green pieces. Then we must have a + b + c = 12, and the number of ways to order the pieces is a . b, c, a − b − c Thus, the desired sum is the number of ways to do this. Let a be the number of ways to do this on a 1 × n board. Then we have the recursion a = a +2 a n n n − 1 n − 2 by casework on the first piece: if it is 1 × 1 , we are left with a 1 × n − 1 board, and otherwise we are left with a 1 × n − 2 board. We also know a = 1 and a = 3 , so the characteristic polynomial for this 1 2 2 recursion is t − t − 2 = 0, which has roots 2 and − 1. Thus, n n a = A · ( − 1) + B · 2 . n 1 2 Then plugging in n = 1 and n = 2 gives A = − and B = , so 3 3 n +1 n 2 + ( − 1) a = . n 3 With n = 12, this evaluates to our answer of 2731.