Maths Olympiad Prep

Library / /131 of 196

Combinatorics Difficulty 5.5 AIME, harder Prove it Soviet Union

Problem:

We place labeled points on a circle as follows. At step 1, take two points at opposite ends of a diameter and label them both 11. At step n>1n > 1, place a point at the midpoint of each arc created at step n1n - 1 and label it with the sum of the labels at the two adjacent points. What is the total sum of the labels after step nn?

For example, after step 4 we have: 11, 44, 33, 55, 22, 55, 33, 44, 11, 44, 33, 55, 22, 55, 44, 33, 44.

Solution

Solution:

Answer: 23n12 \cdot 3^{n - 1}.

True for n=1n = 1. The new points added at step n+1n + 1 have twice the sum of the points after step nn, because each old point contributes to two new points. Hence the total after step n+1n + 1 is three times the total after step nn.

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.