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 3 (modular arithmetic))
(→‎Solution 4)
 
(24 intermediate revisions by 4 users not shown)
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 1==
+
== Solution 1 (Rigorous)==
−
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.
 
  
−
Now, consider the powers of <math>2</math> [[modular arithmetic | mod]] <math>9</math>: <math>2^{6n} \equiv 1, 2^{6n + 1} \equiv 2, 2^{6n + 2} \equiv 4, 2^{6n + 3} \equiv 8 \equiv -1,</math> <math> 2^{6n + 4} \equiv 7 \equiv -2,</math> <math> 2^{6n + 5} \equiv 5 \equiv -4 \pmod 9</math>.
+
Any number from 1 to <math>2^{40}</math> can be represented in binary with 40 digits (because <math>2^{40}</math> has 41) with leading zeroes if necessary. Therefore the number of sets where there are exactly two 1’s in this binary representation is just <math>\binom {40}{2}</math> because we’re choosing 2 1s to go in 40 digit slots. This is equal to 780; we have found <math>q</math>, our denominator.
 +
 
 +
With these particular numbers, when converting back to decimal note that the 38 zeroes all cancel out. Let the first 1 when reading the number in binary from left to right be in position <math>y</math>, I.e. when converting to decimal, it will have value <math>2^{y}</math>. Similarly, let the second 1 have position <math>x</math> (note <math>x<y</math>); then the decimal value of that 1 will be <math>2^{x}</math>. For example, with the binary string 0001001000 <math>y</math> is 6 and <math>x</math> is 3 (note that it is zero indexed).
 +
 
 +
It should also be noted that our constraints on <math>x</math> and <math>y</math> are <math>0 \leq x < y < 40</math> and <math>x, y \in \mathbb{Z}</math>.
 +
 
 +
The numbers that satisfy the constraints are therefore equal to <math>2^{x}+2^{y} = 2^{x} \cdot (1+2^{y-x})</math>. The conditions say that this is divisible by 9. <math>2^{x}</math> is clearly never divisible by 9, so we can just focus on <math>1+2^{y-x}</math>.
 +
<cmath>1+2^{y-x} \equiv 0 \pmod 9 \implies 2^{y-x} \equiv -1 \pmod 9 \implies 2^{y-x} \equiv 8 \pmod 9</cmath>
 +
 
 +
<math>y-x = 3</math> clearly satisfies the congruence, but are there any more? Well, we see that any time we raise -1 (in the second congruence above) to an odd power we get -1 again, so if we raise <math>2^{3}</math>, which we know already works, to an odd power, we will also satisfy the congruence. Thus, <math>2^{3}, 2^{9}, 2^{15},</math> etc. work; or, <cmath>y-x \equiv 3 \pmod 6</cmath>
 +
 
 +
To count the numbers that satisfy the condition, we need to find the amount of numbers that satisfy <math>2^{x} \cdot (1+2^{y-x}) \leq 2^{40}</math>, and <math>y-x \equiv 3 \pmod 6 = 6n +3</math> for some whole number <math>n</math>.
 +
 
 +
Since we know <math>1+2^{y-x} = 1+2^{6n+3}</math> is positive, we can divide both sides of the inequality by it;
 +
<cmath>2^{x} \cdot (1+2^{y-x}) \leq 2^{40} \implies 2^{x} \leq \frac{2^{40}}{1+2^{y-x}} \implies 2^{x} \leq \frac{2^{40}}{1+2^{6n+3}}</cmath>
 +
<cmath>\implies 2^{x} < \frac{2^{40}}{2^{6n+3}} \implies 2^{x} < 2^{40-(6n+3)}\implies 2^{x} < 2^{37-6n} \implies x < 37 - 6n</cmath>
 +
 
 +
Finally, the number of possible values of <math>x</math> is <math>37-6n</math> because <math>x</math> can also be 0 and must be an integer.Therefore, as we increase <math>n</math> from zero upwards, we get the total number of possibilities for <math>x</math> is <math>37+31+25+\ldots+1 = 7 + 36 + 30 + 24 + \ldots + 6 + 0 = 7 + 6 \cdot (6 + 5 + 4\ldots + 1) </math>
 +
 
 +
