Difference between revisions of "2008 iTest Problems/Problem 71"

Revision as of 23:58, 5 October 2018

Problem

One day Joshua and Alexis find their sister Wendy's copy of the 2007 iTest. They decide to see if they can work any of the problems and are proud to find that indeed they are able to work some of them, but their middle school math team experience is still not enough to help with the harder problems.

Alexis comes across a problem she really likes, partly because she has never worked one like it before:

What is the smallest positive integer $k$ such that the number $\binom{2k}k$ ends in two zeroes?

Joshua is the kind of mathematical explorer who likes to alter problems, make them harder, or generalize them. So, he proposes the following problem to his sister Alexis:

What is the smallest positive integer $k$ such that the number $\binom{2k}k$ ends in two zeroes when expressed in base 12?

Alexis solves the problem correctly. What is her answer (expressed in base $10$ )?

Solution

If a number ends in two zeroes when expressed in base 12, the number must be a multiple of 144. Thus, the number must be a multiple of 16 and 9.

All numbers of the form $\tbinom{2k}k$ can be rewritten as $\tfrac{2k \cdot (2k-1) \cdots (k+1)}{k \cdot (k-1) \cdots 1}$ . If we want the number to be a multiple of 16 and 9, the numerator must have $4$ more powers of 2 and $2$ more powers of 3 than the denominator.

Also, notice that if $k$ is even, then $k+1$ has one more power of 2 in the numerator, and if $k$ is a multiple of 3, then either $k+1$ or $k+2$ has one more power of 3 in the numerator. With this in mind, we can create a table comparing the number of powers of 2 and 3 in the numerator and the denominator.

Value of $k$	Powers of 2 in $2k \cdot (2k-1) \cdots (k+1)$	Powers of 2 in $k!$	Powers of 2 in $\tbinom{2k}{k}$	Powers of 3 in $2k \cdot (2k-1) \cdots (k+1)$	Powers of 3 in $k!$	Powers of 3 in $\tbinom{2k}{k}$
$5$	$5$	$3$	$2$	$3$	$1$	$2$
$6$	$6$	$4$	$2$	$3$	$2$	$1$
$8$	$8$	$7$	$1$	$4$	$2$	$2$
$10$	$10$	$8$	$2$	$4$	$4$	$0$
$12$	$12$	$10$	$2$	$5$	$5$	$0$
$14$	$14$	$11$	$3$	$8$	$5$	$3$
$15$	$15$	$11$	$4$	$8$	$6$	$2$

After making a table, we see that the lowest value of $k$ that makes $\tbinom{2k}{k}$ a multiple of 144 is $\boxed{15}$ .

2008 iTest (Problems)
Preceded by: Problem 70	Followed by: Problem 72
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 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • 61 • 62 • 63 • 64 • 65 • 66 • 67 • 68 • 69 • 70 • 71 • 72 • 73 • 74 • 75 • 76 • 77 • 78 • 79 • 80 • 81 • 82 • 83 • 84 • 85 • 86 • 87 • 88 • 89 • 90 • 91 • 92 • 93 • 94 • 95 • 96 • 97 • 98 • 99 • 100

@@ Line 3: / Line 3: @@
 One day Joshua and Alexis find their sister Wendy's copy of the 2007 iTest. They decide to see if they can work any of the problems and are proud to find that indeed they are able to work some of them, but their middle school math team experience is still not enough to help with the harder problems.
-Alexis comes across a problem she really likes, partly because she has never worked one like it before:
+Alexis comes across [http://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_13| a problem] she really likes, partly because she has never worked one like it before:
 ''What is the smallest positive integer <math>k</math> such that the number <math>\binom{2k}k</math> ends in two zeroes?''
@@ Line 11: / Line 11: @@
 ''What is the smallest positive integer <math>k</math> such that the number <math>\binom{2k}k</math> ends in two zeroes when expressed in base 12?''
 Alexis solves the problem correctly. What is her answer (expressed in base <math>10</math>)?
 ==Solution==

Page

Toolbox

Search

Difference between revisions of "2008 iTest Problems/Problem 71"

Revision as of 23:58, 5 October 2018

Problem

Solution

See Also