Difference between revisions of "2005 PMWC Problems/Problem T10"
(→Solutions) |
(→Solutions) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 3: | Line 3: | ||
== Solutions == | == Solutions == | ||
− | |||
− | |||
We list all 2 digit primes: | We list all 2 digit primes: | ||
Line 26: | Line 24: | ||
− | + | 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 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | 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 15: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:
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 |