2
$\begingroup$

If there are $10$ blue balls and $10$ red balls. What are the total number of arrangements of these balls such that no three consecutive balls are of the same color?

I attempted this problem by subtracting unfavourable cases from total number of cases.

Unfavourable cases include those formed by permuting balls with a group of $3$ of $1$ color, and then those of another color. And then excluding those formed by permutations of balls with a group of $3$ red balls as well as a group of $3$ blue balls.

But this leaves many cases unattended.

$\endgroup$
  • $\begingroup$ Any arrangement either starts with two balls of the same color or just one, followed by the same type of arrangement. This gives the recurrence relation for the Fibonacci numbers. So, the total number of arrangements is just twice the 20th Fibonacci number. $\endgroup$ – Rus May Feb 28 '18 at 21:25
0
$\begingroup$

As a brute force approach, divide up each color of balls into sets of size $1$ or $2$ each. Then count the possible number of orderings of each set and then for each partition consider the square of the number of orderings of that partition (if each color is divided into the same number of sets) and also the product with the number of orderings of the next smaller number of sets (if one color both starts and ends the sequence) then multiply by $2$ because either color could have started the sequence. $$\begin{array}{c|cccc}\text{Sets}&\text{Orderings}&\text{Same}&\text{Previous}&\text{Total}\\ \hline5&1&1&0&1\\ 6&15&225&15&240\\ 7&35&1225&525&1750\\ 8&28&784&980&1764\\ 9&9&81&252&333\\ 10&1&1&9&10\\ \hline&&&&4098\end{array}$$ So our final answer is $2\times4098=8196$. As confirmation, I offer total brute force:

program balls1
   implicit  none
   integer i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i
   logical balls(20)
   integer total, count
   total = 0
   count = 0
   do i1=1,11
      do i2=i1+1,12
         do i3=i2+1,13
            do i4=i3+1,14
               do i5=i4+1,15
                  do i6=i5+1,16
                     do i7=i6+1,17
                        do i8=i7+1,18
                           do i9=i8+1,19
                              do i10=i9+1,20
                                 balls = .FALSE.
                                 balls([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]) = .TRUE.
                                 count = count+1
                                 do i = 1,18
                                    if(all(balls(i:i+2)).OR..NOT.any(balls(i:i+2))) exit
                                 end do
                                 if(i>18) total=total+1
                              end do
                           end do
                        end do
                     end do
                  end do
               end do
            end do
         end do
      end do
   end do
   write(*,*) total,count
end program balls1

Output was

8196      184756
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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