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 "2004 AIME II Problems/Problem 10"
(→‎Solution)
Line 2: Line 2:
 
Let <math> S </math> be the [[set]] of [[integer]]s between <math>1</math> and <math> 2^{40} </math> whose binary expansions have exactly two <math>1</math>'s. If a number is chosen at random from <math> S, </math> the [[probability]] that it is divisible by <math>9</math> is <math> p/q, </math> where <math> p </math> and <math> q </math> are relatively prime positive integers. Find <math> p+q. </math>
 
Let <math> S </math> be the [[set]] of [[integer]]s between <math>1</math> and <math> 2^{40} </math> whose binary expansions have exactly two <math>1</math>'s. If a number is chosen at random from <math> S, </math> the [[probability]] that it is divisible by <math>9</math> is <math> p/q, </math> where <math> p </math> and <math> q </math> are relatively prime positive integers. Find <math> p+q. </math>
  
−
== Solution ==
+
== Solution 1==
 
A positive integer <math>n</math> has exactly two 1s in its [[binary representation]] exactly when <math>n = 2^j + 2^k</math> for <math>j \neq k</math> [[nonnegative]] integers.  Thus, the [[set]] <math>S</math> is equal to the set <math>\{n \in \mathbb{Z} \mid n = 2^j + 2^k \,\mathrm{ and }\, 0 \leq j < k \leq 39\}</math>.  (The second condition ensures simultaneously that <math>j \neq k</math> and that each such number less than <math>2^{40}</math> is counted exactly once.)  This means there are <math>{40 \choose 2} = 780</math> total such numbers.
 
A positive integer <math>n</math> has exactly two 1s in its [[binary representation]] exactly when <math>n = 2^j + 2^k</math> for <math>j \neq k</math> [[nonnegative]] integers.  Thus, the [[set]] <math>S</math> is equal to the set <math>\{n \in \mathbb{Z} \mid n = 2^j + 2^k \,\mathrm{ and }\, 0 \leq j < k \leq 39\}</math>.  (The second condition ensures simultaneously that <math>j \neq k</math> and that each such number less than <math>2^{40}</math> is counted exactly once.)  This means there are <math>{40 \choose 2} = 780</math> total such numbers.
  
Line 10: Line 10:
  
 
The probability is <math>\frac{133}{780}</math>, and the answer is <math>133 + 780 = \boxed{913}</math>.
 
The probability is <math>\frac{133}{780}</math>, and the answer is <math>133 + 780 = \boxed{913}</math>.
 +
 +
== Solution 2==
 +
Note that <math>2^3 \equiv -1\text{ (mod 9)}</math>. Since <math>2^6 = 64 \equiv 1\text{ (mod 9)}</math>, multiplying by <math>2^6</math> gives <math>2^{3+6n} \equiv -1\text{ (mod 9)}</math>.
 +
 +
The solutions that work are in the form <math>2^a+2^b</math>. Since <math>2^{3+6n}+1 \equiv 0\text{ (mod 9)}</math>, all of the solutions are in this form or this form multiplied by <math>2^x</math> where <math>0 \leq 3+6n+x \leq 39</math>.
 +
 +
Now we just do casework:
 +
<cmath>2^3+1: 2^0 \text{ to } 2^36</cmath>
 +
<cmath>2^9+1: 2^0 \text{ to } 2^30</cmath>
 +
<cmath>2^{15}+1: 2^0 \text{ to } 2^24</cmath>
 +
<cmath>2^{21}+1: 2^0 \text{ to } 2^18</cmath>
 +
<cmath>2^{27}+1: 2^0 \text{ to } 2^12</cmath>
 +
<cmath>2^{33}+1: 2^0 \text{ to } 2^6</cmath>
 +
<cmath>2^{39}+1: 2^0</cmath>
 +
 +
So, the numerator is <math>37+31+25+19+13+7+1 = 133</math>. The denominator is just <math>{40 \choose 2}</math>, so the probability is <math>\frac{133}{780}</math>, and the answer is <math>133 + 780 = \boxed{913}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 02:07, 11 March 2015

Problem

Let $S$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$'s. If a number is chosen at random from $S,$ the probability that it is divisible by $9$ is $p/q,$ where $p$ and $q$ are relatively prime positive integers. Find $p+q.$

Solution 1

A positive integer $n$ has exactly two 1s in its binary representation exactly when $n = 2^j + 2^k$ for $j \neq k$ nonnegative integers. Thus, the set $S$ is equal to the set $\{n \in \mathbb{Z} \mid n = 2^j + 2^k \,\mathrm{ and }\, 0 \leq j < k \leq 39\}$. (The second condition ensures simultaneously that $j \neq k$ and that each such number less than $2^{40}$ is counted exactly once.) This means there are ${40 \choose 2} = 780$ total such numbers.

Now, consider the powers of $2$ mod $9$: $2^{6n} \equiv 1, 2^{6n + 1} \equiv 2, 2^{6n + 2} \equiv 4, 2^{6n + 3} \equiv 8 \equiv -1,$ $2^{6n + 4} \equiv 7 \equiv -2,$ $2^{6n + 5} \equiv 5 \equiv -4 \pmod 9$.

It's clear what the pairs $j, k$ can look like. If one is of the form $6n$ (7 choices), the other must be of the form $6n + 3$ (7 choices). If one is of the form $6n + 1$ (7 choices) the other must be of the form $6n + 4$ (6 choices). And if one is of the form $6n + 2$ (7 choices), the other must be of the form $6n + 5$ (6 choices). This means that there are $7\cdot 7 + 7\cdot 6 + 7\cdot 6 = 49 + 42 +42 = 133$ total "good" numbers.

The probability is $\frac{133}{780}$, and the answer is $133 + 780 = \boxed{913}$.

Solution 2

Note that $2^3 \equiv -1\text{ (mod 9)}$. Since $2^6 = 64 \equiv 1\text{ (mod 9)}$, multiplying by $2^6$ gives $2^{3+6n} \equiv -1\text{ (mod 9)}$.

The solutions that work are in the form $2^a+2^b$. Since $2^{3+6n}+1 \equiv 0\text{ (mod 9)}$, all of the solutions are in this form or this form multiplied by $2^x$ where $0 \leq 3+6n+x \leq 39$.

Now we just do casework: \[2^3+1: 2^0 \text{ to } 2^36\] \[2^9+1: 2^0 \text{ to } 2^30\] \[2^{15}+1: 2^0 \text{ to } 2^24\] \[2^{21}+1: 2^0 \text{ to } 2^18\] \[2^{27}+1: 2^0 \text{ to } 2^12\] \[2^{33}+1: 2^0 \text{ to } 2^6\] \[2^{39}+1: 2^0\]

So, the numerator is $37+31+25+19+13+7+1 = 133$. The denominator is just ${40 \choose 2}$, so the probability is $\frac{133}{780}$, and the answer is $133 + 780 = \boxed{913}$.

See also

2004 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_10&oldid=68740"