Results 1 to 2 of 2

Math Help - Maths Problem Counting Techniques?

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    Maths Problem Counting Techniques?

    What is the maximumsize of a subset, P, of {1, 2, 3, . . . , 50}
    with the property that no pair of distinct elements of P
    has a sum divisible by 7?
    (A) 21 (B) 22 (C) 23 (D) 24 (E) 25

    How do I solve it?
    Can u guys show me the steps?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Counting problem

    Hello paul14
    Quote Originally Posted by paul14 View Post
    What is the maximumsize of a subset, P, of {1, 2, 3, . . . , 50}
    with the property that no pair of distinct elements of P
    has a sum divisible by 7?
    (A) 21 (B) 22 (C) 23 (D) 24 (E) 25

    How do I solve it?
    Can u guys show me the steps?
    Welcome to Math Help Forum!

    I reckon the answer is 23. Here's my reasoning.

    Consider the partition of P into sets A_i, i = 0, 1, 2,...6 as follows: A_i = \{n:n=i \mod 7\}

    So, for example, A_0 = \{7, 14, ..., 49\}, A_1 = \{1, 8, ..., 50\}, etc

    Then |A_i| = 7, i = 0, 2, 3,4,5, 6 and |A_1| = 8

    Now if we choose an n \in A_i to be in our subset , then we must not choose an m \in A_{7-i}, for then n + m = 0\mod 7

    Thus the subset can contain at most 1 element from A_0, 8 elements from A_1, and then 7 elements from any two of the remaining A_i, in such a way that no two of the i's add up to 7.

    Total: 1 + 8 + 7 + 7 = 23

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting Techniques.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 24th 2009, 03:14 PM
  2. Probability Probelms & Counting Techniques
    Posted in the Statistics Forum
    Replies: 11
    Last Post: June 10th 2008, 08:03 PM
  3. Probability Probelms & Counting Techniques
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 10th 2008, 04:58 PM
  4. Data Help!!! Counting Techniques
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 3rd 2008, 03:33 PM
  5. probability problem counting techniques.
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: September 27th 2007, 07:50 AM

Search Tags


/mathhelpforum @mathhelpforum