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"

 
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
 +
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]] [[integer]]s.  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.
  
 +
Now, consider the powers of 2 [[modular arithmetic | mod]] 9: <math>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</math>. 
 +
 +
It's clear what the pairs <math>j, k</math> can look like.  If one is of the form <math>6n</math> (7 choices), the other must be of the form <math>6n + 3</math> (7 choices).  If one is of the form <math>6n + 1</math> (7 choices) the other must be of the form <math>6n + 4</math> (6 choices).  And if one is of the form <math>6n + 2</math> (7 choices), the other must be of the form <math>6n + 5</math> (6 choices).  This means that there are <math>7\cdot 7 + 7\cdot 6 + 7\cdot 6 = 49 + 42 +42 = 133</math> total "good" numbers.
 +
 +
So our [[probability]] is <math>\frac{133}{780}</math> and our answer is <math>133 + 780 = 913</math>.
 
== See also ==
 
== See also ==
 
* [[2004 AIME II Problems]]
 
* [[2004 AIME II Problems]]
 +
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 11:38, 4 August 2006

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

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.

So our probability is $\frac{133}{780}$ and our answer is $133 + 780 = 913$.

See also

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