tag:blogger.com,1999:blog-2400513859305780710.post6100014557619212814..comments2023-04-04T07:53:53.789-07:00Comments on Mathematical Food For Thought: Digit To The Unit. Topic: Algebra. Level: AIME.Jeffrey Wanghttp://www.blogger.com/profile/11114458640271201663noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-2400513859305780710.post-11236141999010380862006-12-06T13:52:55.000-08:002006-12-06T13:52:55.000-08:00Probably the best question on today's warmup, ...Probably the best question on today's warmup, too bad I didn't really cover anything like that XD<br><br>Anyway, I saw a solution by Lucas' Theorem but I'll go slightly more basic and use the lemma behind it instead:<br><br>Lemma: (a + b)^p = a^p + b^p mod p<br><br>Easy to prove. With this lemma, let n = 2^{e_1} + 2^{e_2}+ ... + 2^{e_d}(its binary expansion). Then<br><br>(x + 1)^n = (x^{2^{e_1}} + 1)(x^{2^{e_2}} + 1)...(x^{2^{e_d}} + 1) mod 2<br><br>If this form is expanded every coefficient will be 1 because of unique represention base 2 so there'll be 2^d odd coefficients, where d is the number of nonzero binary digits in n.t0rajir0unoreply@blogger.comtag:blogger.com,1999:blog-2400513859305780710.post-20045855690552758222006-12-06T13:54:54.000-08:002006-12-06T13:54:54.000-08:00BY THE WAY HARD QUESTION I COULDN'T DO:Instead...BY THE WAY HARD QUESTION I COULDN'T DO:<br><br>Instead of (x + 1)^n find the number of odd coefficients in (x^2 + x + 1)^n<br><br>=(t0rajir0unoreply@blogger.com