Track / Stage 4 / 234 of 340 #1134 of 2604

Problem 1134

AMC 12 late, AIME early

Algebra Difficulty 4.8 Prove it Harvard-MIT Mathematics Tournament · United States

a and b are positive integers. When written in binary, $a$ has 2004 1's, and $b$ has 2005 1's (not necessarily consecutive). What is the smallest number of 1's $a+b$ could possibly have?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Consider the following addition:
$\begin{array}{r} 111\cdots 100\cdots 01 \\ + \\ 11\cdots 11 \end{array}$
By making the blocks of 1's and 0's appropriately long, we can ensure that the addends respectively contain 2004 and 2005 1's. (To be precise, we get $a = 2^{4008} - 2^{2005} + 1$ and $b = 2^{2005} - 1$ .) Then the sum has only one 1. And clearly it is not possible to get any less than one 1.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.