# Math Help - Maths Problem Counting Techniques?

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?

2. ## Counting problem

Hello paul14
Originally Posted by paul14
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$