Track / Stage 4 / 196 of 340 #936 of 2444

Problem 936

AMC 12 late, AIME early

Combinatorics Difficulty 4.8 Find the answer CEMC Fermat · Canada · 2021

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 $n >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
Hide/Reveal Alternative Format for Figure 3

An equilateral triangle with a base of eight unshaded dots. The second row is seven dots: unshaded, shaded, unshaded, shaded, unshaded, shaded, unshaded. The third row is six dots: unshaded, unshaded, shaded, shaded, unshaded, unshaded. The fourth row is five dots: unshaded, shaded, shaded, shaded, and unshaded. The fifth row is four unshaded dots.
The sixth row is three dots: unshaded, shaded, unshaded. The seventh row is two unshaded dots. The top row is one unshaded dot.

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.

Official 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.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.