Although, I already accepted @AndrewSavinykh's answer because it is well written and explained, let me write down my solution which is slightly different.
The clock with dependent hands and a resolution of 1 minute can display
only 12*60 = 720 different states
and not as in the case of a damaged clock when the hands are independent 60*60 = 3600 states
The number of possible combinations to distribute 7 persons on 7 cells is
7! = 7*6*5*5*3*2*1 = 5040
So, how can this work?
Well, the mathematicians have some more information.
Each mathematician knows the names of those who have been assigned before him and the names of those who will be assigned after him.
Preparation 1:
We can encode 720 different permutations of 1,2,3,4,5,6.
They agree that the times in HH:MM (or in minutes) correspond to the permutations in increasing order.
00:00 = 0 min --> 1,2,3,4,5,6
00:01 = 1 min --> 1,2,3,4,6,5
...
11:58 = 718 min --> 6,5,4,3,1,2
11:59 = 719 min --> 6,5,4,3,2,1
So, any possible setting on the clock will correspond to one permutation of the numbers 1,2,3,4,5,6.
A small Python snippet to print a list:
import itertools
for idx,item in enumerate(list(itertools.permutations([1,2,3,4,5,6]))):
print("{:02d}:{:02d} = {: 3} min --> {}".format(idx//60, idx%60, idx, item))
To be honest, I still don't know how to do this encoding and decoding efficiently by hand.
But @AndreaSavinykh gave some interesting links in his answer.
Well, they are mathematicians.... they probably know how to do this in their heads ;-).
Again, the king randomly selects the people and the prison cells, hence, the mathematicians have no influence on this.
Preparation 2:
Let's shorten the mathematician's names to: A, B, C, D, E, F, G and let's call the cells C1 to C7.
Convention:
the first selection of the king gets the number M7 and the rest will adapt their numbers from M1 to M6.
For example:
if D is selection #1, then the "M-numbers" will be: A=M1, B=M2, C=M3, D=M7, E=M4, F=M5, G=M6
Now, the mathematicians A to G get numbered names M1 to M7, where M7 (per convention) is selected first and all mathematicians know about this.
There are 7 options to assign a cell for the first selection. How to tell the later coming mathematicians in which cell the selection #1 was put?
Two cases have to be considered:
- M7 was assigned to C1 to C6
- M7 was assigned to C7
Selection #1:
Per convention (see above), selection #1 is M7.
- if M7 is assigned to a cell from C1 to C6, M7 puts "1" at the location of his cell and places the M-numbers 2 to 6 at the remaining unassigned places in increasing order from left to right.
- else if M7 is assigned to C7, then M7 sets the order to the decreasing sequence from left to right
Examples:
M7 --> C4: 2,3,4,1,5,6 = 150 = 02:30
M7 --> C1: 1,2,3,4,5,6 = 0 = 00:00
M7 --> C6: 2,3,4,5,6,1 = 153 = 02:33
M7 --> C7: 6,5,4,3,2,1 = 719 = 23:59
Hence, as a rule and check for the following mathematicians:
The order of the not-yet-assigned M-numbers (excluding the lowest unassigned M-number) will tell the next mathematician whether M7 is either in C1 to C6 (increasing order) or in C7 (decreasing order).
Selections #2 to #5:
Observation made by #n:
If the order of the unassigned M-numbers (from left to right) is
- increasing: M7 is assigned to the cell where the lowest unassigned M-number is currently located.
- decreasing: M7 is in C7.
Hence, #n knows where M7 and the previous mathematicians are.
Actions for #n:
- if #n is assigned to C7, then don't change anything
- else
- if M7 is in C1 to C6:
- if #n's M-number is identical to the smallest unassigned M-number (considering #n still as unassigned) replace the M-number at this location with the next smallest unassigned M-number.
- put #n's M-number at the assigned cell
- keep all assigned numbers and the lowest unassigned M-number at its place and reorder the remaining unassigned M-numbers on the remaining places in increasing order
- if #1 is in C7:
- put #n's M-number at the assigned cell
- keep all assigned numbers at its place and reorder the remaining unassigned M-numbers on the remaining places in decreasing order
Selection #6:
Observation made by #6:
#6 can make the same observations as #2 to #5.
Additionally, #6 also knows the cell of #7, because #6 knows the cells of #1 to #5 and his own cell.
Action for #6:
- if M7 is at C1 to C6, put #7's M-number at the place where M7 is located (i.e. at the lowest unassigned M-number)
- else if M7 is at C7, place #6's M-number at the assigned cell, #7's M-number will automatically be at the correct place
Selection #7:
Observation made by #7
- if #7's M-number is not yet at the right place, M7 is in the cell where #7's number was
- else if #7's M-number is already at the right place, this means M7 is in C7
Action for #7:
- put #7's number at the assigned cell.
When the mathematicians come back the next day, even before they enter the clock room they all already know
where M7 was.
- If M7 was in C7, the numbers can be read just as is for M1 to M6.
- If M7 was in C1 to C6, which they all know, then at this location they will find the M-number of the mathematician who was sent to C7.
Now, they can simply convert M1 to M7 back to real names A to G.
Let's illustrate the whole thing with two examples:
Phew, I hope this is understandable and there is now flaw in it. It got pretty lengthy, although I thought it can be described shorter ;-)
