1.8 The Number of Subsets of a Given Size 231.8.20LetAbe a set and letA
2
denote the set of all 2-element subsets ofA.
Which of the following statements is true?
A∪B
2
=
A
2
∪
B
2
;
A∪B
2
⊇
A
2
∪
B
2
;
A∩B
2
=
A
2
∩
B
2
;
A∩B
2
⊆
A
2
∩
B
2
.1.8.21LetBbe a subset ofA,|A|=n,|B|=k. What is the number of all
subsets ofAwhose intersection withBhas 1 element?
1.8.22Compute the binary form of 25 and 35, and compute their sum in the
binary notation. Check the results against adding 25 and 35 in the usual decimal
notation and then converting it to binary.
1.8.23Prove that every positive integer can be written as the sum of different
powers of 2. Also prove that for a given number, there is only one way to do so.
1.8.24How many bits does 10^100 have if written in base 2?1.8.25Starting from Washington, DC, how many ways can you visit 5 of the
50 state capitals and return to Washington?
1.8.26Find the number of all 20-digit integers in which no two consecutive
digits are the same.
1.8.27Alice has 10 balls (all different). First, she splits them into two piles;
then she picks one of the piles with at least two elements, and splits it into two;
she repeats this until each pile has only one element.
(a) How many steps does this take?
(b) Show that the number of different ways in which she can carry out this
procedure is
10
2
·
9
2
···
3
2
·
2
2
.[Hint: Imagine the procedure backward.]1.8.28You want to send postcards to 12 friends. In the shop there are only 3
kinds of postcards. In how many ways can you send the postcards, if
(a) there is a large number of each kind of postcard, and you want to send one
card to each friend;
(b) there is a large number of each kind of postcard, and you are willing to send
one or more postcards to each friend (but no one should get two identical
cards);
(c) the shop has only 4 of each kind of postcard, and you want to send one
card to each friend?