Competition problem — Number theory

Library / /15 of 860

Number theory Difficulty 4.6 AIME Find the answer

Let $s(n)$ denote the number of 1's in the binary representation of $n$ . Compute $\frac{1}{255} \sum_{0 \leq n<16} 2^{n}(-1)^{s(n)}$

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

Notice that if $n<8,(-1)^{s(n)}=(-1) \cdot(-1)^{s(n+8)}$ so the sum becomes $\frac{1}{255}\left(1-2^{8}\right) \sum_{0 \leq n<8} 2^{n}(-1)^{s(n)}=$ 45 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.