Track / Stage 5 / 156 of 400 #1236 of 2444

Problem 1236

AIME late

Combinatorics Difficulty 5.3 Prove it Harvard-MIT Math Tournament · United States

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 $a a b$ and $a a a$ 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 $a a a$ alone couldn't be in the language). Given this, determine the maximum possible number of words in the language.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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 \cdot 16 \cdot b$ different words (and the desired conditions will be met). Given the constraints $0 \leq a, b ; a+b \leq 16$ , this product is maximized when $a=b=8$ , giving the answer.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.