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

HMMT February 2010 — Guts Round — Problem 12

[ 7 ] How many different collections of 9 letters are there? A letter can appear multiple times in a collection. Two collections are equal if each letter appears the same number of times in both collections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND

解析

[ 7 ] How many different collections of 9 letters are there? A letter can appear multiple times in a collection. Two collections are equal if each letter appears the same number of times in both collections. ( ) 34 Answer: We put these collections in bijections with binary strings of length 34 containing 9 9 zeroes and 25 ones. Take any such string - the 9 zeroes will correspond to the 9 letters in the collection. If there are n ones before a zero, then that zero corresponds to the ( n + 1)st letter of the alphabet. This scheme is an injective map from the binary strings to the collections, and it has an inverse, so the ( ) 34 number of collections is . 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND