practice problems

Q1. Let X = {1,2,...,n}). In how many ways can you choose (r) elements from (X) such that no two chosen elements are consecutive, where 0 <= r <= (n+1)/2.
S1.
Answer: (n-r+1)c(r)
Solution here.

Q2. In how many ways can three numbers in arithmetic progression (A.P.) be selected from the set (1,2...n)?
S2.
Method 1:
a,b,c in A.P. => a,c are both even or both odd.
b = (a+c)/2

So if we pick 2 even or 2 odd numbers, we will find a number between them to complete the A.P.

Case 1:
n is even.
n = 2m.
m odd and m even numbers.
Pick 2 even: mC2
Pick 2 odd: mC2
Total: 2 * mC2 = m(m-1) = n/2(n/2-1) = n(n-2)/4

Case 2:
n = 2m+1
m+1 odd and m even numbers.
Total ways: (m+1)C2 + mC2
= 1/2[m.(m+1) + m.(m-1)] = m/2[2m] = m^2 = (n-1)^2/4

Method 2:
When n is even:
You can pick an A.P. with d = 1 as 1,2,3 2,3,4 .... n-2,n-1,n
d = 1 => n-2 ways to pick the first term
d = 2 => 1,3,5 2,4,6 ... n-4,n-2,n => n-4 ways
....
For e.g. n=6, max d = 2(1,3,5 2,4,6)
n = 8, max d = 3(1,4,7 2,5,8)
n = 10, max d = 4(1,5,9 2,6,10)
So max d = (n-2)/2 and there will be 2 A.P.s for that.

So total possible A.P.s
= 2 + 4 ... + n-2
= N/2[2 + n - 2] and N = (n-2)/2
= (n-2).n/4

When n is odd:
d = 1 => n-2 ways
For e.g. n =5 then first term can be 1,2,3
d = 2 => 1,3,5 => n-4 =1 ways
So here number of ways will be:
1 + 3 ... + n-2
Nth term = n-2 = 1 + (N-1).2 => n-2 = 2N-1 => 2N = n-1 => N = (n-1)/2
=> sum = (n-1)/4[1+n-2] = [(n-1)/2]^2