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.

We randomly arrange balls numbered 1-100 in a line. What is the probability that there is a spot which splits the balls into two groups: All the balls preceding the splitting point are placed in ascending order (regarding their number), and all the balls from that point forward are place in decending order?

What I did: 100 different balls are placed in a line. Therefore $|\Omega| = 100!$

There are 100 possible "split-points". We'll mark $N$="split-point". For every $N$, the possibility of it being a split-point is $\binom{100}{N}$, as we choose the first $N$ balls and have only one way to arrange them and the remaining $100-N$ balls. Therefore: $$P(\text{a split point exists})=\frac{\sum\limits_{N=1}^{100}\binom{100}{N}}{100!}=\frac{\sum\limits_{N=0}^{100}\binom{100}{N}-1}{100!}=\frac{2^{100}-1}{100!}$$

But the answer given is:$$\frac{2^{99}}{100!}$$

Am I wrong? How?

Thank you for your time and effort.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

You are overcounting in one respect (or possibly two). First consider that you identify the position of the "split" with the location of a ball, so you say there are 100 possible "split" points. But really we are talking about where the 100 ball (highest point) should go.

Once you pick that position k, the subsets of size k-1 and 100-k to the left and right can be chosen (and the arrangement of balls within the two stretches is forced). But really you are picking subsets of 99 balls at this point.

So redo the calculation and I think you'll get the book answer.

share|improve this answer

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.