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 "2013 AMC 12A Problems/Problem 17"

m (boxify)
(→‎Solution 3 (Work backwards))
 
(11 intermediate revisions by 4 users not shown)
Line 9: Line 9:
 
The first pirate takes <math>\frac{1}{12}</math> of the <math>x</math> coins, leaving <math>\frac{11}{12} x</math>.
 
The first pirate takes <math>\frac{1}{12}</math> of the <math>x</math> coins, leaving <math>\frac{11}{12} x</math>.
  
−
The second pirate takes <math>\frac{2}{12}</math> of the remaining coins, leaving <math>\frac{10}{12}*\frac{11}{12}*x</math>.
+
The second pirate takes <math>\frac{2}{12}</math> of the remaining coins, leaving <math>\frac{10}{12}\cdot
 +
\frac{11}{12}*x</math>.
  
 
Note that
 
Note that
  
−
<math>12^{11} = (2^2 * 3)^{11} = 2^{22} * 3^{11}</math>
+
<math>12^{11} = (2^2 \cdot 3)^{11} = 2^{22} \cdot 3^{11}</math>
  
−
<math>11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2</math>
+
<math>11! = 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2</math>
  
  
−
All the 2s and 3s cancel out of <math>11!</math>, leaving
+
All the <math>2</math>s and <math>3</math>s cancel out of <math>11!</math>, leaving
  
−
<math>11 * 5 * 7 * 5 = 1925</math>
+
<math>11 \cdot 5 \cdot 7 \cdot 5 = 1925</math>
  
 
in the numerator.
 
in the numerator.
Line 30: Line 31:
 
The answer cannot be an even number. Here is why:
 
The answer cannot be an even number. Here is why:
  
−
Consider the prime factorization of the starting number of coins. This number will be repeatedly multiplied by <math>\frac{n}{12}</math>. At every step, we are only removing twos from the prime factorization, never adding them (except in a single case, when we multiply by <math>\frac{2}{3}</math> for pirate 4, but that 2 is immediately removed again in the next step).
+
Consider the highest power of 2 that divides the starting number of coins, and consider how this value changes as each pirate takes their share. At each step, the size of the pile is multiplied by some <math>\frac{n}{12}</math>. This means the highest power of 2 that divides the number of coins is continually decreasing or staying the same (except once, briefly, when we multiply by <math>\frac{2}{3}</math> for pirate 4, but it immediately drops again in the next step).
  
−
Therefore, if the 12th pirate's coin total were even, this can't be the smallest possible value; we can cut the initial pot in half and safely cut all the intermediate totals in half. So this number must be odd.
+
Therefore, if the 12th pirate's coin total were even, then it can't be the smallest possible value, because we can safely cut the initial pot (and all the intermediate totals) in half. We could continue halving the result until the 12th pirate's total is finally odd.
  
 
Only one of the choices given is odd, <math>\boxed{\textbf{(D) }1925}</math>.
 
Only one of the choices given is odd, <math>\boxed{\textbf{(D) }1925}</math>.
 +
 +
Note that if there had been multiple odd answer choices, we could repeat the reasoning above to see that the value also must not be divisible by 3.
 +
 +
==Solution 3 (Work backwards)==
 +
Let <math>x</math> be the number of coins the <math>12</math>th pirate takes. Then the number of coins the <math>k<12</math>th pirate takes is <math>\frac{12}{1} \cdot \frac{12}{2} \cdots \frac{12}{12-k} x</math>. For all these to be an integer, we need the denominators to divide into the numerators. Looking at prime factors, obviously there are sufficient <math>2</math>s and <math>3</math>s, so we just need <math>5^2 \cdot 7 \cdot 11 = \boxed{\textbf{(D) }1925}</math> to divide into <math>x</math>. -Frestho
 +
 +
==Video Solution by Richard Rusczyk==
 +
https://artofproblemsolving.com/videos/amc/2013amc12a/356
 +
 +
~dolphin7
  
 
== See also ==
 
== See also ==
 
{{AMC12 box|year=2013|ab=A|num-b=16|num-a=18}}
 
{{AMC12 box|year=2013|ab=A|num-b=16|num-a=18}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 00:36, 11 October 2020

Problem 17

A group of $12$ pirates agree to divide a treasure chest of gold coins among themselves as follows. The $k^\text{th}$ pirate to take a share takes $\frac{k}{12}$ of the coins that remain in the chest. The number of coins initially in the chest is the smallest number for which this arrangement will allow each pirate to receive a positive whole number of coins. How many coins does the $12^{\text{th}}$ pirate receive?

$\textbf{(A)} \ 720 \qquad \textbf{(B)} \ 1296 \qquad \textbf{(C)} \ 1728 \qquad \textbf{(D)} \ 1925 \qquad \textbf{(E)} \ 3850$

Solution

Solution 1

The first pirate takes $\frac{1}{12}$ of the $x$ coins, leaving $\frac{11}{12} x$.

The second pirate takes $\frac{2}{12}$ of the remaining coins, leaving $\frac{10}{12}\cdot \frac{11}{12}*x$.

Note that

$12^{11} = (2^2 \cdot 3)^{11} = 2^{22} \cdot 3^{11}$

$11! = 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2$


All the $2$s and $3$s cancel out of $11!$, leaving

$11 \cdot 5 \cdot 7 \cdot 5 = 1925$

in the numerator.


We know there were just enough coins to cancel out the denominator in the fraction. So, at minimum, $x$ is the denominator, leaving $\boxed{\textbf{(D) }1925}$ coins for the twelfth pirate.

Solution 2

The answer cannot be an even number. Here is why:

Consider the highest power of 2 that divides the starting number of coins, and consider how this value changes as each pirate takes their share. At each step, the size of the pile is multiplied by some $\frac{n}{12}$. This means the highest power of 2 that divides the number of coins is continually decreasing or staying the same (except once, briefly, when we multiply by $\frac{2}{3}$ for pirate 4, but it immediately drops again in the next step).

Therefore, if the 12th pirate's coin total were even, then it can't be the smallest possible value, because we can safely cut the initial pot (and all the intermediate totals) in half. We could continue halving the result until the 12th pirate's total is finally odd.

Only one of the choices given is odd, $\boxed{\textbf{(D) }1925}$.

Note that if there had been multiple odd answer choices, we could repeat the reasoning above to see that the value also must not be divisible by 3.

Solution 3 (Work backwards)

Let $x$ be the number of coins the $12$th pirate takes. Then the number of coins the $k<12$th pirate takes is $\frac{12}{1} \cdot \frac{12}{2} \cdots \frac{12}{12-k} x$. For all these to be an integer, we need the denominators to divide into the numerators. Looking at prime factors, obviously there are sufficient $2$s and $3$s, so we just need $5^2 \cdot 7 \cdot 11 = \boxed{\textbf{(D) }1925}$ to divide into $x$. -Frestho

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2013amc12a/356

~dolphin7

See also

2013 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 16 		Followed by
Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2013_AMC_12A_Problems/Problem_17&oldid=134897"