25
$\begingroup$

In a very strange kingdom, 7 mathematicians (let's call them Ann, Ben, Cid, Dan, Eve, Flo and Guy) were sent to prison because they did a calculation which was correct, but was not in favor of the regnant king.

He was really unpredictable and he loved to gamble, so after their condemnation he declared in front of all the mathematicians: "I will select you in random order and will secretly tell each of you the number (1 to 7) of the single prison cell to which the warden will bring you immediately."

"The next morning, you will be brought back here one by one and I'll give each of you a sheet of paper and a pencil and each of you must write down a guess stating which cell each of the others was in*. Only if all you guess correctly will you be freed."

The king believed that this was a "fair" chance for them to regain freedom. "And now, I give you a few minutes to discuss a strategy."

The mathematicians knew that the chance was pretty low that all blind guesses would be correct. However, they knew something which the king was not aware of: On the way to the cells, they had to pass through a transfer room containing nothing but a clock hanging on the wall. Furthermore, they knew that each of them would be unsupervised for a short moment before being put into their respective cell.

They realized and agreed that the two hands of the clock would be the only way to communicate. A resolution of one minute would be the limit. In order to minimize any suspicion, they decided not to tilt or rotate or damage the clock, so the two hands would stay dependent and the rest of the clock would also stay intact.

The next morning, the mathematicians were brought back from their cells, again passing through this transfer room, but this time, they were constantly observed by the warden, so there was no way to touch the clock.

What could have been their strategy to regain freedom?

Edit:

*thanks to @EdMurphy for the unambiguous formulation.

As @AndrewSavinykh pointed out, of course, an essential assumption is that nobody other than the mathematicians will access or change the hands of the clock. Not the king, not the warden and no forces of nature.

enter image description here

This puzzle I created myself and I am not aware if something similar already exists. I think I have a solution, but I'm not 100% sure. Since there are so many smart puzzle enthusiasts here, I hope to get a 100% solution or a proof that this cannot work. Any feedback is appreciated.

$\endgroup$
6
  • 2
    $\begingroup$ Two questions: 1. Do they know in which order they go? For instance, are they going in alphabetical order and they know it? 2. If not, is the clock randomly set before the first prisonner passage? $\endgroup$
    – Florian F
    Feb 16, 2023 at 22:52
  • 3
    $\begingroup$ Is it a running clock? By the way at the end on standing clock 720 positions under the conditions described is possible to be displayed. which is equal to 6!. Thera are 7! possible arrangements, so somehow try to use the known information for each mathematician himself. $\endgroup$
    – z100
    Feb 16, 2023 at 23:23
  • 1
    $\begingroup$ @FlorianF 1. the king determines the (random) order. At the beginning they are all in the same room. So partially, they know the order. 2. this is not important, let's assume it's showing the right time. $\endgroup$
    – theozh
    Feb 17, 2023 at 5:28
  • $\begingroup$ @z100 it's not important whether the clock is running. It's not explicitly mentioned, but they can stop it. Yes, you have more information. $\endgroup$
    – theozh
    Feb 17, 2023 at 5:57
  • 2
    $\begingroup$ I understand that if the clock is running the mathematicians make it stop, so it will not run again. I'm also assuming that supervisors won't notice that and won't not "fix/start" the clock. $\endgroup$ Feb 18, 2023 at 12:06

10 Answers 10

11
$\begingroup$

This is the same solution by loopy-walt, presented a bit differently and adding some context. It seemed to me that the solution has some leaps that may be obvious to many people but also could be unobvious to some, so I wanted to get a smoother explanation - not sure if I succeeded though ;).

First we observe that the clock with the minute resolution allows us to encode 12x60 = 720 = $6!$. This is exactly what we need for encoding positions of 6 prisoners in 6 cells but falls short for 7 prisoners in 7 cells. We can note however, that the last, 7th prisoner, if he gets encoded information about the first 6 will have the full picture.

One of the ways to map 720 numbers to all the permutations of 6 prisoners between 6 cells (or n prisoners between n cells in general) is explained in this Wikipedia article. A practical implementation of this way can be accomplished by deriving the Lehmer Code from a given permutation and then representing this code in factoradic base. We will assume that we have the functions to convert from a permutation to number and back.

