Maths Olympiad Prep

Library / /1 of 86

Algebra Difficulty 3.7 AMC 10/12 Find the answer Estonia

How many positive integers, where the only allowed digits are 00 and 11, are less than 11111001001111100100?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solutions — 2

Solution 1

The given number has 1111 digits. There are 2111=20472^{11} - 1 = 2047 positive integers with at most 1111 digits each of which is either 00 or 11. We solve the problem by subtracting the number of positive integers that are not less than the given number.
The 1111-digit numbers larger than the given number are all of the form 11111abcde11111abcde. There are 25=322^5 = 32 numbers in this form. Among them, 44 numbers 11111000001111100000, 11111000011111100001, 11111000101111100010 and 11111000111111100011 are less than the given number. Thus the number of positive integers consisting of zeros and ones and being less than 11111001001111100100 is 204732+4=20192047 - 32 + 4 = 2019.

Solution 2

Ordering any two digit sequences that constitute a positional representation on different bases does not depend on the base. This means that if a number is larger than another number on base 22 then the first number is larger than the second number also on base 1010. The number 11111001001111100100 on base 22 equals 210+29+28+27+26+25+22=20202^{10} + 2^9 + 2^8 + 2^7 + 2^6 + 2^5 + 2^2 = 2020 on base 1010. Hence, to solve the problem, it suffices to count all positive integers less than 20202020. The result is obviously 20192019.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.