Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
(→‎Solution)
 
(6 intermediate revisions by 2 users not shown)
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==
−
{{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/Problem 14 | Previous Problem]]
+
*[[Mock AIME 1 2006-2007 Problems/Problem 14 | Previous Problem]]
  
 
*[[Mock AIME 1 2006-2007]]
 
*[[Mock AIME 1 2006-2007]]
−
 
−
Counting all <math>2</math>, <math>3</math>, and <math>4</math> digit combinations and then permuting only those up to <math>2045</math>, we find that there are 186 numbers whose sums are either <math>11</math> or <math>22</math>. We need not account for the sum 33, as it is not achievable with a <math>2</math> as the lowest digit. Since there are a total of <math>2048</math> numbers and <math>186</math> that work, we get <math>186/2048</math> or <math>93/1024</math>. Our sum is then <math>93 + 1024 = 1117</math>. The last three digits are <math>117</math>.
 

Latest revision as of 12:45, 19 February 2016

Problem

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

Solution

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


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


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


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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_15&oldid=76460"