smc

Question

Let K be the number of sequences A_1, A_2, , A_n such that n is a positive integer less than or equal to 10, each A_i is a subset of 1, 2, 3, , 10, and A_i-1 is a subset of A_i 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?

Accepted Answer

Consider any sequence with n terms. Every 10 number has such choices: never appear, appear the first time in the first spot, appear the first time in the second spot… and appear the first time in the nth spot, which means every number has (n+1) choices to show up in the sequence. Consequently, for each sequence with length n, there are (n+1)^10 possible ways. Thus, the desired value is _i=1^10(i+1)^10 510