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.

  • 0
    @goldenmean: I used R - slow but it is fairly easy - see answer2011-06-06

1 Answers 1

1

An answer because the comments will not take what follows:

A simulation in R (poorly written and slow, but it works)

ss <- 10000 balls <- 9 boxes <- 40   diff <- function(x,y) {abs(x-y)} dupe <- function(x) {sum(duplicated(x))}  counter <- 0 for (i in 1:ss) {   a <- sample(1:boxes, balls)   b <- as.data.frame(outer(a,a,FUN="diff"))   if (sum(sapply(b, FUN="dupe")) == 0) {counter = counter+1} }  counter/ss choose(boxes,balls) * counter/ss 

giving the answer

> counter/ss [1] 0.0283 > choose(boxes,balls) * counter/ss [1] 7738320 

(I actually took a larger slower sample, but the result was similar.)

So 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.