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.

I wrote a prolog program to print out all of the possible solutions for the following problem:

You have eight colored balls: 1 black, 2 white, 2 red and 3 green. The balls in positions 2 and 3 are not green. The balls in positions 4 and 8 are the same color. The balls in positions 1 and 7 are of different colors. There is a green ball to the left of every red ball. A white ball is neither first nor last. The balls in positions 6 and 7 are not red.

The program works fine, but I need to mathematically calculate how many solutions there are (with same colors being distinct, and same colors being indistinct.) Any ideas about how to go about this? At first, I tried to find all possible of solutions of each rule independently and then multiplying that together. But i realized this was not correct because there would be a lot of solutions overlapping that will be counted more than once. My second idea was to do 8! and subtract all not-allowed solutions from this by each rule. But this would also delete duplicates. Any ideas? Thanks in advance.

share|improve this question
    
Not sure what "mathematically calculate" means here, other than just enumerate carefully. I doubt there's a simpler way to do it, since there are so many different constraints. However, one can say that the number of solutions with distinguishable balls is $2!2!3!=24$ times greater than the number of solutions with indistinguishable balls. –  mjqxxxx Nov 25 '12 at 1:37
add comment

migrated from stackoverflow.com Nov 25 '12 at 1:07

This question came from our site for professional and enthusiast programmers.

2 Answers

I used the following SWI-Prolog program:

:- use_module(library(clpfd)).

balls(Bs) :-
        % You have eight colored balls:
        Bs = [One,Two,Three,Four,_Five,Six,Seven,Eight],
        % 1 black, 2 white, 2 red and 3 green.
        % (black = 0, white = 1, red = 2, green = 3)
        global_cardinality(Bs, [0-1,1-2,2-2,3-3]),
        % The balls in positions 2 and 3 are not green.
        Two #\= 3, Three #\= 3,
        % The balls in positions 4 and 8 are the same color.
        Four = Eight,
        % The balls in positions 1 and 7 are of different colors.
        One #\= Seven,
        % A white ball is neither first nor last.
        One #\= 1, Eight #\= 1,
        % The balls in positions 6 and 7 are not red.
        Six #\= 2, Seven #\= 2,
        % There is a green ball to the left of every red ball.
        green_left(Bs, -1).

green_left([], _).
green_left([B|Bs], Prev) :-
        B #= 2 #==> Prev #= 3,
        green_left(Bs, B).

num_col(0, black).
num_col(1, white).
num_col(2, red).
num_col(3, green).

and obtained exactly 3 solutions with same colours being indistinct:

?- balls(Bs), label(Bs), maplist(num_col, Bs, Cols), 
   writeln(Cols), false.
[green,red,black,green,red,white,white,green]
[green,red,white,green,red,black,white,green]
[green,red,white,green,red,white,black,green]
false.

It should be easy to obtain the number of solutions with same colours being distinct from this.

share|improve this answer
add comment

Here's my analysis (assuming balls are indistinguishable):

First, condition on where the first green ball appears, and note that it can only appear in the first position. This is because

  1. It cannot be 2 or 3 by constraint.
  2. It cannot be 4 because then 8 must be green as well, and the 2 reds can't be in 6 or 7.
  3. It cannot be 5 or later, because there are 3 greens and 2 reds to fit into fewer than 5 spots.

Now, we know the pattern is $g-------$. Then, 7 cannot be green, and so the remaining greens must either be in positions 4 and 8 or in positions 5 and 6.

So we are left with two patterns as cases:

  1. $g--g---g$
  2. $g---gg--$

We need to place the remaining 5 balls (1 black, 2 white, 2 red).

In the first case, we only need to constrain 1 to be different from 7 and no reds in 6 or 7. This is a fairly straightforward counting problem.

In the second case, either the reds are in 2 and 3 or they are in 4 and 8. Again, we've reduced to another fairly simple counting situation.

The exact answer depends on what you meant by "There is a green ball to the left of every red ball."

  1. If you meant 'directly preceding', then case 2 never occurs, and case 1 implies a pattern of $gr-gr--g$, leaving us to count the number of ways to arrange 2 white balls and 1 black ball with no constraints. This comes out to $\frac{3!}{1!2!} = 3$.
  2. If you meant 'somewhere before', then simple counting arguments give a total of $13$ ways for both cases.
share|improve this answer
add comment

Your Answer

 
discard

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