Page 592 - Discrete Mathematics and Its Applications

Computations and Explorations 571

9. Describe the solution of Ulam’s problem (see Exercise 28 13. Look up the rules of the old French card game of rencon-
in Section 8.3) involving searching with one lie found by tres. Describe these rules and describe the work of Pierre
Andrzej Pelc. Raymond de Montmort on le problème de rencontres.
14. Describe how exponential generating functions can be
10. Discuss variations of Ulam’s problem (see Exercise 28 in
used to solve a variety of counting problems.
Section 8.3) involving searching with more than one lie
and what is known about this problem. 15. Describe the Polyá theory of counting and the kind of
counting problems that can be solved using this theory.
11. Define the convex hull of a set of points in the plane and
16. The problème des ménages (the problem of the house-
describe three different algorithms, including a divide-
holds) asks for the number of ways to arrange n couples
and-conquer algorithm, for finding the convex hull of a
around a table so that the sexes alternate and no husband
set of points in the plane.
and wife are seated together. Explain the method used by
12. Describe how sieve methods are used in number theory. E. Lucas to solve this problem.
What kind of results have been established using such 17. Explain how rook polynomials can be used to solve count-
methods? ing problems.