From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Comb. question (RP)
Date: 18 Jun 1997 16:36:02 GMT

In article <5nsdh2$hjc$1@msunews.cl.msu.edu>,
Mark W Brehob <brehob@cps.msu.edu> wrote:

>Say we have 2 sets of bowls: one Red and one Blue.
>Each bowl is given a unique label (say Blue 1, 2, 3...N and Red
>1, 2, 3 ...N).  There are the same number of bowls in each set.
>
>Now you have X eggs.  Each egg has a blue number and a red number.  The
>egg must be placed either in the appropriate blue bowl or red bowl.
>
>What is the probability that all X eggs can be placed in such a way
>that no bowl has two (or more) eggs in it?
>
>Assume that the numbers on the egg are independent and generated
>using a uniform distribution.
>
>I then went on to ponder if given N eggs and N bowls if
>the problem might not be NP-hard.  I then followed up to my 
>own post that it can actually be solved in O(N^2).

I didn't see those other posts, but I've not been following the news
regularly. You can convert the problem into something more mainstream
as follows.

With the eggs in hand, construct a graph as follows: the set of
vertices is the set of eggs. Draw an edge between two vertices if the
two eggs have either the same red number or the same blue number. (If
two eggs share both numbers I guess I would draw two edges between
those vertices, so really this is a "multigraph".) This is a graph
with X vertices. (The number of edges is not immediately clear.)
There's nothing gained here from having equal numbers of red
and blue bowls.

Now note that if the eggs can be arranged in the way you want, then
the color of the bowl into which egg  v  is placed determines a coloring
of the vertices of the graph in such a way that each edge only joins
vertices of distinct colors; and conversely such a 2-coloring of the
graph gives you placement instructions so the eggs sit in the bowls
correctly.

So this is really a graph-coloring question. Since you're coloring
with just 2 colors, an answer of sorts is available: the graph can be
colored iff there is no cycle of odd length. (So it looks like there
_is_ an advantage to having only two colors of bowls!)

This approach should make it possible to decide quickly whether a
specific set of eggs can be placed in their bowls. I have some
references somewhere regarding the optimal speed of 2-colorings but
I can't find them right now.

Maybe it's not quite the right approach for your probability question
since there isn't a one-to-one correspondence between the equally-likely
events you want to count and the set of random graphs with the right
number of edges and vertices.

Indeed, on the one hand, not every graph will arise. You will only
have graphs with this property: the set of edges can be partitioned
into two sets -- the "red" edges and the "blue" edges -- with the
property that for each vertex v, the set of vertices in the "red"
edges containing that vertex v forms a complete graph, as does the set
of vertices in the "blue" edges containing v.  (If you collapse two
edges into one whenever two eggs share both numbers, you can avoid
having multigraphs, but then you have to reinterpret the previous
sentence to allow some edges to be both red and blue!)

And on the other hand, distinct egg labellings can give the same
graphs. For example, if each egg is represented as an ordered pair
[x,y] showing its red and blue numbers in order, you seem to want the
events [[1,1],[2,2]] and [[1,1],[3,3]] to count as distinct
combinations of labellings of 2 eggs for 3 red and 3 blue bowls, yet
each gives a graph with two vertices and no edges.


dave