How such A.P subsets are there???

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


Viewing 2 posts - 1 through 2 (of 2 total)
  • Author
  • #27966
    swastik pramanik

    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).

    Camellia Ray

    In 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

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

    Now c.d 1 and c.d 11 only 1 subset; c.d 2 &10 ->2 subsets


    For N Odd

    1. 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)


    SAME as previous just one more term n/2 added

    so here it is 2×(1+2+….(n−1)/2)+n/2

Viewing 2 posts - 1 through 2 (of 2 total)
  • You must be logged in to reply to this topic.