Problem:
For nonnegative integers a and b with a+b≤6, let T(a,b)=(a6​)(b6​)(a+b6​). Let S denote the sum of all T(a,b), where a and b are nonnegative integers with a+b≤6. Find the remainder when S is divided by 1000.
Solution:
It follows from
(6a+b​)=(66−(a+b)​)
that
S=a+b≤6∑​(6a​)(6b​)(66−(a+b)​)=a+b+c=6∑​(6a​)(6b​)(6c​)
For given values of a,b, and c, the term (a6​)(b6​)(a+b6​) corresponds to the number of choices when selecting a elements from {1,2,3,4,5,6},b elements from {7,8,9,10,11,12}, and c elements from {13,14,15,16,17,18}. Thus S is equal to the number of 6-element subsets of {1,2,3,…,18}, namely (618​)=18,564. The requested remainder is 564​.
The problems on this page are the property of the MAA's American Mathematics Competitions