One thing that is implied by the puzzle, is that the prisoners know their own order, and the order of all prisoners before them, so the 7th prisoner will know it all. Thus our solution will consist of two parts: firstly we figure out how the first 6 prisoners could encode their cell information to prisoner 7. Secondly we solve how the prisoner 7 can communicate back the final solution, and the prisoners order back to everyone. Note, that the first prisoner does not know the order in which the rest of the prisoners went, and yet they will need to know which prisoner went to which cell.

We can start tackling the first part by trying to get our prisoners to build a list of cell numbers they went in, starting with the first prisoner sent by the king. This first prisoner will start with a list with a single cell - their cell. They will encode this list into a number and set this number on the clockface. The second prisoner will decode that number and will get the list with the first prisoner cell. They will then add their own cell to the list, and encode that list on the clock face and so on, until all the first six prisoners do the same. There are a couple of practical difficulties with this plan, the first is that the number of cells can be 1 to 7, and not 1 to 6 as our encoding function would support. Still the total number of cells for 6 people will still be 6, so we can decrement by 1 the numbers that are greater then the 7th person's cell number. For example, if the 7th person cell number is 3, then the remaining six cell numbers could be (in the order the king sends them): [7,1,2,5,6,4], which we can translate to [7->6,1,2,5->4,6->5,4->3], or [6,1,2,4,5,3] and then encode them after this translation. The other problem, is that the 1st person and the 2nd, and so on would not know which cell the 7th person is so it won't be obvious to them which numbers they need to decrement. We can solve this, by asking them to encode their actual cell number and the other cell numbers that they received from the previous person (if any) if there is no conflicts, and decrement otherwise. In particular, if their cell number is 7 or if their cell number is already present in the list they received, because someone else before them decremented their own cell, they need to decrement their cell number before putting it into the list. If this causes number duplication, they need to also decrement the duplicate, and continue doing that until no duplicates are left. If we consider our previous example, the very first person happened to have number 7 so they will have to decrement it, and encode [6]. The next person has 1 so it's just put as is. Similarly, the two following people also put their number as is. That will lead to [6,1,2,5]. The next person has 6 but 6 already appears in the encoded numbers. So the person decrements 6 to 5, which conflict with the exiting 5, so they decrement that existing 5 to 4. They continue decrementing in this manner until there are no more conflicts, which is in our case after decrementing 5 to 4. The result will be [6,1,2,4,5]. The next person has 4, but 4 is already there. So they decrement 4 to 3 which results in [6,1,2,4,5,3] - exactly the encoding we aimed for.

When a person wants to encode less than 6 numbers e.g. [6,1,2], because they do not know who comes after them, in order for Lehmer encoding to work they need to fill in the remaining slots up to 6 with the numbers that were not taken so far; the order of those remaining numbers does not matter, the next person who decodes this number will know that they are 4th in order (since they know their own order) and they will be able to discard all the numbers but the first 3 based on that.

Now we are coming to the second part. The 7th person in king's order got the encoded number from the 6th person and by incrementing back every number on the list that is equal or greater than their cell number, and then appending their own cell number at the end, they will get the complete list. [6,1,2,4,5,3] for the seventh person in cell 3 will become [6->7,1,2,4->5,5->6,3->4], or [7,1,2,5,6,4], and after adding the final cell 3 we arrive to the initial [7,1,2,5,6,4,3] list. Now this last person needs to do the last final encoding, that will give the rest of the team their final answer. In order to do that this person will a) rearrange the cells list so that the people in the list appear in pre-agreed order, e.g.: Ann, Ben, Cid, Dan, Eve, Flo and Guy; and b) will re-label each room number by adding the same offset by modulo 7 to each room. The offset is chosen so that Guy always ends up in the room 7 after re-labelling. After those two steps we will get the 7 cell numbers in the list, with the last number being 7, because the last person is Guy and we chose the offset so that they are always in the room 7. The last person in the king's order takes the first 6 numbers from this list and encode them and put them on the clock face for everyone to see next day on the way back to the king.

Finally on the next day each person will see that number left for them. They decode it back to the 6 number sequence and add 7 at the end for Guy. Now, since they know what their own cell is and where they are on the list (the list is now ordered from Ana to Guy, and they know their own name) they can calculate the offset applied to the cell numbers by taking the difference between their cell number and the cell number corresponding to them on the list. After this they need to apply this offset to every cell in the list to get the final mapping between all the mathematicians and their cells.

Here is the code implementing it in Go language: The Go Playground.

