Difference between revisions of "1991 AHSME Problems/Problem 26"
(Created page with "An <math>n</math>-digit positive integer is cute if its <math>n</math> digits are an arrangement of the set <math>\{1,2,...,n\}</math> and its first <math>k</math> digits form a...") |
(Added a solution with explanation) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | An <math>n</math>-digit positive integer is cute if its <math>n</math> digits are an arrangement of the set <math>\{1,2,...,n\}</math> and its first | + | == Problem == |
− | <math>k</math> digits form an integer that is divisible by <math>k</math> | + | |
+ | <!-- don't remove the following tag, for PoTW on the Wiki front page--><onlyinclude>An <math>n</math>-digit positive integer is cute if its <math>n</math> digits are an arrangement of the set <math>\{1,2,...,n\}</math> and its first | ||
+ | <math>k</math> digits form an integer that is divisible by <math>k</math>, for <math>k = 1,2,...,n</math>. For example, <math>321</math> is a cute <math>3</math>-digit integer because <math>1</math> divides <math>3</math>, <math>2</math> divides <math>32</math>, and <math>3</math> divides <math>321</math>. How many cute <math>6</math>-digit integers are there?<!-- don't remove the following tag, for PoTW on the Wiki front page--></onlyinclude> | ||
+ | |||
+ | <math>\text{(A) } 0\quad | ||
+ | \text{(B) } 1\quad | ||
+ | \text{(C) } 2\quad | ||
+ | \text{(D) } 3\quad | ||
+ | \text{(E) } 4</math> | ||
+ | |||
+ | == Solution == | ||
+ | <math>\fbox{C}</math> Let the number be <math>abcdef</math>. We know <math>1</math> will always divide <math>a</math>. <math>5</math> must divide <math>abcde</math>, so <math>e</math> must be <math>5</math> or <math>0</math>, but we can only use the digits <math>1</math> to <math>6</math>, so <math>e = 5</math>. <math>4</math> must divide <math>abcd</math>, so it must divide <math>cd</math> (the test for divisibility by 4 is that the last two digits form a number divisible by 4), and so <math>cd</math> must be <math>12</math>, <math>16</math>, <math>24</math>, <math>32</math>, <math>36</math>, (not <math>52</math> or <math>56</math> as the <math>5</math> is already used), or <math>64</math>. We know <math>2</math> divides <math>ab</math> so <math>b</math> is even, <math>4</math> divides <math>abcd</math> so <math>d</math> is even, and <math>6</math> divides <math>abcdef</math> so <math>f</math> is even, and thus <math>b</math>, <math>d</math>, and <math>f</math> must be <math>2</math>, <math>4</math>, and <math>6</math> in some order, so <math>c</math> must be odd, so <math>cd</math> must be <math>12</math>, <math>16</math>, <math>32</math>, or <math>36</math>. Now <math>6</math> divides <math>abcdef</math> implies <math>3</math> divides <math>abcdef</math>, and we know <math>3</math> divides <math>abc</math>, so <math>3</math> must also divide <math>def</math>, so we need a multiple of <math>3</math> starting with <math>2</math> or <math>6</math>, using the remaining digits. If <math>cd</math> is <math>12</math>, then <math>def</math> must be <math>243</math>, <math>234</math>, <math>246</math>, or <math>264</math>, but none of these work as we need <math>e = 5</math>. If <math>cd</math> is <math>16</math>, <math>def</math> must be <math>624</math>, <math>642</math>, <math>645</math>, or <math>654</math>, so <math>654</math> works (it has <math>e=5</math>). If <math>cd</math> is <math>32</math>, similarly nothing works, and if <math>cd</math> is <math>36</math>, <math>651</math> or <math>654</math> works. So now we have, as possibilities, <math>ab1654</math>, <math>ab3651</math>, and <math>ab3654</math>. But clearly <math>ab3651</math> can't work, as we need <math>abcdef</math> to be divisible by <math>6</math>, so it must be even, so we eliminate this possibility. Now with <math>ab1654</math>, we need <math>b</math> to be even, so it must be <math>2</math>, giving <math>a21654</math>, and then <math>321654</math> works as <math>3</math> does divide <math>321</math>. With <math>ab3654</math>, we get <math>a23654</math> as <math>b</math> is even, and then <math>123654</math> works as <math>3</math> divides <math>123</math>. Hence the number of such numbers is <math>2</math>: <math>321654</math> and <math>123654</math>. | ||
+ | |||
+ | == See also == | ||
+ | {{AHSME box|year=1991|num-b=25|num-a=27}} | ||
+ | |||
+ | [[Category: Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 02:40, 24 February 2018
Problem
An -digit positive integer is cute if its digits are an arrangement of the set and its first digits form an integer that is divisible by , for . For example, is a cute -digit integer because divides , divides , and divides . How many cute -digit integers are there?
Solution
Let the number be . We know will always divide . must divide , so must be or , but we can only use the digits to , so . must divide , so it must divide (the test for divisibility by 4 is that the last two digits form a number divisible by 4), and so must be , , , , , (not or as the is already used), or . We know divides so is even, divides so is even, and divides so is even, and thus , , and must be , , and in some order, so must be odd, so must be , , , or . Now divides implies divides , and we know divides , so must also divide , so we need a multiple of starting with or , using the remaining digits. If is , then must be , , , or , but none of these work as we need . If is , must be , , , or , so works (it has ). If is , similarly nothing works, and if is , or works. So now we have, as possibilities, , , and . But clearly can't work, as we need to be divisible by , so it must be even, so we eliminate this possibility. Now with , we need to be even, so it must be , giving , and then works as does divide . With , we get as is even, and then works as divides . Hence the number of such numbers is : and .
See also
1991 AHSME (Problems • Answer Key • Resources) | ||
Preceded by Problem 25 |
Followed by Problem 27 | |
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 | ||
All AHSME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.