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???

Tagged: 

This topic contains 1 reply, has 2 voices, and was last updated by  Camellia Ray 2 months, 4 weeks ago.

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

    swastik pramanik
    Participant

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

    #28159

    Camellia Ray
    Participant

    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

    GENERALIZATION

    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)

    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 2 months, 4 weeks ago by  Camellia Ray.
    • This reply was modified 2 months, 4 weeks ago by  Camellia Ray.
    • This reply was modified 2 months, 4 weeks ago by  Camellia Ray.
    • This reply was modified 2 months, 4 weeks ago by  Camellia Ray.
    • This reply was modified 2 months, 4 weeks ago by  Camellia Ray.
Viewing 2 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic.