IMC 2020, Day 1, Problem 1
Let be a positive integer. Compute the number of words (finite sequences of letters) that satisfy all the following three properties:
(1) consists of letters, all of them are from the alphabet ;
(2) contains an even number of letters ;
(3) contains an even number of letters .
(For example, for there are such words: , , , , and .)
Armend Sh. Shabani, University of Prishtina
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Armend Sh. Shabani, University of Prishtina
Solution 1. Let . Consider a word that satisfies the conditions and let be the sets of positions of letters , , and in , respectively. By the definition of the words we have . The sets and are constrained to have even sizes.
In order to construct all suitable words , choose the set first; by the conditions, must be even. It is well-known that an -element set (with ) has even subsets, so there are possibilities for .
If then we can choose arbitrarily, and then the set is determined uniquely. Since has subsets, we have options for set and therefore suitable words with .
Otherwise, if , we have to choose an arbitrary subset of and an even subset of ; then and are determined and will automatically be even. We have choices for and independent choices for ; so for each nonempty even we have suitable words.
The number of nonempty even sets is , so in total, the number of words satisfying the conditions is
Solution 2. Let denote the number of words of length over such that and appear even number of times. Further, we define the following sequences for the number of words of length , all over .
- - the number of words with an odd number of 's and even number of 's
- - the number of words with even number of 's and an odd number of 's
- - the number of words with an odd number of 's and an odd number of 's
We will call them A-words, B-words, C-words and D-words, respectively. It is clear that and that
First, we find a recurrence relation for . If an A-word of length begins with or , it can be followed by any A-word of length , contributing with . If an A-word of length begins with , it can be followed by any word of length that contains an odd number of 's and even number of 's, thus contributing with . If an A-word of length begins with , it can be followed by any word of length that contains even number of 's and an odd number of 's, thus contributing with . Therefore we have the following recurrence relation:
Now observe that for all , since simultaneously replacing 's to 's and vice versa we get a -word from a -word. Therefore (2) yields . Now (1) yields
Solving the last recurrence relation (for example, diving by we get satisfies , and it remains to sum up consecutive powers of 2) we get
Solution 3. Consider the sum
If a word contains letters ,, and respectively, we get with the coefficient
Hence, by substituting in we get the answer .
Transcribed from the official solutions, pages 1–3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.