From: Robin Chapman Newsgroups: sci.math Subject: Re: Combinatorial Q, how to pick n different cards Date: Tue, 10 Mar 1998 07:48:40 -0600 In article <6e2v2g$92h$1@ratatosk.uio.no>, kjellpe@sisyfos.uio.no (Kjell Fredrik Rogstad Pettersen) wrote: > > Let n,k be positive integers. Suppose you are given n*k cards, > each card is marked with a number from 1 to n such that each > number is represented k times. You shuffle and deal the cards > to n persons, k cards to each one. > > My question is: Is it then possible for each person to lay down > one card so that every number from 1 to n is given once? > > For k=1 or k=2, the answer is yes. How is it in general? Is > there an easy algorithm, or do you have a counterexample? > Any reference? Yes. This is a consequence of Philip Hall's Marriage theorem. The prosaic version of Hall's theorem states that if A_1, A_2, ..., A_n are sets then there are distinct elements a_1, a_2, ..., a_n with a_j in A_j for each j iff the following condition holds: For each subset J of {1, 2,.., n} the union of the A_j with j in J has at least |J| elements. Hall's theorem is proved in many texts in combinatorics. There are many generalizations notably the maxflow/mincut theorem in network flow. Any efficient algorithm for finding maximum flows can be translated into an algorithm for finding the a_j s. In the present problem take A_j to be the set of values of the cards held by the j-th person. It's easy to see that Hall's condition is satsified. The more poetic (albeit sexist and heterosexist) version of hall considers n young ladies who desire a partner in marriage. Each has their own list of acceptable beaux, and the result is that theu can all acheive their aim provided that each subset of the ladies between them have at least as many men on their lists between them as there are ladies in the subset. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading