Three distinct numbers a, b and c are chosen randomly without replacement from the set 1, 2, 3, , 10 . If the probability that the sum of their squares a^2 + b^2 + c^2 is divisible by 3 is p q , where (p, q) = 1 , then p + q is equal to ________

Step-by-step solution

For any integer x , its square x^2 is congruent to either 0 or 1 modulo 3 . Specifically: If x is a multiple of 3 , x^2 0 3 . If x is not a multiple of 3 , x^2 1 3 . In the given set 1, 2, 3, , 10 : There are 3 multiples of 3 (which are 3, 6, 9 ). There are 7 non-multiples of 3 (which are 1, 2, 4, 5, 7, 8, 10 ). We require a^2 + b^2 + c^2 0 3 . Since each square leaves a remainder of 0 or 1 when divided by 3 , their sum can be a multiple of 3 if and only if: Case 1: All three squares leave a remainder of 0 . Case 2