Maths Olympiad Prep

Library / /301 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Three, (50 points) Let the number of all positive integers satisfying the following conditions be NN:
(1) less than or equal to 2,012;
(2) the number of 1s in their binary representation is at least 2 more than the number of 0s.
Find the sum of the digits of NN.

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

Solution

Three, from 2012=(11111011100)22012=(11111011100)_{2}, we know that the numbers satisfying the conditions have at most 11 digits in binary representation.

The first digit must be 1, so the number of d+1d+1-digit numbers with exactly k+1k+1 digits being 1 is Cdk\mathrm{C}_{d}^{k}, and condition (2) is equivalent to
k+1dk+2kd+12dkd12. \begin{array}{l} k+1 \geqslant d-k+2 \\ \Leftrightarrow k \geqslant \frac{d+1}{2} \Leftrightarrow d-k \leqslant \frac{d-1}{2} . \end{array}

First, consider the numbers in [1,2048)[1,2048) that satisfy condition (2)
There are
d=110k={d+12]dCdk=d=110[d12]=a=05(i=0u1C2a1i+i=0a1C2ai)=a=15[22a2+12(22aC2aa)]=34a=154n12a=1aC2aa=(451)12(C21+C42+C63+C84+C105)=102312(2+6+20+70+252)=848 (numbers),  \begin{array}{l} \sum_{d=1}^{10} \sum_{k=\left\{\frac{d+1}{2}\right]}^{d} \mathrm{C}_{d}^{k}=\sum_{d=1}^{10}\left[\frac{d-1}{2}\right] \\ =\sum_{a=0}^{5}\left(\sum_{i=0}^{u-1} \mathrm{C}_{2 a-1}^{i}+\sum_{i=0}^{a-1} \mathrm{C}_{2 a}^{i}\right) \\ =\sum_{a=1}^{5}\left[2^{2 a-2}+\frac{1}{2}\left(2^{2 a}-\mathrm{C}_{2 a}^{a}\right)\right] \\ =\frac{3}{4} \sum_{a=1}^{5} 4^{n}-\frac{1}{2} \sum_{a=1}^{a} \mathrm{C}_{2 a}^{a} \\ =\left(4^{5}-1\right)-\frac{1}{2} \cdot\left(\mathrm{C}_{2}^{1}+\mathrm{C}_{4}^{2}+\mathrm{C}_{6}^{3}+\mathrm{C}_{8}^{4}+\mathrm{C}_{10}^{5}\right) \\ =1023-\frac{1}{2}(2+6+20+70+252) \\ =848 \text { (numbers), } \end{array}

where x\lceil x\rceil represents the smallest integer not less than the real number xx, and [x][x] represents the largest integer not greater than the real number xx.
Since there are 35 integers in [2013,2048)[2013,2048), and only
(11111100000)2=2016 (11111100000)_{2}=2016

does not satisfy condition (2), we have
N=84834=814 N=848-34=814 \text {. }

Therefore, the sum of the digits of NN is 13.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.