Competition problem — Combinatorics

Library / /78 of 94

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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