Competition problem — Combinatorics

Library / /727 of 740

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Tim the Beaver can make three different types of geometrical figures: squares, regular hexagons, and regular octagons. Tim makes a random sequence $F_{0}, F_{1}, F_{2}, F_{3}, \ldots$ of figures as follows:
- $F_{0}$ is a square.
- For every positive integer $i$ , $F_{i}$ is randomly chosen to be one of the 2 figures distinct from $F_{i-1}$ (each chosen with equal probability $\frac{1}{2}$ ).
- Tim takes 4 seconds to make squares, 6 to make hexagons, and 8 to make octagons. He makes one figure after another, with no breaks in between.

Suppose that exactly 17 seconds after he starts making $F_{0}$ , Tim is making a figure with $n$ sides. What is the expected value of $n$ ?

Solution

Solution:

Answer: 7

We write $F_{i}=n$ as shorthand for "the $i$ th figure is an $n$ -sided polygon."

If $F_{1}=8$ , then $F_{2}=6$ or $F_{2}=4$ . If $F_{2}=6$ , Tim is making a 6-gon at time 13 (probability contribution $1/4$ ). If $F_{2}=4$ , $F_{3}=6$ or $F_{3}=8$ will take the time 13 mark ( $1/8$ contribution each).

If $F_{1}=6$ , $F_{2}=8$ or $F_{2}=4$ . If $F_{2}=8$ , it takes the 13 mark ( $1/4$ contribution). If $F_{2}=4$ , $F_{3}=6$ or $F_{3}=8$ will take the 13 mark ( $1/8$ contribution each).

Thus, the expected value of the number of sides at time 13 is $0(4)+\left(\frac{1}{4}+\frac{1}{8}+\frac{1}{8}\right)(6)+\left(\frac{1}{8}+\frac{1}{4}+\frac{1}{8}\right)(8)=7$ .

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.