Library / /486 of 490

, 2021

Combinatorics Difficulty 4.8 AIME Find the answer Canada

In Figure 1, three unshaded dots are arranged to form an equilateral triangle, as shown.

Figure 1

Figure 2 is formed by arranging three copies of Figure 1 to form the outline of a larger equilateral triangle and then filling the resulting empty space with 1 shaded dot.

Figure 2
For each integer $\text{n gt;2}$ , Figure $n$ is formed by first arranging three copies of Figure $n-1$ to form the outline of a larger equilateral triangle and then filling the resulting empty space in the centre with an inverted triangle of shaded dots.

Figure 3

The smallest value of $n$ for which Figure $n$ includes at least 100 000 shaded dots is

$8$
$9$
$10$
$11$
$12$

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Since each Figure is formed by placing two copies of the previous Figure side-by-side along the base and then adding other pieces above, the number of dots in the base of each Figure is two times as many as in the previous Figure.

Since each Figure is an equilateral triangle, then the number of dots in the Figure equals the sum of the positive integers from 1 to the number of dots in the base, inclusive. In other words, if the base of a Figure consists of $b$ dots, then the Figure includes $1 + 2 + 3 + \cdots + (b-1) + b$ dots. This sum is equal to $\frac{1}{2}b(b+1)$ . (If this formula for the sum is unfamiliar, can you argue why it is true?)

Since each Figure is formed by using three copies of the previous Figure and any new dots added are shaded dots, the number of unshaded dots in each Figure is exactly three times the number of unshaded dots in the previous Figure.

Since each dot is either shaded or unshaded, the number of shaded dots equals the total number of dots minus the number of unshaded dots.

Using these statements, we construct a table:

Figure	Dots in base	Dots in Figure	Unshaded dots	Shaded dots
1	2	3	3	0
2	4	10	9	1
3	8	36	27	9
4	16	136	81	55
5	32	528	243	285
6	64	2080	729	1351
7	128	8256	2187	6069
8	256	32896	6561	26335
9	512	131328	19683	111645

Therefore, the smallest value of $n$ for which Figure $n$ includes at least 100 000 dots is $n=9$ .

We note that since the number of dots in the base of Figure 1 is 2 and the number of dots in the base of each subsequent Figure is double the number of dots in the previous Figure, then the number of dots in the base of Figure $n$ is equal to $2^n$ .

Since the number of unshaded dots in Figure 1 is 3 and the number of unshaded dots in each subsequent Figure is three times the number of unshaded dots in the previous Figure, then the number of unshaded dots in Figure $n$ is $3^n$ .

Therefore, a formula for the number of unshaded dots in Figure $n$ is $\frac{1}{2}2^n(2^n+1) - 3^n$ which can be re-written as $2^{2n-1} + 2^{n-1} - 3^n$ , which agrees with the numbers in the table above.

Figure for this problem

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: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.