Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 AIME II Problems/Problem 13"

(→‎Note)
(→‎Solution)
Line 12: Line 12:
  
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 
Label each of the bottom squares as <math>x_0, x_1 \ldots x_9, x_{10}</math>.  
 
Label each of the bottom squares as <math>x_0, x_1 \ldots x_9, x_{10}</math>.  
  
Line 19: Line 20:
  
 
The seven terms from <math>x_2 \ldots x_8</math> can assume either <math>0</math> or <math>1</math>, giving us <math>2^7</math> possibilities. The answer is therefore <math>5 \cdot 2^7 = \boxed{640}</math>.
 
The seven terms from <math>x_2 \ldots x_8</math> can assume either <math>0</math> or <math>1</math>, giving us <math>2^7</math> possibilities. The answer is therefore <math>5 \cdot 2^7 = \boxed{640}</math>.
 +
 +
=== Solution 2 ===
 +
 +
We know that the top square is the sum of the numbers in the <math>11</math>th row, and that each number in the <math>k</math>th row is the sum of the numbers in the <math>(k+1)</math>th row, for <math>1 \le k \le 9</math>.
 +
 +
Let <math>a_i</math> denote the number in the <math>i</math>th square of the <math>11</math>th row.
 +
 +
So the top square is <math>a_1 + a_2 + \cdots + a_{11}</math>.
 +
 +
Because of this we can say that if we have a multiple of 3 in the top square, the sum of the numbers in the <math>11</math>th row is also a multiple of 3.
 +
 +
Because the only numbers in the <math>11</math>th row are 0 and 1, the number of ways to have a multiple of 3 in the sum of the <math>11</math>th row is the number of ways to have a multiple of 3 in the sum of <math>0</math>s and <math>1</math>s.
 +
 +
The number of ways to have a multiple of 3 in the sum of <math>0</math>s and <math>1</math>s is the number of ways to have a multiple of 3 in the sum of <math>0</math>s plus the number of ways to have a multiple of 3 in the sum of <math>1</math>s.
 +
 +
The number of ways to have a multiple of 3 in the sum of <math>0</math>s is the number of ways to have a multiple of 3 in the sum of <math>0</math>s in the <math>11</math>th row, which is <math>\binom{11}{3}, \binom{11}{6}, \binom{11}{9}</math>.
 +
 +
The number of ways to have a multiple of 3 in the sum of <math>1</math>s is the number of ways to have a multiple of 3 in the sum of <math>1</math>s in the <math>11</math>th row, which is <math>\binom{11}{0}, \binom{11}{3}, \binom{11}{6}, \binom{11}{9}</math>
 +
 +
So in total, the number of initial distributions of <math>0</math>s and <math>1</math>s in the bottom row is the number of the top square a multiple of <math>3</math> is <math>\binom{11}{3} + \binom{11}{6} + \binom{11}{9} + \binom{11}{0} + \binom{11}{3} + \binom{11}{6} + \binom{11}{9}</math>.
 +
-KevinChen_Yay
  
 
== Note ==
 
== Note ==

Revision as of 10:06, 22 January 2023

Problem

A triangular array of squares has one square in the first row, two in the second, and in general, $k$ squares in the $k$th row for $1 \leq k \leq 11.$ With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in the given diagram). In each square of the eleventh row, a $0$ or a $1$ is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of $0$'s and $1$'s in the bottom row is the number in the top square a multiple of $3$?

