AIME 2008 I · 第 6 题

Solution 1

Let the $k$th number in the $n$th row be $a(n,k)$. Writing out some numbers, we find that $a(n,k) = 2^{n-1}(n+2k-2)$.[1]

We wish to find all $(n,k)$ such that $67| a(n,k) = 2^{n-1} (n+2k-2)$. Since $2^{n-1}$ and $67$ are relatively prime, it follows that $67|n+2k-2$. Since every row has one less element than the previous row, $1 \le k \le 51-n$ (the first row has $50$ elements, the second $49$, and so forth; so $k$ can range from $1$ to $50$ in the first row, and so forth). Hence

$n+2k-2 \le n + 2(51-n) - 2 = 100 - n \le 100,$

it follows that $67| n - 2k + 2$ implies that $n-2k+2 = 67$ itself.

Now, note that we need $n$ to be odd, and also that $n+2k-2 = 67 \le 100-n \Longrightarrow n \le 33$.

We can check that all rows with odd $n$ satisfying $1 \le n \le 33$ indeed contains one entry that is a multiple of $67$, and so the answer is $\frac{33+1}{2} = \boxed{017}$.

^ Proof: Indeed, note that $a(1,k) = 2^{1-1}(1+2k-2)=2k-1$, which is the correct formula for the first row. We claim the result by induction on $n$. By definition of the array, $a(n,k) = a(n-1,k)+a(n-1,k+1)$, and by our inductive hypothesis,

$$\begin{aligned}a(n,k) &= a(n-1,k)+a(n-1,k+1)\\ &= 2^{n-2}(n-1+2k-2)+2^{n-2}(n-1+2(k+1)-2)\\&=2^{n-2}(2n+4k-4)\\&=2^{n-1}(n+2k-2)\end{aligned}$$ thereby completing our induction.

Solution 2

The result above is fairly intuitive if we write out several rows and then divide all numbers in row $r$ by $2^{r-1}$ (we can do this because dividing by a power of 2 doesn't affect divisibility by $67$). The second row will be $2, 4, 6, \cdots , 98$, the third row will be $3, 5, \cdots, 97$, and so forth. Clearly, only the odd-numbered rows can have a term divisible by $67$. However, with each row the row will have one less element, and the $99-67+1 = 33$rd row is the last time $67$ will appear. Therefore the number of multiples of 67 in the entire array is $\frac{33+1}{2} = \boxed{017}$.

Solution 3

$$\begin{array}{ccccccccccccccc} \color{blue}1 & & \color{blue}3 & & \color{blue}5 & & \color{blue}7 & & \color{blue}9 & & \color{blue}11 & & \color{blue}13 & & \color{blue}\dots \\ & \color{red}4 & & \color{red}8 & & \color{red}12 & & \color{red}16 & & \color{red}20 & & \color{red}24 & & \color{red}\dots & \\ & & \color{blue}12 & & \color{blue}20 & & \color{blue}28 & & \color{blue}36 & & \color{blue}44 & & \color{blue}\dots & & \\ & & & \color{red}32 & & \color{red}48 & & \color{red}64 & & \color{red}80 & & \color{red}\dots & & & \\ & & & & \color{blue}80 & & \color{blue}112 & & \color{blue}144 & & \color{blue}\dots & & & & \\ & & & & & \color{red}192 & & \color{red}256 & & \color{red}\dots & & & & & \end{array}$$ We begin by listing a smaller portion of the given triangular array, as shown in the diagram. Observe that for any term $k$ in the $n$th row, the corresponding term in the $(n+2)$th row is $4k$, and that term is also one position closer to the edge of the triangle. Since $67$ is prime, the only way a term in the array can be a multiple of $67$ is if it originates from the $67$ in the first row. Next, note that there cannot be any multiples of $67$ in the even-numbered rows (rows $2,4,6,\dots,50$). In particular, the second row consists entirely of multiples of $4$ up to $196$, none of which contain a factor of $67$. Since each even row is obtained by repeatedly multiplying by $4$, no even row can contain a multiple of $67$. Now observe that $67$ is the $17$th term from the right edge of the triangle. Each time a term moves two rows down, it shifts one position closer to the edge. Once a term reaches the edge, it is no longer multiplied by $4$, so it cannot produce any new multiples of $67$. Therefore, there are exactly $\boxed{017}$ multiples of $67$ in the array.

~Voidling

Video Solution

2008 AIME I #6

MathProblemSolvingSkills.com