<math>= 7 + 6 \cdot 3 \cdot 7 = 7 + 18 \cdot 7 = 19 \cdot 7 = 133</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.
+
Since 133 and 780 are relatively prime, the answer is <math>\frac{133}{780}</math> and our final 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>.
+
~KingRavi
  
 
== Solution 2==
 
== 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>.
+
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.
  
−
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, consider the powers of <math>2</math> [[modular arithmetic | mod]] <math>9</math>: <math>2^{6n} \equiv 1, 2^{6n + 1} \equiv 2, 2^{6n + 2} \equiv 4, 2^{6n + 3} \equiv 8 \equiv -1,</math> <math> 2^{6n + 4} \equiv 7 \equiv -2,</math> <math> 2^{6n + 5} \equiv 5 \equiv -4 \pmod 9</math>.
  
−
Now we just do casework:
+
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.
−
<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>.
+
The probability is <math>\frac{133}{780}</math>, and the answer is <math>133 + 780 = \boxed{913}</math>.
  
−
==Solution 3 (modular arithmetic)==
+
-minor edit by Mathkiddie
 +
 
 +
==Solution 3 (similar to 2)==
 
As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for <math>2^0</math>, so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation, <math>2^n+1</math> is congruent to 0 mod 9. Instantly we think of <math>2^3=8</math>, and trial and error soon gives us <math>2^9=512</math>. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that <math>2^6</math> is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations.
 
As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for <math>2^0</math>, so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation, <math>2^n+1</math> is congruent to 0 mod 9. Instantly we think of <math>2^3=8</math>, and trial and error soon gives us <math>2^9=512</math>. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that <math>2^6</math> is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations.
 +
  
 
Next, we look at powers of two exclusive from 1-39. Expressed in an equation, <math>2^n+2^m</math> is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives <math>7*6</math>. Repeat for the other two pairs.
 
Next, we look at powers of two exclusive from 1-39. Expressed in an equation, <math>2^n+2^m</math> is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives <math>7*6</math>. Repeat for the other two pairs.
Line 36: Line 50:
  
 
-jackshi2006
 
-jackshi2006
 +
 +
== Solution 4 ==
 +
Notice that in any binary expression, when we take it modulo <math>9</math> and look at it in groups of 3 starting from the right, we get bases with modulo's <math>4,2,1</math> in the first group and <math>-4,-2,-1</math> in the second group. For our number to be divisible by <math>9</math>, we have to get one of the positive multipliers and its opposite to cancel out. There are a total of <math>7</math> complete positive groups and <math>6</math> complete negative groups and then <math>2^{39}</math> is left which is <math>-1</math>. If we select a <math>1</math>, we have <math>7</math> ways to negate it and <math>7</math> ways to select it giving <math>49</math>. If we select a <math>2</math>, we have <math>6</math> ways to negate it and <math>7</math> ways to select it giving <math>42</math>. The same follows for selecting a <math>4</math>. In total, we need to choose <math>2</math> out of the total <math>40</math> digits to "activate" and turn into a <math>1</math>. In total we get <cmath>\frac{49+42+42}{{40\choose{2}}} = \frac{133}{780}</cmath> Adding, we get <math>133 + 780 = \boxed{913}</math>.
 +
 +
-Vedoral
  
 
== See also ==
 
== See also ==

Latest revision as of 18:19, 8 May 2024

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 (Rigorous)

Any number from 1 to $2^{40}$ can be represented in binary with 40 digits (because $2^{40}$ has 41) with leading zeroes if necessary. Therefore the number of sets where there are exactly two 1’s in this binary representation is just $\binom {40}{2}$ because we’re choosing 2 1s to go in 40 digit slots. This is equal to 780; we have found $q$, our denominator.

With these particular numbers, when converting back to decimal note that the 38 zeroes all cancel out. Let the first 1 when reading the number in binary from left to right be in position $y$, I.e. when converting to decimal, it will have value $2^{y}$. Similarly, let the second 1 have position $x$ (note $x<y$); then the decimal value of that 1 will be $2^{x}$. For example, with the binary string 0001001000 $y$ is 6 and $x$ is 3 (note that it is zero indexed).

