2012 AIME I Problem 5

Below is the professionally curated solution for Problem 5 of the 2012 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:number basecombinations

Difficulty rating: 2460

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.

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 4Full ExamProblem 6

Problem 5 in Other Years