2012 AIME I Problem 5

Attempt Problem 5 of the 2012 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2012 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

5.

Let BB be the set of all binary integers that can be written using exactly 55 zeros and 88 ones where leading zeros are allowed. If all possible subtractions are performed in which one element of BB is subtracted from another, find the number of times the answer 11 is obtained.

Answer: 330
Concepts:number basecombinations
Difficulty rating: 2460
Solution:

We must count pairs of elements of BB differing by 1,1, say mm and m+1.m + 1. Adding 11 to a binary number turns its trailing block 0111011\cdots1 (a zero followed by kk ones) into 1000,100\cdots0, changing the number of ones by 1k.1 - k. Both numbers have exactly eight ones precisely when k=1:k = 1: mm ends in 01,01, m+1m + 1 ends in 10,10, and the two numbers agree everywhere else.

The shared first eleven digits then consist of the remaining seven ones and four zeros, and since leading zeros are allowed, every arrangement gives a valid pair: (114)=330.\binom{11}{4} = 330. Each pair produces the answer 11 exactly once, so the count is 330.330.

← Problem 4#4
Full Exam

Problem 5 in Other Years