Track / Stage 6 / 138 of 400 #1138 of 1964

Problem 1138

National olympiad, first round

Combinatorics Difficulty 6.2 Prove it

Consider $\Gamma$ . Petya calculated the number of all possible $m$ -letter words, in which only four letters T, O, W, and N can be used, and in each word, the letters T and O are equal in number. Vasya calculated the number of all possible $2m$ -letter words, in which only two letters T and O can be used, and in each word, these letters are equal in number. Who ended up with more words? (A word is any sequence of letters.)

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

Let's establish a one-to-one correspondence between Petya's and Vasya's words. We will divide Vasya's word, consisting of $2 m$ letters, into blocks of two letters. We will replace each TT block with the letter T, the OO block with the letter O, the TO block with the letter W, and the OT block with the letter N. This will result in a word of $m$ letters, in which the letters T and O are equal in number (initially, they were equal in number, and the replacement of TO and OT blocks removes an equal number of T and O letters, meaning there will be as many TT blocks as OO blocks). Thus, we have associated each of Vasya's words with a word of Petya's.

Conversely, from each $m$ -letter word of Petya's, it is easy to restore which word of Vasya's it came from: we need to replace the letters according to the rule

$\mathrm{T} \rightarrow \mathrm{TT}, \mathrm{O} \rightarrow \mathrm{OO}, \mathrm{W} \rightarrow \mathrm{TO}, \mathrm{N} \rightarrow \mathrm{OT}$ .

## Answer

The number of words turned out to be the same.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.