Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that I have N bags, each containing balls of a unique colour. What is the maximum number of pairs I can form without replacing the balls back in the bags and with the following constraints: 1)A pair cannot contain balls of the same colour(i.e from the same bag) 2)There cannot be more than one combination of 2 colours i.e if there's already a pair of red and black balls there cannot be another pair of the aforementioned colours .

My question is whether there's a simple method/formula to solve the above problem. I've also noticed that it strangely resembles the graph theory problem of proving that a degree sequence is graphical or not( which can be solved by the Havel-Hakimi algorithm)...

share|improve this question
add comment

2 Answers 2

Assuming that each bag has enough balls in it, you can form $N$-choose-2 different pairs. That's $N(N-1)/2$.

share|improve this answer
add comment

If you want to phrase it in graph-theoretic terms, let the bags/colors be vertices, and place an edge between vertices when you draw a pair from those bags. Your constraints amount to saying that you have a simple graph: no loops, and no multiple edges. The maximum possible number of edges is found in the complete graph $K_N$ and is $\binom{N}2=\frac12N(N-1)$.

Of course, this assumes that you have at least $N-1$ balls in each bag. If you haven’t, the problem becomes substantially harder: in effect you’re then imposing upper bounds less than $N-1$ on the degrees of at least some of the vertices. In that case you could use the Erdős-Gallai theorem to determine whether you have a realizable degree sequence. If you have, the maximum number of pairs is of course just half the sum of the degrees. If not, you’d need to find the smallest reduction in total degree that would produce a realizable degree sequence. I suspect that one could come up with a reasonably efficient algorithm for doing this, but I’ve not given it a lot of thought.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.