Library / All-Soviet-Union Mathematical Olympiad /67 of 185

All-Soviet-Union Mathematical Olympiad

Combinatorics Difficulty 4.9 AIME Prove it Soviet Union

Problem:
How many (algebraically) different expressions can we obtain by placing parentheses in $a_1 / a_2 / \ldots / a_n$ ?

Solution

Solution:
Answer $2^{n - 2}$ . $a_1$ must be in the numerator, and $a_2$ must be in the denominator, but the other symbols can be in either. This is easily proved by induction.

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

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