Mock AIME 1 2006-2007 Problems/Problem 15
Let be the set of integers . An element (in) is chosen at random. Let denote the sum of the digits of . The probability that is divisible by 11 is where and are relatively prime positive integers. Compute the last 3 digits of
First of all, note that there can be at most 11 digits. Let become . Where will be partitioned into different sections (using dividers) such that each section represents a digit. There are = possibilities... but this includes having or more 's in one section (Which means that it considers to be a digit). Thus, we need to subtract off the invalid "numbers" for the overcount. We count these in cases:
If there are 's, there will only be one left over. Let denote the group of 's. We want to find the number of possible arrangements of such that is not next to the . Let B denote (or where is next to ). NOTE: times the number of arrangements of is the actual number of arrangements in which is next to . There are .
If there are 's, let C denote all 's grouped together. Finding the number of arrangements of .
Since there are a total of numbers in S, the probability that the sum of the digits of is equal to . Since the denominator has as the last three digits. The answer is just the last three digits of the numerator.