Consider the set S of all binary strings of length 10 (each character is either the digit 0 or the digit 1). Questions in Description below.

Question

Consider the set S of all binary strings of length 10 (each character is either the digit 0 or the digit 1).

a) How many elements are in S?

b) How many elements of S begin and end with 0?

c) How many elements of S begin or end with 0?

d) How many elements of S begin with 10 or have 0 as the third digit?

e) How many elements of S contain two or more 0s?

Answer 1

Understanding OR and AND is essential for this problem.

a) How many elements are in S?

2^10 = 1024 [all ten digits may vary]

b) How many elements of S begin AND end with 0?

2^8 = 256 [only 8 digits may vary]

c) How many elements of S begin OR end with 0?

Begin with 0 = 2^9 = 512

Of the other 512 that begin with 1, there are 512/2 = 256 that end with 0. So 512+256 = 768

d) How many elements of S begin with 10 OR have 0 as the third digit?

Have 0 as the third digit = 2^10/2 = 2^9 = 512

Of the other 512 that have 1 as the third digit, there are 512/4 = 128 that have "10" as the first two.

So, 512 + 128 = 640

e) How many elements of S contain two or more 0s?

You should look forward to learning about Pascal's Triangle. Let's consider binary numbers with four digits and the sum of the digits:

First, consider four-digit binary numbers:

 SUM of 1 bits

0 0 0 0   0

0 0 0 1   1

0 0 1 0   1

0 0 1 1   2

0 1 0 0   1

0 1 0 1   2

0 1 1 0   2

0 1 1 1   3

1 0 0 0   1

1 0 0 1   2

1 0 1 0   2

1 0 1 1   3

1 1 0 0   2

1 1 0 1   3

1 1 1 0   3

1 1 1 1   4

Count of 1’s	0	1	2	3	4
Frequency	1	4	6	4	1

How many elements of S contain two or more 0s ? That's the same as asking, "How many numbers from 0 to 15 have at two or fewer 1's ?" There are 1+4+6 = 11

So, how many elements of S contain two or more 0s ? That's the same as asking, "How many numbers from 0 to 1023 have 8 or fewer 1's (that is, the sum of the digits is 8 or less)? So, 1 + 10 + 45 + 120 + 210 + 252 + 210 + 45 = 1013

0	1	2	3	4	5	6	7	8	9	10
1	10	45	120	210	252	210	120	45	10	1

Answer 2

(a) 2^10 = 1024

(b) 2^8 = 256

(c) 2^9 = 512

(d) 2^7 = 128

(e) 2^8 + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2 + 1 = 256+128+64+32+16+8+4+2+1=511