Problem:
Let K be the number of sequences A1,A2,…,An such that n is a positive integer less than or equal to 10 , each Ai is a subset of {1,2,3,…,10}, and Ai−1 is a subset of Ai for each i between 2 and n, inclusive. For example, {},{5,7},{2,5,7},{2,5,7},{2,5,6,7,9} is one such sequence, with n=5. What is the remainder when K is divided by 10?
Answer Choices:
A. 1
B. 3
C. 5
D. 7
E. 9
Solution:
Such a sequence can be described by a value of n together with a function f from {1,2,3,…,10} to {1,2,…,n,n+1} such that f(j) is the least i such that j∈Ai if j∈An and f(j)=n+1 if j∈/An. The number of such functions is (n+1)10, because there are n+1 choices for where to send each element of the domain. Therefore K=210+310+410+⋯+1110. It remains to determine the remainders when each of the terms in this sum is divided by 10.
- Powers of 2: The remainders of powers of 2 have the pattern 2,4,8,6,2,4,8,6,2,4, so 210 contributes 4 to the sum.
- Powers of 3: The remainders of powers of 3 have the pattern 3,9,7,1,3,9,7,1,3,9, so 310 contributes 9 .
- Powers of 4: The remainders of powers of 4 have the pattern 4,6,4,6,4,6,4,6,4,6, so 410 contributes 6 .
- Powers of 5: All powers of 5 have remainder 5 .
- Powers of 6: All powers of 6 have remainder 6 .
- Powers of 7: The remainders of powers of 7 have the pattern 7,9,3,1,7,9,3,1,7,9, so 710 contributes 9 .
- Powers of 8: The remainders of powers of 8 have the pattern 8,4,2,6,8,4,2,6,8,4, so 810 contributes 4 .
- Powers of 9: The remainders of powers of 9 are alternately 9 and 1 , so that term contributes 1 .
Finally, 1010 contributes 0 and 1110 contributes 1 . Therefore the remainder when K is divided by 10 is the same as the remainder when 4+9+6+5+6+9+4+1+0+1=45 is divided by 10 , namely (C)5 .
OR
As above, it suffices to compute the remainder when 210+310+410+⋯+1110 is divided by 10 . Note that m10≡m2(mod10) for all m. Then modulo 10 ,\
K=210+310+⋯+1110≡22+32+⋯+112=611⋅(11+1)⋅(2⋅11+1)−1=505≡(C)5.
Note: In fact, K=40,851,766,525.
The problems on this page are the property of the MAA's American Mathematics Competitions