Can you help me with this probabilities question? Problem 2 [20 pts (5,5,10)]: C

Question

Can you help me with this probabilities question?

Problem 2 [20 pts (5,5,10)]: Count Possibilities with Bits A. How many natural numbers smaller than 1024 are the sum of four different powers of 2? four different hint. Think of this problem in binary (bits). What does it mean for a number to be the sum of B. How many natural numbers between 512 and 1024 are the sum of four different powers of powers of 2? 2? C. How many natural numbers smaller than 1000 are the sum of four different powers of 2?

Explanation / Answer

=A)

1024 in binary is 100 0000 0000 (binary string of length 11)

Now numbers < 1024 will contains binary string of length 10 at max

Hence binary strings in general format can be represented as xx xxxx xxxx

Here x can be any of 0 or 1.

Given the number should be represented as a sum of four different powers of 2.

Now in the 10 x we need exactly 4 1's and 6 0's

In 10 x we can select 4 1's in 10c4 ways which is = 210

Hence total numbers < 1024 which can be represented as a sum of four different powers of 2 = 210.

B)

Here before we find numbers from 512 and 1024 first

we will calculate numbers smaller than 512   

512 in binary is 10 0000 0000 (binary string of length 10)

Now numbers < 512 will contains binary string of length 9 at max

Hence binary strings in general format can be represented as x xxxx xxxx

Here x can be any of 0 or 1.

Given the number should be represented as a sum of four different powers of 2.

Now in the 9 x we need exactly 4 1's and 5 0's

In 9 x we can select 4 1's in 9c4 ways which is = 126

Hence total numbers < 512 which can be represented as a sum of four different powers of 2 = 126.

Now total numbers between 512 and 1024 is = (total numbers < 1024) - (total numbers < 512)

= 210 - 126 = 84

Hence total numbers between 512 and 1024

which can be represented as a sum of four different powers of 2 = 84.

C)

Numbers smaller than 1000 that can be represented as sum of 4 different powers of 2 =

( Numbers smaller than 1024 which can be represented as a sum of 4 different powers of 2 -

Numbers between 999 and 1024 which can be represented as a sum of 4 different powers of 2 )

We know, Numbers smaller than 1024 which can be represented as a sum of 4 different powers of 2 = 210

Now Numbers between 999 and 1024 which can be represented as a sum of 4 different powers of 2 = 0

Hence Numbers smaller than 1000 that can be represented as sum of 4 different powers of 2 = 210.

  

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---