1

A triangular array of numbers has a first row consisting of the odd integers $1,3,5,\ldots,99$ in increasing order. Each row below the first has one fewer entry than the row above it, and the bottom row has a single entry. Each entry in any row after the top row equals the sum of the two entries diagonally above it in the row immediately above it. How many entries in the array are multiples of $67$?

Except for writing down some numbers, I wasn't sure how to proceed on this question. Does anyone have any ideas?

Dude156
  • 1,316
  • 3
    don't they usually have solutions on their website? – Christopher Marley Jun 06 '18 at 03:34
  • Yes, but the solution didn't make too much sense to me, so I figured I'd post it here – Dude156 Jun 06 '18 at 03:38
  • This is what I usually do (whenever the solution doesn't make sense) and its helped me understand these AIME questions really well – Dude156 Jun 06 '18 at 03:39
  • 2
    In this case, you may want to post a link to the solution, and highlight which parts you are unable to understand. Of course, if the entire approach, while being correct, seems to come out of the blue, you may request a more intuitive understanding of the answer. – Sarvesh Ravichandran Iyer Jun 06 '18 at 03:40
  • 2
    no, why does he have to post other solutions? just because other solutions exists doesnt meen he has to add one – Asinomás Jun 06 '18 at 03:41
  • how would you determine if a specific entry is a multiple of 67? – Asinomás Jun 06 '18 at 03:46
  • By dividing it by 67? – Dude156 Jun 06 '18 at 03:50
  • Every term is a lineal combination of terms in the top row, can you find the coefficients? They are binomial coefficients – Asinomás Jun 06 '18 at 03:57
  • 1
    https://artofproblemsolving.com/wiki/index.php?title=2008_AIME_I_Problems/Problem_6 I can't make heads or tails of it either. The second solution looks neater though. – Christopher Marley Jun 06 '18 at 04:01
  • @JorgeFernández While it looks like either way the situation has been settled to everyone's satisfaction, a good reason to post a link to the solution and say what you don't understand is to make sure that the answers here don't just cause the same confusion. I wouldn't say it's mandatory, but it's often helpful. – Misha Lavrov Jun 09 '18 at 16:01

2 Answers2

1

Claim : every row of the triangular array that you have, is an arithmetic progression. More precisely, the common difference in the $n$th row (difference between consecutive elements of the row) is $2^{n}$.

Proof : Clearly, the first row is an arithmetic progression of common difference two.

Call the elements of the triangular array $a_{n,i}$ where $n$ is the row (from top : the topmost row is $1$, second top most is $2$ etc.) and $i$ is the index within the row (for example, $a_{1,2} = 3$).

Then, $a_{(n+1),i} = a_{n,i+1} + a_{n,i}$ (similar to, but not quite the combinatorial relation), so $a_{(n+1),i+1} - a_{(n+1),i} = (a_{n,i+1} - a_{n,i-1}) = 2 \times 2^{n} = 2^{n+1}$. So our fact follows by induction.

Now, is there a nice formula for the first element of every row? Indeed, $a_{(n+1),1} = a_{n,1} + a_{n,2} = 2a_{n,1} + 2^n$ is a recurrence relation.

Now, we actually have a formula for each element : $a_{n,i} = a_{n,1} + (i-1)2^n$, and the above formula are the key points.

We have yet another claim, however.

Claim : $a_{n,1} = n2^{n-1}$!

Proof : Indeed, it is true for $n = 1$ and $a_{(n+1),1} = (n+1)2^n$ is easy to see, completing the inductive hypothesis.

Finally, we are in a very nice position : $a_{n,i} = a_{n,1} + (i-1)2^n = (n+2i-2)2^{n-1}$.

You can see this : for example, $a_{2,2} = 8 = (2 + (2 \times 2) - 2)2^{2-1}$

Finally, when is $a_{n,i}$ a multiple of $67$? Note that $2^n$ is coprime to $67$.

Therefore, $a_{n,i}$ is a multiple of $67$ precisely when $(n+2i-2)$ is a multiple of $67$.

Knowing that $1 \leq n \leq 99$ and $i \leq 100-n$, can you now do the problem?

EDIT : You should get $17$ multiples.

Sarvesh Ravichandran Iyer
  • 76,105
1

Instead of generating each row by taking sums of consecutive elements, take averages. This will divide every element in the whole triangle by some power of $2$, and therefore will not affect which ones are divisible by $67$. Doing it this way the table becomes $$\matrix{ 1&&3&&5&&\cdots&&95&&97&&99\cr &2&&4&&6&&\cdots&&96&&98\cr &&3&&5&&7&&\cdots&&97\cr}$$ with an obvious pattern. At this stage there is one multiple of $67$ in every row that starts with an odd number. This continues until the $33$rd row, which is $$\matrix{33&&35&&37&&\cdots&&65&&67\cr}\ ;$$ after this we have $$\matrix{34&&36&&38&&\cdots&&66\cr&35&&37&&\cdots&&65\cr}$$ and it is clear that there will be no more multiples of $67$. So there is one multiple of $67$ in rows $1,3,5,\ldots,33$, and no more.

Answer. The triangle contains $17$ multiples of $67$.

David
  • 82,662