Maths Olympiad Prep

Library / /32 of 37

Number theory Difficulty 6.8 National Olympiad Prove it Italy

Problem:

To steal a precious jewel, a thief must discover the code that allows him to open the safe's door. The information he managed to obtain is the following:
- the code is a number
- any subsequence of consecutive digits of the code (thus every single digit taken individually, as well as every pair of digits, etc., up to the entire number) represents a prime number (for example, 217 does not work, because 1 is not a prime and 21 is not a prime)
- the code is the largest number having this property.
What is the secret code to open the safe?

Solution

Solution:

The answer is 373373.

Let us find all numbers that satisfy the conditions of the problem.

First of all, notice that if we have found all acceptable numbers with nn digits, then an acceptable number with n+1n+1 digits must necessarily contain one of the numbers with nn digits. In particular, if we discover that no number with kk digits exists, then no acceptable number with more than kk digits will exist.

The acceptable numbers with one digit are the one-digit primes, that is 2,3,52, 3, 5 and 77. Notice, however, that the digit 22 and the digit 55 can only appear at the beginning of an acceptable number (otherwise the number would have a subsequence divisible by 22 or by 55 respectively).

The acceptable numbers with two digits are therefore 23,37,53,7323, 37, 53, 73.

Let us now look at the numbers with 33 digits. None can end in 2323 or in 5353. Then 237237, 537537, 273273 and 573573 are not acceptable since they are multiples of 33. No number can begin with the same pair of digits, otherwise it would have a subsequence that is a multiple of 1111 (for example in 773773 the subsequence 7777 is a multiple of 1111). What remains to be checked are 373373, which turns out to be prime (and therefore acceptable), and 737737, which is a multiple of 1111.

Let us now see whether there can be numbers with 44 digits. We only need to check 44 of them: 23732373, 33733373, 53735373 and 73737373. The first and the third contain a subsequence that is a multiple of 33. The second contains a subsequence that is a multiple of 1111, and the last turns out to be a multiple of 101101. Therefore no acceptable numbers with 44 digits exist and, for the reason stated at the beginning, no acceptable numbers with more than 44 digits will exist either. The sought code is therefore 373373.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.