$\endgroup$
2
  • $\begingroup$ Very good answer! Nevertheless, I still had to read it several times to get it. Thanks for the interesting links. No need to reinvent the wheel ;-). Thanks for the Go-code. $\endgroup$
    – theozh
    Feb 22, 2023 at 22:09
  • $\begingroup$ Nice answer and well-written explanation! $\endgroup$
    – justhalf
    Feb 23, 2023 at 3:59
12
$\begingroup$

HEADS UP: If you find this post interesting in principle but too terse or messy for your liking @Andrew Savinykh has written a more friendly version.

UPDATE: Here is a program demoing the strategy

Python 3

import random

def encode(n,S):
    n-=1
    a = {*range(n)}
    out = 0
    for k in range(n,0,-1):
        out *= k
        if S:
            s,*S=S
            out += sorted(a).index(s)
            a.remove(s)
    return out

def decode(n,c,cut=None):
    n-=1
    out = []
    for k in range(1,n+1):
        x = c%k
        c //= k
        if cut!=None and k<=n-cut:
            assert x==0
            continue
        out = [x] + [y+(y>=x) for y in out]
    return out

def insert(n,S,x):
    if len(S)!=n-1 and {*range(x,n-1)}<={*S}:
        x -= 1
    if {*range(x)}<={*S}:
        sgn = 1
    else:
        sgn = -1
    idx = []
    y = x
    while x in S:
        idx += [S.index(x)]
        x += sgn
    S = S + [y]
    for i in idx:
        S[i]+=sgn
    return S

def encode_final(n,S):
    offs = S[n-1]+1
    S = [(s-offs)%n for s in S]
    return encode(n,S[:n-1])

def decode_final(n,c,j,x):
    S = decode(n,c) + [n-1]
    offs = x - S[j]
    return [(s+offs)%n for s in S]

def agent(clock,id_,rank,cell_id,n=7, all_ids=None):
    S = decode(n,clock,rank)
    S = insert(n,S,cell_id)
    print(f"prisoner {id_} called in position {rank} assigned to cell {cell_id}")
    if rank<n-1:
        out = encode(n,S)
    else:
        R = S[:]
        for k,i in enumerate(all_ids):
            R[i] = S[k]
        out = encode_final(n,R)
    print(f"clock in {clock} clock out {out}")
    return out

n = 7
clock = 0
cells = [*range(n)]
ids = [*range(n)]
random.shuffle(cells)
random.shuffle(ids)

for j,c,i in zip(range(n),cells,ids):
    clock = agent(clock,i,j,c,all_ids=ids) if j==n-1 else agent(clock,i,j,c)
for j,c,i in zip(range(n),cells,ids):
    print(f"prisoner {i}'s guess:", decode_final(n,clock,i,c))

Try it online!

I think it can be done as follows:

As OP clarified each prisoner knows exactly who of the others have already been been assigned their cells. Each can use the clock to send information (a number between 1 and 720) to the next.

As 7x6x5 < 720 the first three can encode their cell numbers without difficulty.

The fourth can do the following:

EDIT not needed can be dealt with using method from prisoners 5 and 6 below. Thanks @user16074

