Library / /478 of 481

, 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 $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.

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.