2008 iTest Problems/Problem 78

Problem

Feeling excited over her successful explorations into Pascal's Triangle, Wendy formulates a second problem to use during a future Jupiter Falls High School Math Meet:

How many of the first 2010 rows of Pascal's Triangle (Rows 0 through 2009) have exactly 256 odd entries?

What is the solution to Wendy's second problem?

Solution

Building off of Method 2 in problem 77, we see that each that the base 2 representation of the number reveals to us how many times we end up applying the recursion relation $O_k=2*O_{k-2^{n-1}}$.

For example, $2008=1024+512+256+128+64+16+8=(11111011000)_2$ has seven nonzero terms in its base 2 expansion so that we end up applying the recursion relation seven times giving a final term of $O_{2008}=2^7\cdot O_{0}=2^7=128$. So we need to count the number of integers between $\{0,2009\}$ which have exactly 8 nonzero terms in their base 2 expansion.

$2009=(11111011001)_2$.

$\binom{11}{8}$ counts the numbers up to $2047=2^{11}-1$ which have exactly 8 nonzero terms in their base 2 expansion. Of these $\binom{11}{8}=165$ candidates, the following 12 must be excluded since they exceed $2009$:

$2040=(11111111000)_2,2036(11111110100)_2,$

$2034=(11111110010)_2,2033=(11111110001)_2,$

$2028=(11111101100)_2,2026=(11111101010)_2,$

$2025=(11111101001)_2,2022=(11111100110)_2,$

$2021=(11111100101)_2,2019=(11111100011)_2,$

$2012=(11111011100)_2,2010=(1111011010)_2$

This gives an answer of $165-12=153$.

Solution 2

By Lucas' Theorem, we require there to be $8$ ones in the binary representation of the row number. Continue as in solution 1.

See Also

2008 iTest (Problems)
Preceded by:
Problem 77
Followed by:
Problem 79
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