Encode their own cell number. Next, encode how the 6 other numbers are split between the three already assigned and the remaining 3, but without specifying which of the two groups is which. (This saves a factor of 2 and doesn't cost anything because the next prisoner will be able to recover that information from their their own cell number.) Finally, they encode how the three cell numbers are mapped to the first three prisoners. Required coding space 7 x 6-choose-3 / 2 x 3! = 420.

The fifth already will know everything except for one bit. They can now

"remove" the larger of the two yet unassigned cells in the sense that all assigned cells above will have their number reduced by one. Encoding these modified cell assignments requires 6x5x4x3x2 possible states so fits exactly.

The sixth now add their cell number like so:

If it equals the gap they leave the endcoded message unchanged (the gap is reinterpreted as sixth cell). If it is the other value insert it, i.e. increment all larger or equal already assigned cell numbers to make room for it. And then remove the gap as described for the fifth prisoner. Again, their will be just enough coding space to pass this on to the last prisoner.

The last prisoner can now recover full information by inserting their cell number as described for number six. Then they must reencode using an order the prisoners have agreed on before because the order of assignment is not available to all of them. One way of doing this would be:

Let the agreed order be p0,p1,...,p6. Now rename the cells by adding an offset and reducing modulo 7 such that p6 is assigned to the renamed cell c6. Drop this now redundant assignment from the list and encode the remaining renamed associations. Every prisoner can now recover the full assignment list by adding p6->c6. They can then find the offset by comparing their actual cell number to the renamed one and subtract it mod 7 to undo the renaming.

$\endgroup$
9
  • $\begingroup$ Seems interesting, can you add examples? $\endgroup$ Feb 17, 2023 at 14:37
  • $\begingroup$ Avpr! Guvf trarenyvmrf gb neovgenel $a$, ol rapbqvat gur beqre bs pryyf rkpyhqvat gur ynetrfg tnc. Lbh pna hfr guvf vqrn va rirel fgrc naq lbh qba'g rira arrq gur 'gevpx' sbe gur sbhegu cevfbare: Whfg yrg gurz rapbqr gur beqrevat bs gur svefg sbhe cevfbare'f pryyf naq gur svefg gjb tncf. $\endgroup$
    – user16074
    Feb 17, 2023 at 15:02
  • $\begingroup$ I am not sure who the 7 x 6-choose-3 / 2 x 3! = 420 calculation is performed. If you need to select 3 items from 6 posible items without specifying the order, there are $\frac{6!}{3!3!}=20$ posible combinations. You also mention that it is not necessary to specify which is the first and the last group, so this reduces the number by a factor of 2. In total there are $7\frac{6!}{3!3!2}=70$ posible states that need to be encoded. $\endgroup$ Feb 17, 2023 at 15:20
  • $\begingroup$ @TheAverageHijano You need the order within the already assigned group, also, since that information is otherwise lost. Hence a factor of 3!. Easy to overlook in my messy write-up. $\endgroup$
    – loopy walt
    Feb 17, 2023 at 15:55
  • 1
    $\begingroup$ I think that the last paragraph could be improved by explicitly specifying that we not just relabelling the rooms, but also reshuffling the mathematicians as per pre-agreed order. It took me a couple of minutes to figure this part out, as it is not called out explicitly. $\endgroup$ Feb 18, 2023 at 2:33
3
$\begingroup$

I think:

it is not possible.

For simplicity's sake, assume the mathematicians go in alphabetical order. Names can be shuffled without affecting the answer. Notice that when A enters the clock room for the first time they has no information other than their own cell number, so when they return through the room they must be given at least the order of the six other prisoners (this is possible as $6! = 720 = 12\cdot60$). The exact positions are not necessary, as there are only six cells other than A's.

This implies that when G enters the clock room, they must know the order of A-F from the clock (again, possible for the same reason) in order to transmit this information to A. Again, exact positions are not necessary as G knows their cell number.

This implies F must know exact positions of A-E. If F only knows the order of A-E, there is no way for F to know the order of A-F, as they won't know in what position of the permutation they are in. For example, if F knows that the order of A-E is BCADE, but not which cells they're in, then the order of A-F could be any of FBCADE, BFCADE, BCFADE and so on.

However, it is also not possible for F to know the exact positions of A-E. There are $^7P_5$ ways to arrange 5 prisoners in 7 cells, which is 2520, more than the number of possibilities able to be shown by the clock.

$\endgroup$
3
  • 1
    $\begingroup$ rot13(lrf, lbh unir frirauhaqerqnaqgjragl cbffvovyvgvrf gb frg gur pybpx naq lbh guvax lbh jbhyq arrq svirgubhfnaqnaqsbhegl sbe frira crbcyr naq frira pryyf. Ohg gur zngurzngvpvnaf unir zber vasbezngvba guna whfg gur unaqf. Hayrff gurer vf n synj va zl fbyhgvba, V (pheeragyl) fgvyy guvax vg vf cbffvoyr.) $\endgroup$
    – theozh
    Feb 17, 2023 at 6:31
  • $\begingroup$ Rnpu bar, ol gur gvzr gurl zhfg thrff, xabjf: (n) gur beqre bs gubfr jub jrer gnxra njnl orsber gurz, (o) gur gvzr ba gur pybpx jura gurl frr vg gur svefg gvzr, (p) gurve bja pryy, naq (q) gur gvzr ba gur pybpx jura gurl frr vg gur frpbaq gvzr. (Sbe gur svefg bar, (n) vf na rzcgl frg naq (o) vf hfryrff.) Cerfhznoyl n fgengrtl thnenagrrvat pbeerpg thrffrf jbhyq vaibyir gur friragu bar birejevgvat fbzr vasbezngvba gung gur bgure fvk nyernql yrnearq rneyvre. $\endgroup$
    – Ed Murphy
    Feb 17, 2023 at 7:47
  • $\begingroup$ Ah, my bad. I misinterpreted the question. I thought the mathematicians didn't get to know the order of entry. I'll think about it some more and try again later $\endgroup$ Feb 17, 2023 at 12:53
2
$\begingroup$

Here is a solution for $n \leq 6$ prisoners, where they are allowed to communicate using a device with $(n-1)!$ states, which I'll number from $1$ to $(n-1)!$. Call the cell number of the $i$th prisoner $a_i$.

  • $n = 2$: ($1$ state) No communication needed: The other prisoner is in the other cell.
  • $n = 3$: ($2$ states)
    • The first prisoner encodes their cell as $1 \mapsto 1$, $2 \mapsto \text{whatever}$ and $3 \mapsto 2$.
    • The second prisoner then knows the order of $a_1$ and $a_2$: They trivially know this if $a_2 \in \{1, 3\}$, and if $a_2 = 2$ they can look at the device. They communicate this to the third prisoner.
    • The third prisoner knows the order of $a_1$ and $a_2$, and therefore knows everything. They now communicate the order of $a_2$ and $a_3$. This is sufficient for the other prisoners to determine everything.

In general, the last prisoner must always know everything when it is their turn, and it suffices that they communicate the order of $a_2, \ldots, a_n$ to the others. The penultimate prisoner must communicate the order of $a_1, \ldots, a_{n-1}$.

  • $n = 4$: ($6$ states)

    • The first prisoner communicates $a_1$.

    • The second prisoner communicates the order of $a_1$ and $a_2$, along with information about the vacant cells. Consider the following graph whose nodes are binary codes with two $1$'s: enter image description here

      Two codes are joined by an edge if they satisfy the following conditions:

      1. There exists a position $i$ at which both codes have a $1$.
      2. The number of ones before position $i$ is distinct in both codes.

      This graph has a coloring with two colors, which means that the nodes can be colored with only two colors in such a way that no neighbors have the same color. The prisoners agree on a coloring of this graph.

      The second prisoner looks at which cells are vacant, assigns a $1$ to those cells and a zero to the other cells, and communicates the color of the binary code, along with the ordering of $a_1$ and $a_2$.

    • The third prisoner's cell corresponds to one of the $1$'s. Knowing the color of the binary code, they are able to tell how many cells are occupied before and after their position. This determines the ordering of $a_1, a_2, a_3$, which they communicate to the last prisoner.

    • The last prisoner now has all information, and as always communicates the ordering of $a_2, a_3, a_4$.

  • $n = 5$: ($24$ states)

    • The first two prisoners simply communicate their cell number.

    • The third prisoner communicates the order of $a_1, a_2, a_3$ and the color of the binary code corresponding to the vacant cells, based on a coloring of the following graph: enter image description here

      In this case, $3$ colors are sufficient.

    • The fourth prisoner can then determine the order of $a_1, \ldots, a_4$, and the rest works out as before.

  • $n = 6$: ($120$ states)

    • Prisoners $1$ to $3$ just communicate their cell numbers. ($120$ states used)
    • Prisoner $4$ now needs to communicate the order of $a_1, \ldots, a_4$ along with the color of a binary code. It follows from Brook's theorem that $4$ colors are sufficient, because it is not hard to see that every node has at most $4$ neighbors. So this requires $4! \cdot 4 < 120$ states.
    • Prisoner $5$ then knows the ordering of $a_1, \ldots, a_5$ and we are done.
$\endgroup$
1
$\begingroup$

I think this is doable for 3 people.

Suppose we have 2 people and the clock has 1! = 1 position. Then this is possible (the clock is not altered).

For 3 people we can take the following table (P2 knows where P3 is, each P2 clock + P3 combination is unique, and each P3 clock + P1 combination is unique):

P1 P1 clock P2 P2 clock P3 P3 clock
1 1 2 2 3 1
1 1 3 1 2 2
2 2 1 1 3 1
2 2 3 2 1 2
3 2 1 2 2 1
3 2 2 1 1 2

This is a success because each player has a unique row corresponding to the combination of P3 clock, the clock before it gets to them and their own room number.

I'm trying to build an inductive construction for n > 3 but am having trouble getting my head around the details.

$\endgroup$
1
$\begingroup$

In the following I describe a method for the mathematicians to pass the information to one another using the clock so that they can all determine in which cell each mathematician is imprisoned. My method assumes that the two hands of the clock can be arbitrarily rotated. In conventional clocks, the hour and minute hands are mechanically coupled through gears (the position of the hour hand at a given hour is determined by the position of the minute hand) so that the clock only has $12 \times 60=720$ positions. If the two hands are uncoupled, you can use the $60 \times 60=3600$ positions of the clock to send information. I will use the following notation to express the position of the hands: hh:mm, where the two digit numbers hh and mm range from 0 to 59. This is equivalent to using a sexagesimal numeral system, so that hh:mm represents the hh*60+mm number. For example, if the hour hand points over the 33 minute mark and the minute hand over the 15 minute mark the position of the clock is 33:15, which represents the 1995 number in the decimal system.

The OP mentions that the mathematicians are initially in the same room, so they know who has been selected before them and in which order.

The mathematicians need to use the clock to store where the previously selected mathematicians and themselves have been imprisoned. The first mathematician only needs to store his position, there are 7 posible options so he only needs to cover the numbers from 0 to 6 (00:00 to 00:06).

The first 5 mathematicians should follow the same procedure:

The $n$th mathematician needs to store the position of the previously imprisoned mathematicians respecting the order. They know the order in which the other mathematicians have been selected, so they just needs to store the cell numbers in order. The total number of posible variations is $7!/(7-n)!$. For $n=5$ we have $2520$ variations, so we have enough clock positions to encode all variations.

When the 6th mathematician enters the transfer room, he will know where each of the previous mathematicians have been imprisoned, plus where he will be imprisoned. This means that they know that the 7th mathematician will be imprisoned in the remaining cell. The same thing can be said about the 7th mathematician, once he sees the clock prepared by the 5th mathematician he will know the complete solution to the problem.

The 7th mathematician needs to transfer this knowledge to the rest of mathematicians, specially to the first one, who has the least information so far (he only knows that he was imprisoned first and their cell number).

The key is that at this point everyone knows who the first mathematician is and where he was improsoned, so they only have to know where the remaining 6 mathematicians were imprisoned in the remaining 6 cells. This means that there are $6!=720$ possible permutations that need to be encoded. This method will not reveal the order in which they have been imprisoned, only what mathematician has been assigned to each cell. For example, let us assume that Cid was the first mathematician and he was assigned cell #2. His name and cell number need to be removed from the name and cell number lists respectively, so that cell #3 now represents the 2nd cell and so on (the same can be done for the name list).

For example, in this particular case, the 1A 3B 4D 5E 6F 7G configuration (2C is implied) would be represented by number 0 (00:00), the 1A 3B 4D 5E 6G 7F configuration by number 1 (00:01), 1A 3B 4D 5G 6E 7F by number 2 (00:02), 1A 3B 4D 5G 6F 7E by number 3 (00:03), and so on.

This way, all mathematicians will know what mathematician has been assigned to each cell when they walk through the transfer room in their way back to the king.

$\endgroup$
2
  • 3
    $\begingroup$ According to the question the clock is not broken and the two hands would stay dependent, which gives 720 values, not 3600. $\endgroup$ Feb 18, 2023 at 2:30
  • $\begingroup$ @Andrew Savinykh Ahh, I did not realise about the dependent part. Well, I hope that my answer is still useful to design other strategies. $\endgroup$ Feb 20, 2023 at 9:15
1
$\begingroup$

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*4*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 @AndrewSavinykh 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 = 11: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 M7 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:

enter image description here

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 ;-)

