Difference between revisions of "2010 AIME II Problems/Problem 3"

m (Solution)
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
== Problem 3 ==
+
== Problem ==
Let <math>K</math> be the product of all factors <math>(b-a)</math> (not necessarily distinct) where <math>a</math> and <math>b</math> are integers satisfying <math>1\le a < b \le 20</math>. Find the greatest positive integer <math>n</math> such that <math>2^n</math> divides <math>K</math>.
+
Let <math>K</math> be the product of all factors <math>(b-a)</math> (not necessarily distinct) where <math>a</math> and <math>b</math> are integers satisfying <math>1\le a < b \le 20</math>. Find the greatest positive [[integer]] <math>n</math> such that <math>2^n</math> divides <math>K</math>.
  
 
== Solution ==
 
== Solution ==
 +
In general, there are <math>20-n</math> pairs of integers <math>(a, b)</math> that differ by <math>n</math> because we can let <math>b</math> be any integer from <math>n+1</math> to <math>20</math> and set <math>a</math> equal to <math>b-n</math>. Thus, the product is <math>(1^{19})(2^{18})\cdots(19^1)</math> (or alternatively, <math>19! \cdot 18! \cdots 1!</math>.)
  
In general, there are <math>20-n</math> pairs of integers <math>(a, b)</math> that differ by <math>n</math> because we can make <math>b</math> anyway from <math>n+1</math> to <math>20</math> and make <math>a</math> <math>b-n</math>.
+
When we count the number of factors of <math>2</math>, we have 4 groups, factors that are divisible by <math>2</math> at least once, twice, three times and four times.
  
Thus, the product is <math>(1^{19})(2^{18})\cdots(19^1)</math> (some people may recognize it as <math>19!18!\cdots1!</math>.)
 
 
When we count the number of factors of <math>2</math>, we have 4 groups, factors that are divisible by <math>2</math> at least once, twice, three times and four times.
 
 
<br/>
 
<br/>
  
Number that are divisible by <math>2</math> at least once: <math>2, 4, \cdots, 18</math>
+
*Numbers that are divisible by <math>2</math> at least once: <math>2, 4, \cdots, 18</math>
  
Exponent corresponding to each one of them <math>18, 16, \cdots 2</math>
+
:Exponent corresponding to each one of them <math>18, 16, \cdots 2</math>
  
Sum <math>=2+4+\cdots+18=\frac{(20)(9)}{2}=90</math>
+
:Sum <math>=2+4+\cdots+18=\frac{(20)(9)}{2}=90</math>
 
<br/>
 
<br/>
  
Number that are divisible by <math>2</math> at least twice: <math>4, 8, \cdots, 16</math>
+
*Numbers that are divisible by <math>2</math> at least twice: <math>4, 8, \cdots, 16</math>
  
Exponent corresponding to each one of them <math>16, 12, \cdots 4</math>
+
:Exponent corresponding to each one of them <math>16, 12, \cdots 4</math>
  
Sum <math>=4+8+\cdots+16=\frac{(20)(4)}{2}=40</math>  
+
:Sum <math>=4+8+\cdots+16=\frac{(20)(4)}{2}=40</math>  
  
 
<br/>
 
<br/>
  
Number that are divisible by <math>2</math> at least three times: <math>8,16</math>
+
*Numbers that are divisible by <math>2</math> at least three times: <math>8,16</math>
  
Exponent corresponding to each one of them <math>12, 4</math>
+
:Exponent corresponding to each one of them <math>12, 4</math>
  
Sum <math>=12+4=16</math>  
+
:Sum <math>=12+4=16</math>  
  
 
<br/>
 
<br/>
  
Number that are divisible by <math>2</math> at least four times: <math>16</math>
+
*Number that are divisible by <math>2</math> at least four times: <math>16</math>
  
Exponent corresponding to each one of them <math>4</math>
+
:Exponent corresponding to each one of them <math>4</math>
  
Sum <math>=4</math>  
+
:Sum <math>=4</math>  
  
 
<br/>
 
<br/>
  
summing all this we have <math>\boxed{150}</math>
+
Summing these give an answer of <math>\boxed{150}</math>.
 +
 
 +
==Video Solution==
 +
For those of you who want a video solution: https://www.youtube.com/watch?v=NL-9fJBE3HI&list=PLpoKXj-PWCba2d6OG3-ExCZKTLRVYoAkq&index=6
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2010|num-b=2|num-a=4|n=II}}
 
{{AIME box|year=2010|num-b=2|num-a=4|n=II}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 15:17, 12 May 2020

Problem

Let $K$ be the product of all factors $(b-a)$ (not necessarily distinct) where $a$ and $b$ are integers satisfying $1\le a < b \le 20$. Find the greatest positive integer $n$ such that $2^n$ divides $K$.

Solution

In general, there are $20-n$ pairs of integers $(a, b)$ that differ by $n$ because we can let $b$ be any integer from $n+1$ to $20$ and set $a$ equal to $b-n$. Thus, the product is $(1^{19})(2^{18})\cdots(19^1)$ (or alternatively, $19! \cdot 18! \cdots 1!$.)

When we count the number of factors of $2$, we have 4 groups, factors that are divisible by $2$ at least once, twice, three times and four times.


  • Numbers that are divisible by $2$ at least once: $2, 4, \cdots, 18$
Exponent corresponding to each one of them $18, 16, \cdots 2$
Sum $=2+4+\cdots+18=\frac{(20)(9)}{2}=90$


  • Numbers that are divisible by $2$ at least twice: $4, 8, \cdots, 16$
Exponent corresponding to each one of them $16, 12, \cdots 4$
Sum $=4+8+\cdots+16=\frac{(20)(4)}{2}=40$


  • Numbers that are divisible by $2$ at least three times: $8,16$
Exponent corresponding to each one of them $12, 4$
Sum $=12+4=16$


  • Number that are divisible by $2$ at least four times: $16$
Exponent corresponding to each one of them $4$
Sum $=4$


Summing these give an answer of $\boxed{150}$.

Video Solution

For those of you who want a video solution: https://www.youtube.com/watch?v=NL-9fJBE3HI&list=PLpoKXj-PWCba2d6OG3-ExCZKTLRVYoAkq&index=6

See also

2010 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 2
Followed by
Problem 4
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