Prison Secrets

#1

Our prisoners are fed up with the wardens games and have decided they want to escape. They have been studying the prison and each one has learned a secret which will aid in their escape. The prisoners have started to meet one on one to exchange secrets. Every meeting results in both prisoners knowing all the secrets of the other one. For example, if prisoner A knows secrets 1,3, and 5 while B knows 2 and 6 the result of A and B meeting would be A and B both knowing secrets 1, 2, 3, 5, and 6.

Being a paranoid bunch they are convinced if they have too many meetings the warden will catch on to their plan. Assuming there are 10 prisoners and each one starts knowing a single secret, what is the minimal number of meetings they need for everyone to know all 10 secrets?

#2

I brute forced it one way and got

#

20

Then brute forced it another way and got

#

18

Then I brute forced it a third way and got

#

16

Then I brute forced it a fourth way and got

#

17

I’m tempted to think that

#

16

is the minimum because

Summary

the minimum number of meetings until one prisoner (then by definition two prisoners) know all the secrets is 9 (right?), then you have 8 prisoners remaining to get filled in and I can only see how to reduce that down to 7 more meetings

but I don’t have a proof at the moment

#3

I also lack a proof at the moment. You and I seem to be on the same track tho.

I lack a concrete strategy for 10 prisoners but here’s the argument that agrees with your conclusions

n prisoners upper bound

I basically have that if it takes k meetings for n prisoners then you can at least do it in k+2 meetings for n+1 prisoners. This works by just having prisoner n+1 meet with prisoner 1 first, carry out old strategy, then have prisoner n+1 meet with whoever. Then the 4 prisoner case yields 4 meetings:

  1. 1 meets with 2
  2. 3 meets with 4
  3. 1 meets with 3
  4. 2 meets with 4

This gives us an upped bound of 2n-4 for n prisoners or at least when n > 3 I can’t see any way for 3 prisoners to pull this off in just 2 calls.

#4
My strategy for 10 prisoners

Say prisoner A knows secret 1, prisoner B knows secret 2 etc.

Have prisoner A meet with B, then B meet with C, then C meet with D, then D meet with E. Then have prisoner J meet with I, then I meet with H, then H meet with G, then G meet with F.

This is 8 meetings, and now we have
A - 12
B - 123
C - 1234
D - 12345
E - 12345
F - 678910
G - 678910
H - 78910
I - 8910
J - 910

Then we have E meet with F and D meet with G, and all four of them know all the secrets, after 10 meetings. At this point we just have one of these, say E, meet with the remaining 6 prisoners, and that gives us 16 meetings.