# 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$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.70048565,"math_prob":0.9962791,"size":1566,"snap":"2021-21-2021-25","text_gpt3_token_len":547,"char_repetition_ratio":0.087067865,"word_repetition_ratio":0.051948052,"special_character_ratio":0.47509578,"punctuation_ratio":0.052980132,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99984777,"pos_list":[0,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],"im_url_duplicate_count":[null,4,null,4,null,4,null,4,null,4,null,4,null,4,null,7,null,null,null,4,null,4,null,4,null,4,null,4,null,4,null,4,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-05-19T00:22:00Z\",\"WARC-Record-ID\":\"<urn:uuid:4a90d674-479e-4bac-9e3c-41c062497a7d>\",\"Content-Length\":\"48771\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f6778202-e9e2-4626-b4ea-9740fc388bea>\",\"WARC-Concurrent-To\":\"<urn:uuid:2a414bff-8c86-4535-a630-f7d1d33405b6>\",\"WARC-IP-Address\":\"172.67.69.208\",\"WARC-Target-URI\":\"https://artofproblemsolving.com/wiki/index.php/2008_iTest_Problems/Problem_78\",\"WARC-Payload-Digest\":\"sha1:CJRFZQIC3SNK74SLA2SXP2W5PZ56SDSM\",\"WARC-Block-Digest\":\"sha1:QXDB2XZS3KYTUE5NYVCLV734TUVLBGHF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-21/CC-MAIN-2021-21_segments_1620243989874.84_warc_CC-MAIN-20210518222121-20210519012121-00412.warc.gz\"}"}