Solutions to the Problems
This chapter contains solutions for all problems presented at the end of the theory chapters. In many problems, more than one solution is shown (perhaps some not using the tools from the subject it comes from).
- PDF / 677,565 Bytes
- 55 Pages / 477 x 684 pts Page_size
- 116 Downloads / 258 Views
Solutions to the Problems
9.1
Solutions for Chap. 1
Solution 1.1 Note that for the rooks not to attack each other they must use 3 different 2 rows and 3 different columns. There are 53 ways to choose them. Then we have to assign to each row its corresponding column where the rooks are going to be placed. 2 There are 3! ways to do this. Thus there are 53 3! = 600 ways to place the rooks. Solution 1.2 Note that there are 19 women. For each woman that has a woman to its right there is a woman that has a woman to its left. Thus there are 12 women that have a man to their left. Hence, there are 12 men that have a woman to their right. Thus there are 16 men, which gives us a total of 35 persons at the table. Solution 1.3 Consider a set of n elements. First we choose k of them and paint them red. Then we choose r red elements and paint them blue. Then we choose s blue elements and paint them green. There are nk kr rs ways to do this. In the end we have s green elements, r − s blue elements and k − r red elements. To paint them this way we can also paint first the s green elements. Then, out the remaining elements we choose r − s and paint them blue, and out of the remaining elements n−r paint k − r in red. There are ns n−s r−s k−r ways to do this. Since we are counting the same colorings, the two results must coincide. Solution 1.4 First order the shoes in one row and the socks in another. There are (8!)2 ways to do this. To decide the order in which the spider is going to put on the shoes and socks let us write in a list the numbers from 1 to 8 twice in some order. The spider is going to read this list and, according to the number it reads, put a sock or a shoe on that foot (depending on whether it already has a sock on it or not). To write these number note that there are (16)! to order 16 numbers, but we are counting 2! times each list because the numbers 1 are indistinguishable, 2! times because the numbers 2 are indistinguishable, etc. Thus the number of ways to put 2 the shoes and socks is 16!(8!) . 28 P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_9, © Springer Basel 2013
113
114
9
Solutions to the Problems
Solution 1.5 Paint the first column in any way. There are 28 possibilities. Note that if there are two consecutive squares of the same color, in the next column they must have the colors swapped. Having these two squares with the colors swapped, the whole next column must have opposite colors to the first column. We can go on this way and the whole board coloring is fixed. If there were no two consecutive squares of the same color in the first column then it had to be painted alternating colors. There are only 2 ways to do this. If this happens, then the next column must also be alternating colors, and so on. Thus we only have to choose with which color each column starts. In the first case there were 28 − 2 colorings, while in the second case there were 28 . Thus there’s a total of 28 + 28 − 2 = 2(28 − 1) possibilities. Solution 1.6 F
Data Loading...
