Difference between revisions of "2005 PMWC Problems/Problem T10"
(→Solutions) |
(→Solutions) |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
== Solutions == | == Solutions == | ||
| + | We list all 2 digit primes: | ||
| + | 11, 13, 17, 19 | ||
| − | + | 23, 29 | |
| − | + | 31, 37 | |
| + | |||
| + | 41, 43, 47 | ||
| − | + | 53, 59 | |
| − | + | 61, 67 | |
| − | + | 71, 73, 79 | |
| − | + | 83, 89 | |
| − | + | 97 | |
| − | |||
| − | + | Note that <math>0,2,4,5,6,8</math> can only appear as the first digit. We can construct the solution by appending digits to the right of the current number with the following maps from the current units digit. <math>1 \to 1,3,7,9; 3 \to 1,7; 7 \to 1,3,9; 9 \to 7</math>. These alone give a maximum of <math>11</math> digits (counting the first digit of the first prime). Note that <math>9</math> may only map one time, but is mapped to from both <math>1</math> and <math>7</math>, so <math>9</math> must also be used as the last digit. To obtain <math>12</math> digits, we must let the first digit must be of the aforementioned alternatives. | |
| − | + | We also note that we need to use both the strings <math>131</math> and <math>737</math>, since the <math>3</math>s may only appear twice. Also, the strings <math>17</math> and <math>97</math> must appear, barring <math>7</math> from being the second digit. These together imply that <math>3,7,9</math> cannot be the first digit, so the second digit must be <math>1</math>. We [[Greedy algorithm|greedily]] use <math>61</math> first. | |
| − | + | At each step, we pick the maximal number that does not yield a contradiction. This immediately gives: | |
| − | + | <cmath>\boxed{619737131179}</cmath> | |
== See also == | == See also == | ||
Latest revision as of 14:30, 3 July 2012
Problem
Find the largest 12-digit number for which every two consecutive digits form a distinct 2-digit prime number.
Solutions
We list all 2 digit primes:
11, 13, 17, 19
23, 29
31, 37
41, 43, 47
53, 59
61, 67
71, 73, 79
83, 89
97
Note that 
can only appear as the first digit. We can construct the solution by appending digits to the right of the current number with the following maps from the current units digit. 
. These alone give a maximum of 
digits (counting the first digit of the first prime). Note that 
may only map one time, but is mapped to from both 
and 
, so must also be used as the last digit. To obtain 
digits, we must let the first digit must be of the aforementioned alternatives.
We also note that we need to use both the strings 
and 
, since the 
s may only appear twice. Also, the strings 
and 
must appear, barring from being the second digit. These together imply that 
cannot be the first digit, so the second digit must be . We greedily use 
first.
At each step, we pick the maximal number that does not yield a contradiction. This immediately gives:
![\[\boxed{619737131179}\]](http://latex.artofproblemsolving.com/a/4/4/a44e3d8caad40373a86167da54d68a25b88344e7.png)
See also
| 2005 PMWC (Problems) | ||
| Preceded by Problem T9 |
Followed by Last Question | |
| I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 | ||
