Home › Forums › Math Olympiad, I.S.I., C.M.I. Entrance › How such A.P subsets are there???

Tagged: Combinatorics

- This topic has 1 reply, 2 voices, and was last updated 1 year ago by Camellia Ray.

- AuthorPosts
- May 26, 2019 at 6:45 pm #27966swastik pramanikParticipant
Let \(S=\{1, 2,3,\cdots, n\}\). Find the number of subsets \(A\) of \(S\) satisfying the following conditions:

- \(A=\{a, a+d, \cdots, a+kd\}\) for some positive integers \(a, d, k\), and
- \(A\cup \{x\} \) is no longer an A.P with common difference \(d\) for each \(x\in S\backslash A\).

(Note that \(|A|\geq 2\) and any sequence of two terms is considered as an A.P).

- This topic was modified 1 year ago by swastik pramanik.

May 27, 2019 at 7:23 am #28159Camellia RayParticipantIn the given question it has been asked to find the no of subsets which satisfy the condition that

A={a, a+d,a+2d….a+kd} &A U{x} is no longer an A.P where x ∈ (S-A)

From above 2 condns it can b concluded that at a time with c.d d we have to form the largest sequence having c.d d and starting element say a

For ex if X={1,2,3,,,,12} then for

only 1 subset possible;**c.d 1:**subset possible namely { 1,3,5,7,,,11} & {2,4,6,8,,,,12}*c.d 2 ->2*:Now

**c.d 1 and c.d 11**only**1**subset;**c.d 2 &10 ->2**subsetsGENERALIZATION

**For N Odd**- c.d 1 & n-1 -> 1 subset; 2. c.d 2 & n-2 -> 2 subsets

similarly for c.d (n-1)/2) & cd (n+1)/(2) it will be (n-1)/2 subsets

SO TOTAL IS

**2× (1+2+3+…..+(n-1)/2)****FOR EVEN**SAME as previous just one more term n/2 added

so here it is

**2×(1+2+….(n−1)/2)+n/2**- This reply was modified 1 year ago by Camellia Ray.
- This reply was modified 1 year ago by Camellia Ray.
- This reply was modified 1 year ago by Camellia Ray.
- This reply was modified 1 year ago by Camellia Ray.
- This reply was modified 1 year ago by Camellia Ray.

- AuthorPosts

- You must be logged in to reply to this topic.