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.

Here's a problem in my textbook:

"From a set of 2n + 1 consecutively numbered tickets, three are selected at random without replacement. Find the probability that the numbers of the tickets form an arithmetic progression. [The order in which the tickets are selected does not matter.]"

I tried to solve it by first arbitrarily choosing 2 numbers from the first n+1 tickets. This is because in any 3 tickets in an arithmetic progression there must be at least 2 tickets from the first half of the pile. Once we've chosen our two numbers there is only one possible third ticket. Thus the probability must be 2C3/[(2n+1)C3]. However, the textbook gives n^2/[(2n+1)C3].

What went wrong?

share|improve this question
    
There need not be two from the first half. Let $n=3$ so the tickets range from $1$ to $7$. $5,6,7$ are in arithmetic progression. Isn't 2C3=0? –  Ross Millikan Jan 15 '13 at 21:28

3 Answers 3

up vote 1 down vote accepted

${{2n+1} \choose 3}$ is the number of ways to pick three tickets, so the book is claiming that there are $n^2$ ways to select three ticket in arithmetic progression. To see this, if we count the ways to pick the highest and lowest such that they have the same parity, there is a specific ticket for the middle. If the lowest is $1$, there are $n$ choices, if the lowest is $2$ or $3$, there are $n-1$, if the lowest is $4$ or $5$ there are $n-2$, so the total is $n+2(n-1)+2(n-2)+\ldots+2(1)=\frac {n(n+1)}2+\frac {(n-1)n}2=n^2$

share|improve this answer

This is because in any 3 tickets in an arithmetic progression there must be at least 2 tickets from the first half of the pile.

One of the things that went wrong is that your reasoning here is false. For example, if $n=10$, so you have tickets from 1 to 21, say, then 19,20,21 is an arithmetic progression that doesn't contain any tickets from the first half of the pile.

Once we've chosen our two numbers there is only one possible third ticket.

is also false. Back to the first example, if you selected 16 and 18, you could then select either 14, 17, or 20, any of which would give an arithmetic progression.

share|improve this answer
    
Why is n^2/[(2n+1)C3] –  user54609 Jan 15 '13 at 21:30
1  
@EricDong That wasn't your question. Your question was "What went wrong", and Jonathan gave a good explanation of why all your steps are wrong. –  Calvin Lin Jan 15 '13 at 21:36

Hint: We count the number of increasing arithmetic progressions. I suggest you do it the hard way, by working out a detailed example, and then generalizing.

Let $2n+1=13$.

How many AP are there with middle term $2$? Clearly only $1$.

How many AP with middle term $3$? Clearly $2$.

How many with middle term $4$? Clearly there are $3$.

Continue. Note that there are $6$ with middle term $7$, and then the numbers start decreasing.

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.