Number of three-term arithmetic progressions in [n]

Question

Three numbers are chosen at random between 1 and $n$ (say $n=500$).What will be the probability of those numbers to be in arithmetic progression?

I don't know how to count the number of favorable events. Sample space={(1,2,3),(4,5,6),(18,20,21)........} favorable events={(2,4,6),(8,12,16),(10,20,30),(50,100,150... and many more)} I can count the sample space but how do i count the favorable events. Some insight could help?

Answer 1

I have assumed that three randomly chosen numbers are distinct.

Let $d$ be the common difference of the arithmetic progression. Then it is easy to see that $d$ must take an integer value between $1$ and $249$ inclusive. So for any one of these $d$ values, let $a$ be the smallest of the trio in the arithmetic progression. Then we just have to count the number of distinct $a$s we can have for each $d$.

First let's consider $d=1$, then $a$ can be between $1$ and $498$.

For $d=2$, $a$ is between $1$ and $496$.

It quickly becomes evident that the range of values $a$ can take for any given $d$ is from the set $\{1, 2, \cdots , 500-2d\}$, and this is easily shown to be true since if $a$ is the smallest, then $a+2d$ is the largest of the trio and must not exceed $500$

So the number of different trio of APs we can form is: $$\sum_{i=1}^{249} (500-2i)$$ Can you determine this value? (Note that if three randomly chosen numbers can be the same, then the sum takes $i$ from $0$ not $1$, otherwise it should be the same).

Edit: I realized that $n=500$ is an example, and the asker wanted general $n$. In this case $d$ can take values between $1$ (or $0$ if non distinct integers are picked) and $\lfloor{\frac{n-1}{2}}\rfloor$.

In this case we get $$\sum_{i=1}^{\lfloor{\frac{n-1}{2}}\rfloor}n-2i$$

Answer 2

Counting favorable samples: $(1,1+k,1+2k)$ is favorable. So are $(2,2+k,2+2k),...,(n-2k,n-k,n)$. For an increment of $k$, there are $n-2k$ such combinations. The increment can take all values from 1 to $\lfloor \frac{n-1}{2} \rfloor$ where the brackets indicate "floor", i.e., $\frac{n-1}{2}$ if n is odd and $\frac{n-2}{2}$ if $n$ is even. Total number of favorable combinations is $$\sum_{k=1}^{\lfloor \frac{n-1}{2} \rfloor}n-2k$$ which is easily summed as $\frac{n^2-2n+1}{4}$ if $n$ is odd and $\frac{n^2-2n}{4}$ if $n$ is even.

Answer 3

(Assuming three distinct numbers are chosen.)

A three-element arithmetic progress $a,b=a+k,c=a+2k$ with $k>0$ is entirely determined by $a,c$, and thus the number of them is equal to the number of ways of picking $a,c$ with the same parity (either both odd or both even.)

The number of odd numbers from $1$ to $n$ is $\lceil n/2\rceil$ and the number and the number of even numbers from $1$ to $n$ is $\lfloor n/2\rfloor$.

This means that the number of arithmetic progressions is:

$$\binom{\lfloor n/2\rfloor}{2}+\binom{\lceil n/2\rceil}{2}$$

When $n$ is even, this is $2\binom{n/2}{2}=\frac{n(n-2)}{4}$. When $n$ is odd, this is $\binom{(n-1)/2}{2}+\binom{(n+1)/2}2=\frac{(n-1)^2}{4}.$

Both cases can be written in one formula:

$$\left\lfloor\frac{(n-1)^2}{4}\right\rfloor$$

When $n>2$ is even, the probability is:

$$\dfrac{\frac{n(n-2)}{4}}{\frac{n(n-1)(n-2)}{6}}=\frac{3}{2(n-1)}$$

When $n>1$ is odd:

$$\frac{3(n-1)}{2n(n-2)}$$

---

Another way to count the pairs of the same parity which might be easier is to count all pairs and then subtract the pairs, one odd, the other even. This gives:

$$\binom n2-\left\lfloor\frac n2\right\rfloor \left\lceil \frac n2\right\rceil$$

Answer 4

Here's another approach.

The number of ways of selecting $3$ numbers from $n$ is $N=\binom n3=\frac 16 n(n-1)(n-2)$.

For any $3$ numbers to be in AP, they must be successively equidistant.

Let $f(s)$ be the number of equidistant triplets including $s$ itself, which can be formed from the first $s$ positive integers.

Counting backwards from $s$, it can be easily established that $$f(2r-1)=f(2r)=r-1$$

The total number of equidistant triplets which can be formed from the first $n$ integers (both including and excluding $n$ itself) is $$S_n=\sum_{r=3}^n f(r)$$ For even $n$,
e.g. $n=2m$ (i.e.$m=\frac n2$),

$$\begin{align} S&=\sum_{r=3}^{2m}f(r)\\ &=\sum_{r=2}^m\underbrace{f(2r-1)}_{r-1}+\underbrace{f(2r)}_{r-1}\\ &=2\sum_{r=2}^m(r-1)\color{lightgrey}{=2\sum_{r=1}^{m-1}r=2\binom m2}\\ &=m(m-1)\color{lightgrey}{=\frac n2\left(\frac n2-1\right)}\\ &=\frac 14{n(n-2)}\end{align}$$

Probability of selecting $3$ numbers which are in AP is $$\frac SN=\frac{\frac 14n(n-2)}{\frac 16n(n-1)(n-2)}=\color{red}{\frac 3{2(n-1)}}$$

For odd $n$,
e.g. $n=2m-1$ (i.e.$m=\frac {n+1}2$),

$$\begin{align} S&=\sum_{r=3}^{2m-1}f(r)\\ &=\left(\sum_{r=3}^{2m}f(r)\right)-\underbrace{f(2m)}_{m-1}\\ &=\frac 14(n+1)(n-1)-\left(\frac {n+1}2-1\right)\\ &=\frac 14{(n-1)^2} \end{align}$$

Probability of selecting $3$ numbers which are in AP is $$\frac SN=\frac{\frac 14(n-1)^2}{\frac 16n(n-1)(n-2)}=\color{red}{\frac {3(n-1)}{2n(n-2)}}$$