uniolympiads Ελληνικά

IMC 2020, Day 1, Problem 1

Let nn be a positive integer. Compute the number of words ww (finite sequences of letters) that satisfy all the following three properties:

(1) ww consists of nn letters, all of them are from the alphabet {a,b,c,d}\{\mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}\};

(2) ww contains an even number of letters a\mathtt{a};

(3) ww contains an even number of letters b\mathtt{b}.

(For example, for n=2n = 2 there are 66 such words: aa\mathtt{aa}, bb\mathtt{bb}, cc\mathtt{cc}, dd\mathtt{dd}, cd\mathtt{cd} and dc\mathtt{dc}.)

Armend Sh. Shabani, University of Prishtina

Original from the official PDFLet n be a positive integer. Compute the number of words w (nite sequences of letters) that satisfy all the following three properties: Problem 1. (1) w consists of n letters, all of them are from the alphabet { a , b , c , d } ; (2) w contains an even number of letters a ; (3) w contains an even number of letters b . (For example, for n = 2 there are 6 such words: aa , bb , cc , dd , cd and dc .) Armend Sh. Shabani, University of Prishtina

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Armend Sh. Shabani, University of Prishtina

Solution 1. Let N={1,2,…,n}N = \{1, 2, \ldots, n\}. Consider a word ww that satisfies the conditions and let A,B,C,D⊂NA, B, C, D \subset N be the sets of positions of letters a\mathtt{a}, b\mathtt{b}, c\mathtt{c} and d\mathtt{d} in ww, respectively. By the definition of the words we have A⊔B⊔C⊔D=NA \sqcup B \sqcup C \sqcup D = N. The sets AA and BB are constrained to have even sizes.

In order to construct all suitable words ww, choose the set S=A∪BS = A \cup B first; by the conditions, ∣S∣=∣A∣+∣B∣|S| = |A| + |B| must be even. It is well-known that an nn-element set (with n≥1n \ge 1) has 2n−12^{n-1} even subsets, so there are 2n−12^{n-1} possibilities for SS.

If S=∅S = \emptyset then we can choose C⊂NC \subset N arbitrarily, and then the set D=S∖CD = S \setminus C is determined DD uniquely. Since NN has 2n2^n subsets, we have 2n2^n options for set CC and therefore 2n2^n suitable words ww with S=∅S = \emptyset.

Otherwise, if k=∣S∣>0k = |S| > 0, we have to choose an arbitrary subset CC of N∖SN \setminus S and an even subset AA of SS; then D=(N∖S)∖CD = (N \setminus S) \setminus C and B=S∖AB = S \setminus A are determined and ∣B∣=∣S∣−∣A∣|B| = |S| - |A| will automatically be even. We have 2n−k2^{n-k} choices for CC and 2k−12^{k-1} independent choices for AA; so for each nonempty even SS we have 2n−k⋅2k−1=2n−12^{n-k} \cdot 2^{k-1} = 2^{n-1} suitable words.

The number of nonempty even sets SS is 2n−1−12^{n-1} - 1, so in total, the number of words satisfying the conditions is

1⋅2n+(2n−1−1)⋅2n−1=4n−1+2n−1.1 \cdot 2^n + (2^{n-1} - 1) \cdot 2^{n-1} = 4^{n-1} + 2^{n-1}.

Solution 2. Let ana_n denote the number of words of length nn over A={a,b,c,d}\mathcal{A} = \{\mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}\} such that a\mathtt{a} and b\mathtt{b} appear even number of times. Further, we define the following sequences for the number of words of length nn, all over A\mathcal{A}.

  • bnb_n - the number of words with an odd number of a\mathtt{a}'s and even number of b\mathtt{b}'s
  • cnc_n - the number of words with even number of a\mathtt{a}'s and an odd number of b\mathtt{b}'s
  • dnd_n - the number of words with an odd number of a\mathtt{a}'s and an odd number of b\mathtt{b}'s

We will call them A-words, B-words, C-words and D-words, respectively. It is clear that a1=2a_1 = 2 and that

an+bn+cn+dn=4n.a_n + b_n + c_n + d_n = 4^n.