$\endgroup$
0
$\begingroup$

Each one only has to write down a guess, and no one ever said that a guess had to cover all six of the other mathematicians. So (say) Ann sets the hour hand to 1 through 7 while leaving the minute hand unchanged, Ben sets the minute hand to 1 through 7 while leaving the hour hand unchanged, and then Ann guesses Ben's room and everyone else guesses Ann's room.

$\endgroup$
2
  • $\begingroup$ OK, maybe it was not clear enough: "each of you ..... a guess about who was in which cell". This implies to me a guess about where all others have been. If you suggest a formulation which makes it unambiguous, I will modify the question. $\endgroup$
    – theozh
    Feb 17, 2023 at 5:38
  • 3
    $\begingroup$ "Each of you must write down a guess stating which cell each of the others was in." $\endgroup$
    – Ed Murphy
    Feb 17, 2023 at 7:06
0
$\begingroup$

Disclaimer: I am sharing my method, which I believe is straightforward to comprehend, and I have not reviewed any previous responses so it could be duplicate.

When faced with a complex problem, I typically begin by simplifying it into smaller versions. For instance, I may consider a scenario involving only three people and determine how much information is necessary for them to communicate effectively.

Let's all prisons as J1, J2, J3..., people who passes the room with clock as P1,P2,P3... and clock location as 0,1,2...