It should also be noted that our constraints on $x$ and $y$ are $0 \leq x < y < 40$ and $x, y \in \mathbb{Z}$.

The numbers that satisfy the constraints are therefore equal to $2^{x}+2^{y} = 2^{x} \cdot (1+2^{y-x})$. The conditions say that this is divisible by 9. $2^{x}$ is clearly never divisible by 9, so we can just focus on $1+2^{y-x}$. \[1+2^{y-x} \equiv 0 \pmod 9 \implies 2^{y-x} \equiv -1 \pmod 9 \implies 2^{y-x} \equiv 8 \pmod 9\]

$y-x = 3$ clearly satisfies the congruence, but are there any more? Well, we see that any time we raise -1 (in the second congruence above) to an odd power we get -1 again, so if we raise $2^{3}$, which we know already works, to an odd power, we will also satisfy the congruence. Thus, $2^{3}, 2^{9}, 2^{15},$ etc. work; or, \[y-x \equiv 3 \pmod 6\]

To count the numbers that satisfy the condition, we need to find the amount of numbers that satisfy $2^{x} \cdot (1+2^{y-x}) \leq 2^{40}$, and $y-x \equiv 3 \pmod 6 = 6n +3$ for some whole number $n$.

Since we know $1+2^{y-x} = 1+2^{6n+3}$ is positive, we can divide both sides of the inequality by it; \[2^{x} \cdot (1+2^{y-x}) \leq 2^{40} \implies 2^{x} \leq \frac{2^{40}}{1+2^{y-x}} \implies 2^{x} \leq \frac{2^{40}}{1+2^{6n+3}}\] \[\implies 2^{x} < \frac{2^{40}}{2^{6n+3}} \implies 2^{x} < 2^{40-(6n+3)}\implies 2^{x} < 2^{37-6n} \implies x < 37 - 6n\]

Finally, the number of possible values of $x$ is $37-6n$ because $x$ can also be 0 and must be an integer.Therefore, as we increase $n$ from zero upwards, we get the total number of possibilities for $x$ is $37+31+25+\ldots+1 = 7 + 36 + 30 + 24 + \ldots + 6 + 0 = 7 + 6 \cdot (6 + 5 + 4\ldots + 1)$

$= 7 + 6 \cdot 3 \cdot 7 = 7 + 18 \cdot 7 = 19 \cdot 7 = 133$.

Since 133 and 780 are relatively prime, the answer is $\frac{133}{780}$ and our final answer is $133+780 = \boxed{913}$

~KingRavi

Solution 2

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}$.

-minor edit by Mathkiddie

Solution 3 (similar to 2)

As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for $2^0$, so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation, $2^n+1$ is congruent to 0 mod 9. Instantly we think of $2^3=8$, and trial and error soon gives us $2^9=512$. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that $2^6$ is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations.


Next, we look at powers of two exclusive from 1-39. Expressed in an equation, $2^n+2^m$ is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives $7*6$. Repeat for the other two pairs.

In the end there are $7+42+42+42$ "good" combinations, for an answer of $133 + 780 = \boxed{913}$.


-jackshi2006

Solution 4

Notice that in any binary expression, when we take it modulo $9$ and look at it in groups of 3 starting from the right, we get bases with modulo's $4,2,1$ in the first group and $-4,-2,-1$ in the second group. For our number to be divisible by $9$, we have to get one of the positive multipliers and its opposite to cancel out. There are a total of $7$ complete positive groups and $6$ complete negative groups and then $2^{39}$ is left which is $-1$. If we select a $1$, we have $7$ ways to negate it and $7$ ways to select it giving $49$. If we select a $2$, we have $6$ ways to negate it and $7$ ways to select it giving $42$. The same follows for selecting a $4$. In total, we need to choose $2$ out of the total $40$ digits to "activate" and turn into a $1$. In total we get \[\frac{49+42+42}{{40\choose{2}}} = \frac{133}{780}\] Adding, we get $133 + 780 = \boxed{913}$.

-Vedoral

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=219123"