First, we find a recurrence relation for ana_n. If an A-word of length nn begins with c\mathtt{c} or d\mathtt{d}, it can be followed by any A-word of length n−1n - 1, contributing with 2an−12a_{n-1}. If an A-word of length nn begins with a\mathtt{a}, it can be followed by any word of length n−1n - 1 that contains an odd number of a\mathtt{a}'s and even number of b\mathtt{b}'s, thus contributing with bn−1b_{n-1}. If an A-word of length nn begins with b\mathtt{b}, it can be followed by any word of length n−1n - 1 that contains even number of a\mathtt{a}'s and an odd number of b\mathtt{b}'s, thus contributing with cn−1c_{n-1}. Therefore we have the following recurrence relation:

an=2an−1+bn−1+cn−1.(1)a_n = 2a_{n-1} + b_{n-1} + c_{n-1}. \tag{1}
Next, we find a recurrence relation for bnb_n. If a B-word of length nn begins with c\mathtt{c} or d\mathtt{d}, it can be followed by any B-word of length n−1n - 1, contributing with 2bn−12b_{n-1}. If a B-word of length nn begins with a\mathtt{a}, it can be followed by any word of length n−1n-1 that contains even number of a\mathtt{a}'s and even number of b\mathtt{b}'s, contributing with an−1a_{n-1}. If a B-word of length nn begins with b\mathtt{b}, it can be followed by any word of length n−1n-1 that contains an odd number of a\mathtt{a}'s and an odd number of b\mathtt{b}'s, contributing with dn−1=4n−1−an−1−bn−1−cn−1d_{n-1} = 4^{n-1} - a_{n-1} - b_{n-1} - c_{n-1}. Therefore we have the following recurrence relation:
bn=bn−1+4n−1−cn−1.(2)b_n = b_{n-1} + 4^{n-1} - c_{n-1}. \tag{2}

Now observe that bk=ckb_k = c_k for all kk, since simultaneously replacing a\mathtt{a}'s to b\mathtt{b}'s and vice versa we get a CC-word from a BB-word. Therefore (2) yields bn=4n−1b_n = 4^{n-1}. Now (1) yields

an=2⋅an−1+2⋅4n−2.a_n = 2 \cdot a_{n-1} + 2 \cdot 4^{n-2}.

Solving the last recurrence relation (for example, diving by 2n2^n we get xn:=an2−nx_n := a_n 2^{-n} satisfies xn−xn−1=2n−3x_n - x_{n-1} = 2^{n-3}, and it remains to sum up consecutive powers of 2) we get

an=2n−1+4n−1.a_n = 2^{n-1} + 4^{n-1}.

Solution 3. Consider the sum

(a+b+c+d)n+(−a−b+c+d)n+(−a+b+c+d)n+(a−b+c+d)n4.(∗)\frac{(a+b+c+d)^n + (-a-b+c+d)^n + (-a+b+c+d)^n + (a-b+c+d)^n}{4}. \tag{$*$}
Expanding the parentheses as
(a+b+c+d)n=(a+b+c+d)(a+b+c+d)…(a+b+c+d),(a+b+c+d)^n = (a+b+c+d)(a+b+c+d)\ldots(a+b+c+d),
we get a sum of products x1…xnx_1 \ldots x_n, xi∈{a,b,c,d}x_i \in \{a, b, c, d\}, naturally corresponding to the words of length nn over the alphabet {a,b,c,d}\{\mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}\}. Consider the other terms in the numerator similarly.

If a word x1…xnx_1 \ldots x_n contains A,B,C,DA, B, C, D letters a\mathtt{a},b\mathtt{b},c\mathtt{c} and d\mathtt{d} respectively, we get aAbBcCdDa^A b^B c^C d^D with the coefficient

1+(−1)A+B+(−1)A+(−1)B4=(1+(−1)A)(1+(−1)B)4={1,if A and B are even0,otherwise.\frac{1 + (-1)^{A+B} + (-1)^A + (-1)^B}{4} = \frac{(1 + (-1)^A)(1 + (-1)^B)}{4} = \begin{cases} 1, & \text{if } A \,\text{and}\, B \text{ are even} \\ 0, & \text{otherwise.} \end{cases}

Hence, by substituting a=b=c=d=1a = b = c = d = 1 in (∗)(*) we get the answer (4n+2n+1)/4=4n−1+2n−1(4^n + 2^{n+1})/4 = 4^{n-1} + 2^{n-1}.

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?