How many different positive numbers smaller than 2*10^8 can be formed

Question

How many different positive numbers smaller than  2*10^8  can be formed using the digits 1 and 2 only?

A. 256
B. 510
C. 512
D. 766
E. 6561

sowragu · Answer

Any combination of number starts with digit "2" is greater than 2*10^8
Total possible combinations with 1 and 2 = 2^9
Total possible combinations with 2 as starting digit = 2^8

Numbers smaller than 2*10^8 can be formed = 2^9 - 2^8
 = 2^8(2-1)
 = 256.

IMO A

Another method:

Start with most restrictive clause:

Any number starts with 1 is smaller than 2*10^8.

1*2^8
=256

IMO A

BrentGMATPrepNow · Answer

Let's start with all 9-digit numbers that are less than 200,000,000 So, let's take the task of creating 9-digit numbers and break it into stages . Stage 1 : Select the 1st digit. This digit must be 1, so we can complete stage 1 in 1 way Stage 2 : Select the 2nd digit. This digit can be either 1 or 2, so we can complete stage 2 in 2 ways Stage 3 : Select the 3rd digit. This digit can be either 1 or 2, so we can complete stage 3 in 2 ways Stage 4 : Select the 4th digit. This digit can be either 1 or 2, so we can complete stage 4 in 2 ways . . . . . Stage 9 : Select the 9th digit. This digit can be either 1 or 2, so we can complete stage 3 in 2 ways By the Fundamental Counting Principle (FCP), we can complete all 9 stages (and thus create a 9-digit number) in (1)(2)(2)(2)(2)(2)(2)(2)(2) ways This equals 2^8 . Now, we'll count all 8-digit numbers So, let's take the task of creating 8-digit numbers and break it into stages . Stage 1 : Select the 1st digit. This digit can be 1 or 2 , so we can complete stage 1 in 2 ways Stage 2 : Select the 2nd digit. This digit can be either 1 or 2, so we can complete stage 2 in 2 ways . . . . . Stage : Select the 8th digit. This digit can be either 1 or 2, so we can complete stage 3 in 2 ways By the FCP, the total number of outcomes = 2^8 If we follow the same steps for 7-digit numbers, we get a total of 2^7 outcomes. And so on. So, the TOTAL number of possibilities = 2^8 + 2^8 + 2^7 + 2^6 ..... + 2^1 = 766 Answer: D -------------------------- Note: the FCP can be used to solve the MAJORITY of counting questions on the GMAT. For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting/video/775 You can also watch a demonstration of the FCP in action: https://www.gmatprepnow.com/module/gmat ... /video/776 Cheers, Brent

kinsho · Answer

So we are looking for  ALL  the numbers  less  than  2*10^8 .

Start with single-digit numbers. We only have 1 and 2.

Move on to two-digit numbers. There, we have four possible numbers - 11, 12, 21, 22.

At this point, a trend should be becoming noticeable here. The number of ways you can form n-digit numbers using only the numbers 1 and 2 is  2^n . This is pretty sensible from a permutation perspective, given that each digit in any n-digit number can be thought of as slots in which you are allowed to place any combination of 1s and 2s.

Now we are working with numbers that can grow to be nine-digits long, but we have to mindful of the ceiling the problem places on us -  2*10^8 . The number of nine-digit numbers that we can form are limited to those numbers that have 1 as its first digit. The rest of the 8 digits can be populated with any combination of 1s and 2s.

Therefore, for nine-digit numbers, we have  2^8  different numbers that can be formed using only 1s and 2s. For eight-digit numbers, we also have  2^8  different numbers that can be formed (the first digit is not constrained to 1). For seven-digit numbers, we have  2^7  different possibilities. For six-digit numbers, we have  2^6  possibilities. A pattern should be becoming evident here. Once you see that pattern, you can form an equation that will give you the answer.

2^8 + 2^8 + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1

256 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 = 766

The answer is  766 (D)

chetan2u · Answer

Hi,
you have understood the Q well but made a critical error..

The Q asks for all smaller numbers but you have found only for 9-digits number..
your Solution would have been OK had the Q been
 How many different 9-digit positive numbers smaller than 2*10^8  can be formed using the digits 1 and 2 only?

chetan2u · Answer

Hi,
such Q requires initially understanding the Problem in terms of number and then Progressions-

since here we have 1 digit number to 9 digit number, 2*10^8..
so lets work out digit wise-
1)  1-digit--  1 and 2 : total-  2^1 way
2)  2-digit--  two places and can be filled by two numbers 1,2 : ways=  2*2=2^2 
3)  3-digit--  3 places and can be filled by two numbers 1,2 : ways= 2*2*2=2^3 
and so on till ..
8)  8-digit--   2^8 
9)  9-digit--   2^9 .. but here only numbers with first digit as 1 as we require number <2*10^8  : total \frac{2^9}{2}

Total ways=  2^1+2^2+2^3+2^4+2^5+2^6+2^7+2^8+\frac{2^9}{2} 
 this can also be solved with Geometric Progression 
 SUM=  \frac{a(r^N-1)}{(r-1)} .. where r=2, a=2^1, N=8.. 
so total = \frac{2(2^8-1)}{(2-1)} + \frac{2^9}{2} =2*255 + \frac{512}{2}=510+256=766 
Ans= 766
D

Regor60 · Answer

With a few calculations the answer choices can be eliminated to just one.

2*10^8 contains 9 digits.

With the restriction of being less than the above, the largest can only start with 1, leaving 2^8 = 256 ways to fill the remaining 8 digits.

Next we have an 8 digit number to complete. This can also be completed 2^8 = 256 ways.

Total ways so far equals 512 and we have 7 digit through 1 digit to complete, so only answers D & E are possible.

Since the sum of all possible digit formations is a multiple of 2, Answer E is not possible, leaving Answer D as the correct choice.

So

How many different positive numbers smaller than 2*10^8 can be formed

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

How many different positive numbers smaller than 2*10^8 can be formed

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards