Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 15"
(→Solution) |
|||
(9 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | 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== | ||
+ | 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> | ||
+ | ---- | ||
+ | |||
+ | *[[Mock AIME 1 2006-2007 Problems/Problem 14 | Previous Problem]] | ||
+ | |||
+ | *[[Mock AIME 1 2006-2007]] |
Latest revision as of 13: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.