Problem Set 4

Most of the problems are assigned from the required textbook Amazon logo Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books]

A problem marked by * is difficult; it is not necessary to solve such a problem to do well in the course.

Problem Set 4

  • Due in Session 11
  • Practice Problems
    • Session 8: Chapter 6: Exercises 7, 8, 10. Problem 10 is famous for its very tricky solution. (The second paragraph of the solution to Problem 10 belongs with Problem 9.)
    • Session 9: Chapter 6: Exercises 2, 3, 5, 7, 8, 14, 18, 23
    • Session 10: None
  • Problems Assigned in the Textbook
    • Chapter 6: Exercises 26, 31. Problem 26 seems to be missing the verb "are."
    • Chapter 6: Exercises 43, 49
  • Additional Problems
    • (A4) This problem is a variation of a result discussed in class. (For the class problem, see This resource may not render correctly in a screen reader.Problem 1: Names in Boxes (PDF).) We have the same 100 prisoners and evil warden. As before, the prisoners are brought one at a time into a room with 100 boxes labeled 1,2,…,100. Inside each box is the name of a prisoner, a different name in each box. This time a prisoner must open 99 boxes, one at a time. If the prisoner encounters his own name, then all prisoners are killed. The prisoners may talk together before the first prisoner enters the room with the boxes. After that there is no further communication. A prisoner cannot leave a signal in the room. All boxes are closed before each prisoner enters the room. Clearly the probability that the prisoners aren't killed cannot exceed 1/100, since that is the probability that the first prisoner does not encounter his name. What strategy maximizes the probability that the prisoners are not killed, and what is this maximum probability?
    • (A5) Let n≥3. Pick a permutation π of 1,2,...,n at random (uniform distribution, i.e., all permutations are equally likely). What is the probability that 1,2,3 are all in different cycles of π?
    • (A6*) Call two permutations a1, ..., an and b1, ..., bn of 1,2,...,n equivalent if one can be obtained from the other by switching adjacent terms that differ by at least two. For instance 254613 is equivalent to 542361, one sequence of switches being 254613, 524613, 542613, 542631, 542361. Clearly this is an equivalence relation. (It is assumed that you know about equivalence relations and equivalence classes.) How many equivalence classes are there? For instance, when n=3 there are the four classes {123}, {132,312}, {213,231}, {321}.
  • Bonus Problems
    • None