Number of Ordered Triples – Duke Math Meet 2009 Problem 7

Try this problem from Duke Math Meet 2009 Problem 7 based on the number of ordered triples. This problem was asked in the team round.

How many ordered triples of integers (a, b, c) are there such that $ 1 \le a, b, c \le 70 $ and $ a^2 + b^2 + c^2 $ is divisible by 28.

Any square quantity is 0 or 1 modulo 4

Now the sum of three square quantities is 0 or 1 mod 4. Since 28 is 0 mod 4, therefore none of the three squares can be 1 mod 4.

Thus a, b, c are even.

Again a square quantity is always 0, 1, 4, 2 mod 7

Since we want the three squares to add up to 0 mod 7 (28 is 0 mod 7), the possibilities are (0, 0, 0) mod 7 and (1, 4, 2) mod 7

So we have the following cases:

Case 1

a, b, c are all even multiples of 7. There are 5 of them. Since we are looking for ordered triplet there are $latex 5^3 = 125 $ of these$

Case 2

a, b, c are all even numbers. with 1, 6 mod 7, 2, 5 mod 7 and 3, 4 mod 7

1 mod 7 - 10 elements
6 mod 7 - 10 elements

Hence there are 20 numbers which are 1 or 6 mod 7. 10 of these are even.

Similarly, there are 20 numbers which are 2 or 5 mod 7 and 20 numbers which are 3 or 4 mod 7. Half of each of which we will take.

So 10 choices for each set. $ 10^3 = 1000$ choices. Now since we are taking ordered pairs, we must consider all the $ 3! = 6 $ permutations. So there are 6000 cases.

Hence answer is $ 6000 + 125 = 6125 $

Some Useful Links:

• Duke Math Meet 2009 Problem 9
• Our Math Olympiad Program
• AM-GM Inequality – Video