7
$\begingroup$

How many Arithmetic Progressions having $3$ terms can be made from integers $1$ to $n$? The numbers in the AP must be distinct.

For example if $n=6$ then number of AP's possible are $6$

  • $1,2,3$
  • $2,3,4$
  • $3,4,5$
  • $4,5,6$
  • $2,4,6$
$\endgroup$
  • $\begingroup$ Note, you don't specifically say that the three numbers are distinct. $1,1,1$ is an arithmetic progression... $\endgroup$ – Thomas Andrews Dec 1 '12 at 18:56
  • 1
    $\begingroup$ Yeah I missed that. The numbers are essentially distinct in this question. $\endgroup$ – PRYM Dec 2 '12 at 18:32
  • $\begingroup$ What about 5,3,1? $\endgroup$ – user14972 Dec 2 '12 at 18:35
  • $\begingroup$ @Hurkyl it is valid. We will just multiply the answer by 2 as only distinct numbers are allowed $\endgroup$ – PRYM Dec 19 '12 at 18:17
8
$\begingroup$

One can select any tow distinct elements of the same parity. Together with their mean, they make such a progression.

There are $\left\lfloor \frac n2\right\rfloor$ even numbers $\le n$ and $\left\lfloor \frac{n+1}2\right\rfloor$ odd numbers. Since we need to select unordered pairs (or ordered? But you seem not to distinguish between 1,2,3 and 3,2,1), the total number is $$ f(n) = {\left\lfloor \frac n2\right\rfloor\choose 2}+{\left\lfloor \frac {n+1}2\right\rfloor\choose 2}.$$ If $n=2m$ is even, this amounts to $$ f(n) = 2{m\choose 2}=m(m-1)$$ and if $n=2m+1$ is odd, to $$ f(n) = {m\choose 2}+{m+1\choose 2} = m^2.$$ Both may also be summarized as $$ f(n) = \left\lfloor\frac n2\right\rfloor\cdot\left\lfloor\frac{n-1}2\right\rfloor.$$

Example: Letting $n=6$, we obtain $f(n)=\left\lfloor\frac 62\right\rfloor\cdot\left\lfloor\frac52\right\rfloor=3\cdot 2=6$.

$\endgroup$
3
$\begingroup$

Let the three term AP be $a,a+d,a+2d$ where $a,d$ are natural numbers.

So, $a\ge1$ and $a+2d\le n\implies 1\le a\le n-2d \implies d\le \frac{n-1}2$

If $d=1,a$ can assume $1,2,\cdots, n-2$ i.e., $n-2$ values.

If $d=2,a$ can assume $1,2,\cdots, n-4$ i.e., $n-4$ values.

If $n$ is even, $d_{max}=\frac{n-2}2$

for $d=\frac {n-2}2,1\le a\le 2$ i.e., $a$ has 2 values.

If $n$ is even, the number of AP is $(n-2)+(n-4)+\cdots+2=\frac{(n-2)}4(2+n-2)=\frac{n(n-2)}4$

If $n$ is odd, $d_{max}=\frac{n-1}2$

So, in that case the number of AP will be $1+3+\cdots+(n-4)+(n-2)=\frac{(n-1)^2}4$

$\endgroup$
  • 1
    $\begingroup$ the way I have solved this question gives me the wrong answer: For even- choose 2 elements first from n/2 elements, then the third element can be found by adding the difference of the first 2 numbers. This gives: $\binom{n/2}{2}$ which i hlf the answer you get. Why is my method wrong? $\endgroup$ – oshhh Mar 5 '17 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.