2
$\begingroup$

I read this puzzle as below.

You have 40 boxes, all placed in a row at exact intervals of 1 meter. You also have 9 balls(all same type). You wish to place all the balls in the boxes, no more than one ball in each box, so that there are no three boxes A, B, and C such that the distance between A and B is equal to the distance between B and C. How many ways can you arrange the balls in the boxes?

e.g. (For clearer understanding) For 5 boxes and 4 balls Then only possible arrangement is as below

Boxes: 1 2 3 4 5

Balls: B B - B B

I want to come up with a formula in terms of nPr (permutation) or nCr(combination) of r objects out of n objects and other some terms in the formula for this particular case(40 boxes,9 balls) and generic formula for n boxes and r balls.

I am trying to solve this first on paper by manually listing down arrangements for different values of boxes and balls. I tried for combinations (5,4) , (6,4) , (7,4), ... but haven't seen a pattern to construct a generic formula. I have below questions regarding this-

1.Should we consider permutations(where order of balls is not important) or combinations(where order of balls is important).

2.What would be the generic relation for solving this problem.

Any pointers useful.

  • 1
    The order of the balls is irrelevant (since they are all the same type). You are trying to select boxes (combinations) subject to specific restrictions.2011-06-05
  • 0
    I thought so. But the original puzzle does not mention anything about this and left it open.2011-06-05
  • 0
    This problem doesn't really have anything to do with the difference between permutations and combinations. Which one you use will depend upon which method you come up with of counting the possibilities. I would suggest counting the combinations using inclusion-exclusion.2011-06-05
  • 0
    As others have noted the problem is definitely about combinations, but that doesn't mean that the solution will necessarily be in terms of only the combination functions.2011-06-06
  • 0
    Simulation suggests the answer is about 2.8% of the ${40 \choose 9}$ possibilities, so between 7.5 and 8 million in total. A brute force enumeration and check may turn out to be the easiest way to find an exact solution.2011-06-06
  • 0
    @All: Sorry a bit confused from various comments above. 1. What do u think, one should consider combinations or permutations, with some restriction applied such that only certain permutations/combinations are valid. 3. @Henry: How did u infer 2.8% of nCr? and how does it come out 7.5 to 8 million?2011-06-06
  • 0
    @goldenmean: There are ${40 \choose 9}$ or 273,438,880 ways of putting 9 (indistinguishable) balls into 40 (distinguishable) boxes such that no box has more than one ball. This becomes $9!$ times greater, i.e. 99,225,500,774,400, if you decide to distinguish between the balls. I ran a simulation looking at a large number of cases and found that about 2.8% of the cases in the simulation met your condition on distances. So the answer will be about 2.8% of the total number of ways, i.e. between 7.5 and 8 million, or between 2.5 and 3 trillion on the bigger count.2011-06-06
  • 0
    @Henry:If i may ask, what language did u do the simulation in? What is the restrictive / excluding condition look like in that language? Can u give some pointers.2011-06-06
  • 0
    @goldenmean: I used R - slow but it is fairly easy - see answer2011-06-06

1 Answers 1