Problems & Puzzles:
Puzzles
Puzzle 212. Substring
reversion
Jon Perry sent the following interesting
puzzle:
Given 1 2 3 4 5 6 7 8 9, you are allowed to reverse
any consecutive group of digits, as long as their sum is prime. e.g. we
might progress:
1 2 3 4 5 6 7 8 9
1 2 4 3 5 6 7 8 9
1 2 4 3 5 7 6 8 9
1 2 7 5 3 4 6 8 9
A permutation is not allowed to be repeated. What is
the longest run achievable?
This is easy for smaller sets: e.g. n=2 has the
complete run of 2 (1 2 > 2 1) n=3 has 2 runs of 2 (1 2 3 > 2 1 3 or 1 3
2) but soon gets more difficult.
Q1. Find the longest
run for the starting string 123456789
Now, let me (C.R.)
add the following natural
variation.:
Let's start with a prime composed of
nine distinct digits of the ten available. In each step you may reverse
any substring (not necessarily these with a prime sum). A permutation is
not allowed to be repeated
Q2. What is the largest path if all the
permutations must be prime numbers?
Solution:
