# Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 15"

(→Solution) |
|||

Line 2: | Line 2: | ||

Let <math>S</math> be the set of integers <math>0,1,2,...,10^{11}-1</math>. An element <math>x\in S</math> (in) is chosen at random. Let <math>\star (x)</math> denote the sum of the digits of <math>x</math>. The probability that <math>\star(x)</math> is divisible by 11 is <math>\frac{m}{n}</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Compute the last 3 digits of <math>m+n</math> | Let <math>S</math> be the set of integers <math>0,1,2,...,10^{11}-1</math>. An element <math>x\in S</math> (in) is chosen at random. Let <math>\star (x)</math> denote the sum of the digits of <math>x</math>. The probability that <math>\star(x)</math> is divisible by 11 is <math>\frac{m}{n}</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Compute the last 3 digits of <math>m+n</math> | ||

==Solution== | ==Solution== | ||

− | {{ | + | First of all, note that there can be at most 11 digits. Let <math>11</math> become <math>11111111111||||||||||</math>. Where <math>11</math> will be partitioned into <math>11</math> different sections (using <math>10</math> dividers) such that each section represents a digit. There are <math>\frac{21!}{11! \cdot 10!}</math> = <math>352716</math> possibilities... but this includes having <math>10</math> or more <math>1</math>'s in one section (Which means that it considers <math>10</math> to be a digit). Thus, we need to subtract off the invalid "numbers" for the overcount. We count these in cases: |

+ | If there are <math>10</math> <math>1</math>'s, there will only be one <math>1</math> left over. Let <math>A</math> denote the group of <math>10</math> <math>1</math>'s. We want to find the number of possible arrangements of <math>A1||||||||||</math> such that <math>A</math> is not next to the <math>1</math>. Let B denote <math>A1</math> (or where <math>A</math> is next to <math>1</math>). NOTE: <math>2</math> times the number of arrangements of <math>B||||||||||</math> is the actual number of arrangements in which <math>A</math> is next to <math>1</math>. There are <math>\frac{12!}{10!}</math> <math>-</math> <math>2 \cdot \frac{11!}{10!}</math> <math>=</math> <math>\frac{12! - 2 \cdot 11!}{10!}</math> <math>=</math> <math>\frac{10 \cdot 11!}{10}</math> <math>=</math> <math>110</math>. | ||

+ | |||

+ | |||

+ | If there are <math>11</math> <math>1</math>'s, let C denote all <math>11</math> <math>1</math>'s grouped together. Finding the number of arrangements of <math>C||||||||||</math> <math>=</math> <math>\frac{11!}{10!}</math> <math>=</math> <math>11</math>. | ||

+ | |||

+ | |||

+ | Since there are a total of <math>10^{11}</math> numbers in S, the probability that the sum of the digits of <math>x</math> is equal to <math>\frac{\frac{21!}{11! \cdot 10!} - 110 - 11}{10^{11}}</math> <math>=</math> <math>\frac{352595}{10^{11}}</math> <math>=</math> <math>\frac{70519}{2 \cdot 10^{10}}</math>. Since the denominator has <math>000</math> as the last three digits. The answer is just the last three digits of the numerator. <math>\boxed{519}</math> | ||

---- | ---- | ||

## Latest revision as of 12:45, 19 February 2016

## Problem

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

## Solution

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.