HMMT 二月 2002 · 冲刺赛 · 第 20 题

HMMT February 2002 — Guts Round — Problem 20

[7] The Antarctican language has an alphabet of just 16 letters. Interestingly, every word in the language has exactly 3 letters, and it is known that no word’s first letter equals any word’s last letter (for instance, if the alphabet were { a, b } then aab and aaa could not both be words in the language because a is the first letter of a word and the last letter of a word; in fact, just aaa alone couldn’t be in the language). Given this, determine the maximum possible number of words in the language.

解析

The Antarctican language has an alphabet of just 16 letters. Interestingly, every word in the language has exactly 3 letters, and it is known that no word’s first letter equals any word’s last letter (for instance, if the alphabet were { a, b } then aab and aaa could not both be words in the language because a is the first letter of a word and the last letter of a word; in fact, just aaa alone couldn’t be in the language). Given this, determine the maximum possible number of words in the language. Solution: 1024 Every letter can be the first letter of a word, or the last letter of a word, or possibly neither, but not both. If there are a different first letters and b different last letters, then we can form a · 16 · b different words (and the desired conditions will be met). Given the constraints 0 ≤ a, b ; a + b ≤ 16, this product is maximized when a = b = 8, giving the answer.