2008 iTest Problems/Problem 77
Problem
With about six hours left on the van ride home from vacation, Wendy looks for something to do. She starts working on a project for the math team.
There are sixteen students, including Wendy, who are about to be sophomores on the math team. Elected as a math team officer, one of Wendy's jobs is to schedule groups of the sophomores to tutor geometry students after school on Tuesdays. The way things have been done in the past, the same number of sophomores tutor every week, but the same group of students never works together. Wendy notices that there are even numbers of groups she could select whether she chooses or students at a time to tutor geometry each week:
Playing around a bit more, Wendy realizes that unless she chooses all or none of the students on the math team to tutor each week that the number of possible combinations of the sophomore math teamers is always even. This gives \her an idea for a problem for the Jupiter Falls High School Math Meet team test:
How many of the 2009 numbers on Row 2008 of Pascal's Triangle are even?
Wendy works the solution out correctly. What is her answer?
Solution
Drawing Pascal's triangle Mod 2 reveals a repeating even/odd structure.
Every Pascal's triangle of size can be decomposed into triangles of size which include the all-zero "inner" triangle with vertices
and the three identical "outer" triangles with vertices
i)
ii) and
iii)
as shown in the previous diagram (starting at row 0):
Method 1 (direct)
Let be the number of EVEN numbers in the row of the Pascal triangle and let . Then we have the following recursive relation reflecting the fact that the row associated with is just 2 copies of the row associated with along with zeros associated with the "inner" triangle.
Substitution yeilds
The algebra behind the self-similarity of the parity Pascal triangle is due to the fact that if is the maximum power of 2 that divides a, then is also the maximum power of 2 that divides .
Method 2 (indirect)
The recursion relation can be simplified by focusing instead on the number of odd entries in the row of the Pascal triangle. Let be the number of ODD numbers in the row of the Pascal triangle , and let then we have the following recursive relation reflecting the fact that the row associated with is just 2 copies of the row associated with along with an "inner" triangle of evens which does not contribute to the sum.
Then
.