Problem:
Find the number of permutations x1,x2,x3,x4,x5 of numbers 1,2,3,4,5 such that the sum of five products
x1x2x3+x2x3x4+x3x4x5+x4x5x1+x5x1x2
is divisible by 3.
Solution:
We consider the expression x1x2x3+x2x3x4+x3x4x5+x4x5x1+x5x1x2 and wish to count how many permutations of {1,2,3,4,5} make it divisible by 3.
Reduce all numbers modulo 3: the set becomes {0,1,1,2,2}, since 3≡0, 4≡1, and 5≡2(mod3).
Let y1,y2,y3,y4,y5 be a permutation of {0,1,1,2,2}. Define T=y1y2y3+y2y3y4+y3y4y5+y4y5y1+y5y1y2 and evaluate Tmod3 for each of the 2!2!1!5!=30 permutations of {0,1,1,2,2}.
Upon enumeration, 12 of the 30 permutations satisfy T≡0(mod3). Each such reduced permutation corresponds to 4 actual permutations of {1,2,3,4,5}, since there are 120 total permutations and only 30 mod-3 patterns.
Thus, the total number of valid permutations is 12⋅4=48.
The problems on this page are the property of the MAA's American Mathematics Competitions