[asy] for (int i=0; i<12; ++i){ for (int j=0; j<i; ++j){ //dot((-j+i/2,-i)); draw((-j+i/2,-i)--(-j+i/2+1,-i)--(-j+i/2+1,-i+1)--(-j+i/2,-i+1)--cycle); } } [/asy]

Solution

Solution 1

Label each of the bottom squares as $x_0, x_1 \ldots x_9, x_{10}$.

Through induction, we can find that the top square is equal to ${10\choose0}x_0 + {10\choose1}x_1 + {10\choose2}x_2 + \ldots {10\choose10}x_{10}$. (This also makes sense based on a combinatorial argument: the number of ways a number can "travel" to the top position going only up is equal to the number of times it will be counted in the final sum.)

Examine the equation $\mod 3$. All of the coefficients from $x_2 \ldots x_8$ will be multiples of $3$ (since the numerator will have a $9$). Thus, the expression boils down to $x_0 + 10x_1 + 10x_9 + x_{10} \equiv 0 \mod 3$. Reduce to find that $x_0 + x_1 + x_9 + x_{10} \equiv 0 \mod 3$. Out of $x_0,\ x_1,\ x_9,\ x_{10}$, either all are equal to $0$, or three of them are equal to $1$. This gives ${4\choose0} + {4\choose3} = 1 + 4 = 5$ possible combinations of numbers that work.

The seven terms from $x_2 \ldots x_8$ can assume either $0$ or $1$, giving us $2^7$ possibilities. The answer is therefore $5 \cdot 2^7 = \boxed{640}$.

Solution 2

We know that the top square is the sum of the numbers in the $11$th row, and that each number in the $k$th row is the sum of the numbers in the $(k+1)$th row, for $1 \le k \le 9$.

Let $a_i$ denote the number in the $i$th square of the $11$th row.

So the top square is $a_1 + a_2 + \cdots + a_{11}$.

Because of this we can say that if we have a multiple of 3 in the top square, the sum of the numbers in the $11$th row is also a multiple of 3.

Because the only numbers in the $11$th row are 0 and 1, the number of ways to have a multiple of 3 in the sum of the $11$th row is the number of ways to have a multiple of 3 in the sum of $0$s and $1$s.

The number of ways to have a multiple of 3 in the sum of $0$s and $1$s is the number of ways to have a multiple of 3 in the sum of $0$s plus the number of ways to have a multiple of 3 in the sum of $1$s.

The number of ways to have a multiple of 3 in the sum of $0$s is the number of ways to have a multiple of 3 in the sum of $0$s in the $11$th row, which is $\binom{11}{3}, \binom{11}{6}, \binom{11}{9}$.

The number of ways to have a multiple of 3 in the sum of $1$s is the number of ways to have a multiple of 3 in the sum of $1$s in the $11$th row, which is $\binom{11}{0}, \binom{11}{3}, \binom{11}{6}, \binom{11}{9}$

So in total, the number of initial distributions of $0$s and $1$s in the bottom row is the number of the top square a multiple of $3$ is $\binom{11}{3} + \binom{11}{6} + \binom{11}{9} + \binom{11}{0} + \binom{11}{3} + \binom{11}{6} + \binom{11}{9}$. -KevinChen_Yay

Note

The specific induction process: we want to prove that if the bottom row is $x_0, x_1 \cdots x_{n}$, the top square is ${n\choose0}x_0 + {n\choose1}x_1 + {n\choose2}x_2 + \ldots {n\choose{n}}x_{n}$.

Base Case: when n = 1, this is obviously true.

Induction Step: Assume that the statement is true for n, and we wish to prove it for $n + 1$. Therefore, we add another row below the $n + 1$ row, and name the squares as $a_0, a_1, \cdots a_{n+1}$. We obtain that $x_0 = a_0 + a_1, x_1 = a_1 + a_2, \cdots x_{n} = a_{n} + a_{n+1}$, and using the assumption, yield the top square equals ${n\choose0}(a_0 + a_1) + {n\choose1}(a_1 + a_2) + \ldots {n\choose{n}}(a_{n} + a_{n+1})$. While it's easy to prove that ${n\choose{k}} + {n\choose{k+1}} = {n+1\choose{k+1}}$ (just expand it), we find that the two equations are identical.

Note contributed by MVP_Harry, friend me if you want ~

Assume that the numbers filled in the 11th row is a b c d e f g h i j. Writing the number in each box, you will find that the coefficient of each letter turns out to be a pascal triangle.

See also

2007 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_13&oldid=187260"