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

Mock AIME 1 2006-2007 Problems/Problem 15

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"