Competition problem — Combinatorics

Library / /15 of 15

Combinatorics Difficulty 7.0 National Olympiad Prove it Philippines

Problem:

Gari took a 6-item multiple choice test with 3 choices per item, labelled $A$ , $B$ , and $C$ . After the test, he tried to recall his answers to the items. He only remembered that he never answered three consecutive $A$ 's, he never answered three consecutive $B$ 's, and he did not leave any item blank. How many possible sets of answers could Gari have had?

Solution

Solution:

The problem is equivalent to that of finding the number of ternary strings of length $6$ that do not contain any $3$ consecutive $0$ 's or $3$ consecutive $1$ 's. Using the principle of inclusion and exclusion, it suffices to count the number of ternary strings of length $6$ that contain at least $3$ consecutive $0$ 's, multiply the number by $2$ (by symmetry), and then subtract the number of ternary strings of length $6$ that contain at least $3$ consecutive $0$ 's and $3$ consecutive $1$ 's.

Note that there are $60$ such strings with exactly $3$ consecutive $0$ 's, $16$ with exactly $4$ consecutive $0$ 's, $4$ with exactly $5$ consecutive $0$ 's, and $1$ with exactly $6$ $0$ 's. This gives a total of $60+16+4+1=81$ strings of length $6$ that contain at least $3$ consecutive $0$ 's.

The total number of ternary strings of length $6$ is $3^{6}$ while the number of ternary strings of length $6$ that contain both $3$ consecutive $0$ 's and $3$ consecutive $1$ 's is $2$ . Thus, the number of strings that satisfy the problem are $3^{6}-(2)(81)+2=569$ .

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.