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 "2008 iTest Problems/Problem 77"

(Created page with "== 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 six...")
 
m
 
Line 108: Line 108:
  
 
<math>=2^7O_{0}=128</math>.
 
<math>=2^7O_{0}=128</math>.
 +
 +
 +
==See Also==
 +
{{2008 iTest box|num-b=76|num-a=78}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 04:15, 28 January 2019

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 $4$ or $5$ students at a time to tutor geometry each week:

\begin{align*}\dbinom{16}4&=1820,\\\dbinom{16}5&=4368.\end{align*}

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

[asy] import graph; size(5cm,10cm); for (int i=0; i<16; ++i) { for (int j=0; j<=i; ++j) { int remainder = choose(i,j) %2 ; MP((string) remainder ,(-j+i/2,-i),S); } } draw((0,0)--(-4,-8.2)--(4,-8.2)--cycle,black); draw((4,-8.2)--(8,-16.2)--(0,-16.2)--cycle,black); draw((-4,-8.2)--(-8,-16.2)--(0,-16.2)--cycle,black); filldraw((4,-8.2)--(-4,-8.2)--(0,-16)--cycle,green,black); [/asy]

Every Pascal's triangle of size $2^n$ can be decomposed into $4$ triangles of size $2^{n-1}$ which include the all-zero "inner" triangle with vertices

$\Bigg\{\binom{2^{n-1}}{1},\binom{2^{n-1}}{2^{n-1}-1},\binom{2^n-2}{2^{n-1}-1}\Bigg\}$

and the three identical "outer" triangles with vertices

i) $\Bigg\{\binom{0}{0},\binom{2^{n-1}-1}{0} ,\binom{2^{n-1}-1}{2^{n-1}-1}\Bigg\}$

ii)$\Bigg\{\binom{2^{n-1}}{0},\binom{2^{n}-1}{0} ,\binom{2^{n}-1}{2^{n-1}-1}\Bigg\}$ and

iii)$\Bigg\{\binom{2^{n-1}}{2^{n-1}},\binom{2^{n}-1}{2^n-1} ,\binom{2^{n}-1}{2^{n-1}+1}\Bigg\}$

as shown in the previous diagram (starting at row 0):


Method 1 (direct)

Let $E_k$ be the number of EVEN numbers in the $k^{th}$ row of the Pascal triangle $\{\binom{k}{0},\binom{k}{1},\ldots,\binom{k}{k-1},\binom{k}{k}\}$ and let $2^{(n-1)}<=k<=2^n$. Then we have the following recursive relation $E_k=2*E_{k-2^{(n-1)}}+(2^{n}-1-k)$ reflecting the fact that the row associated with $E_k$ is just 2 copies of the row associated with $E_{k-2^{(n-1)}}$ along with $(2^{n}-1-k)$ zeros associated with the "inner" triangle.

$E_{2008}=2\cdot E_{2008-1024}+(2047-2008)$

$E_{984}=2\cdot E_{984-512}+(1023-984)$

$E_{472}=2\cdot E_{472-256}+(511-472)$

$E_{216}=2\cdot E_{216-128}+(255-216)$

$E_{88}=2\cdot E_{88-64}+(127-88)$

$E_{24}=2\cdot E_{24-16}+(31-24)$

$E_{8}=2\cdot E_{8-8}+(15-8)=7$

Substitution yeilds $E_{2008}=2(2(2(2(2(2(7)+7)+39)+39+39))+39)+39=1881$

The algebra behind the self-similarity of the parity Pascal triangle is due to the fact that if $2^k$ is the maximum power of 2 that divides a, then $2^k$ is also the maximum power of 2 that divides $(a-2^{k+1})$.


Method 2 (indirect)

The recursion relation can be simplified by focusing instead on the number of odd entries in the $k^{th}$ row of the Pascal triangle. Let $O_k$ be the number of ODD numbers in the $k^{th}$ row of the Pascal triangle $\{\binom{k}{0},\binom{k}{1},\ldots,\binom{k}{k-1},\binom{k}{k}\}$, and let $2^{(n-1)}<=k<=2^n$ then we have the following recursive relation $O_k=2*O_{k-2^{(n-1)}}$ reflecting the fact that the row associated with $O_k$ is just 2 copies of the row associated with $O_{k-2^{(n-1)}}$ along with an "inner" triangle of evens which does not contribute to the sum.

Then

$O_{2008}=2\cdot O_{2008-1024}$

$=2^2\cdot O_{2008-1024-512}$

$=2^3\cdot O_{2008-1024-512-256}$

$=2^4\cdot O_{2008-1024-512-256-128}$

$=2^5\cdot O_{2008-1024-512-256-128-64}$

$=2^6\cdot O_{2008-1024-512-256-128-64-16}$

$=2^7\cdot O_{2008-1024-512-256-128-64-16-8}$

$=2^7O_{0}=128$.


See Also

2008 iTest (Problems)
Preceded by:
Problem 76 		Followed by:
Problem 78
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • 61 • 62 • 63 • 64 • 65 • 66 • 67 • 68 • 69 • 70 • 71 • 72 • 73 • 74 • 75 • 76 • 77 • 78 • 79 • 80 • 81 • 82 • 83 • 84 • 85 • 86 • 87 • 88 • 89 • 90 • 91 • 92 • 93 • 94 • 95 • 96 • 97 • 98 • 99 • 100
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_77&oldid=101039"