What mathematicians know?

1- Each person can observe who is going to be sent to jail sequentially, and they are all aware that they have the ability to manipulate the clock, but it is also possible that they may choose not to do so.

2: Ultimately, they will all pass by the room containing the clock, affording each person the opportunity to view the outcome.

3: However, since we are uncertain about the order in which the king will select prisoners to be sent to jail, we designate the first prisoner chosen as P1, and so on in ascending order.

4: At present, the clock is operational, but the prisoners have the option to halt its function if they so choose.

These hints are significant because they imply that each time a person passes by the clock, they can transmit a signal to the previous person, and as a result, everyone will witness a signal at the end while going back to the king.


Let's play this game with 3 people only first;

First person goes, it could be A,B or C; what information does he has? he knows which jail he is taken! he is missing

the location of 2nd and 3rd person.

But at least he can give information about himself to others somehow...

1- if P1 is going to J1, he can give information to the next person by adjusting the clock to 0 by damaging the clock, so the P2 will know that P1 will go to J1 jail, likewise, 1 -> J2, if it is J3, then he would not damage the clock so P2 will know that he is going for the J3. So 0 or 1 would be enough for P2 to figure it out.

Second person: since he knows the location of 1st person and himself, he knows P3's location as well. At the moment he knows everything so he should say P3 their location. making the lock 0 or 1 only. 0 means (low,high), 1 mean (high, low). So two information is enough to figure out the rest for him.

For example, if P3 goes to 2 and

  • P1 goes to 1 and P2 goes to 3 then P2 will leave the clock to 0, otherwise
  • P1 goes to 3 and P2 goes to 1 then P2 will leave the clock to 1.

So only P1 does not know the order, P3 will use the same principle as P2 have done for him.

As a result when they are going back to the king, they will all know their locations and 0 and 1 was enough for this!

With the same logic we can solve every kind of size of the people and prisons;

P1: he will just tell his location to P2

P2: he will tell to the P3 about his and P1's location with two information (0,1)

P3: he will tell to the P4 his prison, P1 and P2's location with four information (0,1,2,3)

...

P6: he will tell to P7 about P1,P2,P3,P4,P5 and his location with 6! information.

P7: he will tell to P1 about P2,P3,P4,P5,P6 and his location with 6! information at the end.

$\endgroup$
0
$\begingroup$

Let there be 4 mathematicians ($m_1,m_2,m_3,m_4$) and the resolution 10 minutes.

The $m_4$ must match each ordering of $m_2,m_3,m_4$ with a clock position so that even $m_1$ can work out the cells.

$m_1,m_2,m_3,m_4$ cell no order matches to be used by $m_3$ and $m_4$:

Set to 0 minutes: 1234, 2134, 3124, 4123
Set to 10 minutes: 1432, 2431, 3421, 4321
Set to 20 minutes: 1243, 2143, 3142, 4132
Set to 30 minutes: 1342, 2341, 3241, 4231
Set to 40 minutes: 1324, 2314, 3214, 4213
Set to 50 minutes: 1423, 2413, 3412, 4312

12 possibilities are available to $m_2$, so they must use each clock position twice. When this gets passed to $m_3$, the latter must be able to pinpoint which abovementioned category that would fall into with the help of their own revealed cell. Let 12 be matched with 0 minutes. Then:

Set to 0 minutes: 12, 21
Set to 10 minutes: 34, 43
Set to 20 minutes: 31, 41
Set to 30 minutes: 13, 23
Set to 40 minutes: 32, 42
Set to 50 minutes: 14, 24

... is a possibility. It can also be applied to any number of mathematicians. In general, whenever $m_n$ passes to $m_{n+1}$, the latter must be able to pinpoint which of their category that would fall into with the help of their own revealed cell, and the last mathematician must match each ordering of anyone but the first with a clock position so that even the first can work out the cells.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.