16
$\begingroup$

Al and Jane are hosting a party tonight. Al plans on proposing to Jane, a secret only he knows.
The party begins and all 8 guests arrive on time. Immediately and again every minute, everyone forms new conversations.
Throughout the entire party:
1. Each of the 10 partiers is always in exactly 1 conversation.
2. Each conversation must contain at least 2 people.
3. Each conversation lasts exactly 1 minute.
4. No two conversations may involve the exact same set of people.
If someone in a conversation knows the secret they reveal it, so everyone in the conversation now knows the secret.
What is the maximum number of minutes the party can last without Jane discovering the secret?

$\endgroup$
  • 1
    $\begingroup$ By exact same set of people, does that mean no two people can be in the same conversation as each other twice? In other words, if Alice and Bob are in a conversation, can they later be in the same conversation with a third person (say Alice, Bob, and Jane)? $\endgroup$ – JMcAfreak Dec 5 '14 at 21:34
  • $\begingroup$ Nothing says that the secret will spread... How does 1 know when another finds out? $\endgroup$ – warspyking Dec 5 '14 at 21:38
  • $\begingroup$ @JMcAfreak No. If Alice and Bob are in a conversation, then Alice, Bob, and Joe could be in a later conversation. $\endgroup$ – taef Dec 5 '14 at 21:43
  • 3
    $\begingroup$ @warspyking "If someone in a conversation knows the secret they reveal it, so everyone in the conversation now knows the secret." $\endgroup$ – taef Dec 5 '14 at 21:54
  • $\begingroup$ This is reminiscent of the "Gossiping Dons" puzzle. I first saw it in Bollobás' "The Art of Mathematics", though it is much older. $\endgroup$ – Julian Rosen Dec 6 '14 at 20:40
9
$\begingroup$

Edit I can get $15$ minutes before Jane finds out - thanks to @Joel Rondeau. Jane finds out the secret in the $16^{th}$ conversation/minute

Using the notation from @xnor, here is a method:

1. AB; CDEFGHIJ - A-B knows 2. ABC; DEFGHIJ - A-C knows 3. ABCD; EFGHIJ - A-D knows 4. AD BC; EGI FHJ - A-D knows 5. AC BD; EGJ FHI - A-D knows 6. ABCDE; FGHIJ - A-E knows 7. AE BCD; JF IHG - A-E knows 8. BE ACD; IF JHG - A-E knows 9. CE ABD; HF JIG - A-E knows 10. CD ABE; GH FIJ - A-E knows 11. FDB ECA; JG IH - A-F knows 12. FDA ECB; JH IG - A-F knows 13. ABCDEF; GHIJ - A-F knows 14. ABCDEFG: JIH - A-G knows 15. ABCDEFGH: JI - A-H knows

Notice the symmetry: The last 5 are the inverse of the first 5. The ones in the middle are symmetrical with themselves.

$\endgroup$
  • $\begingroup$ Can add CD ABE; GH FIJ $\endgroup$ – Joel Rondeau Dec 8 '14 at 19:45
  • $\begingroup$ Nice, this means the optimal answer is one of 15, 16, or 17. Your observation about symmetry can be nicely formalized: Any solution remains a solution if you reverse the order of the conversations and flip the roles of Al and Jane. $\endgroup$ – xnor Dec 9 '14 at 4:20
4
$\begingroup$

This is a proof of an upper bound of

22 minutes

It shows that the party can't last longer than that. I don't think this bound is tight.

The main idea is to:

Split the party into two parts: Phase A, where $\le5$ people know the secret, and Phase B, where $\ge6$ people know it. The party consists of Phase A followed by Phase B. We bound the length of each half.

The first part is:

Phase A lasts at most 15 minutes because Al must be talking with a different non-empty subset of the four other people in the group of 5 that will be spoiled by the end of Phase A, of which there are $2^4-1 = 15$

The second part proceeds similarly

Phase B lasts at most 7 minutes because Jane must be talking with a different non-empty subset of the three other people that are not spoiled when Phase B starts, of which there are $2^3-1 = 17$

This gives an overall bound of

$7+15 = 22$ minutes


Edit

We can actually improve the bound to

17 minutes

by observing that

Al can only be in one group of 4 in phase A, and Jane can only be in one group of three in Phase B.

$\endgroup$
3
$\begingroup$

Here's a way to get a time of

12 minutes

Arranges conversations by

spliting the party into two groups of five, one with Al and one with Jane, and have each group split into 2+3 in each of the ten possible ways.

You can get another two minutes by

Having each group of 5 in a conversation.

and

Doing the same but splitting a person from each group (not Jane) into a conversation pair, leaving each half with 4.


Here's a way to get a slighly better time of

13 minutes

There's nothing that systematic here. I'll just post the list of conversation clusters. Each line list the people who know the secret beforehand, followed by the conversations, with secret-sharing conversation before the semicolon.

A: AB; CDEFGHIJ AB: ABC; DEFGHIJ ABC: ABCD; EFGHIJ A-D: AD BC; EGI FHJ A-D: AC BD; EGJ FHI A-D: ABCDE; FGHIJ A-E: AE BCD; FG HIJ A-E: BE ACD; FH GIJ A-E: CE ABD; FI GHJ A-E: ABCDEF; GHIJ A-F: ABE CDF; GH IJ A-F: ACE BDF; GI HJ A-F; BCE ADF; GJ HI

$\endgroup$
  • $\begingroup$ this works and beats my best solution $\endgroup$ – taef Dec 6 '14 at 1:07
  • $\begingroup$ See my answer I just posted. I was able to add two extra groups and remove one to get a 14 minute solution. $\endgroup$ – Trenin Dec 8 '14 at 19:42
1
$\begingroup$

8 minutes.
If the secret follows a linear path:
- Al talk to A, so A knows the secret(1 minute);
- Then Al and A, talk to B, so B knows the secret(2 minutes);
- Then Al and A and B talk to C, so now C knows the secret(3 minutes);
Keep this until the next to last person, because "Each conversation must contain at least 2 people" and Jane must be the last person to know about it AND if we include that last person, Jane won´t have anyone to make a conversation.

Anyway it is really strange party!

$\endgroup$
1
$\begingroup$

15 minutes.
First 4 minutes, starts with 1 person, increases group by 1 until size 5. (+4)
Then, need to make groups of 2, so 5 choose 2 is 10, but down by 2 since the groups of 2 and 3 from part 1 don't account. (+8)
Add 1 person. At that point, the small group of 4 can do 2 arrangements (all 4, 2+2, if you left the right combinations from their 5 choose 2). (+2)
Finally, add 1 person to the big group, then finally tell Jane. You can't have the final untold group of 2, since all those combinations have already been done. (+1)

Edited: down to 15 min.

AB | CDEFGHIJ
ABC | DEFGHIJ
ABCD | EFGHIJ
ABCDE | FGHIJ
AC | BDE | HJ | FGI
AD | BCE | FH | GIJ
AE | BCD | FI | GHJ
BC | ADE | FJ | GHI
BD | ACE | GH | FIJ
BE | ACD | GI | FHJ
CD | ABE | GJ | FHI
CE | ABD | HI | FGJ
ABCDEF | GHIJ
ABCDEFG | HIJ
ABCDEFGH | IJ
ABCDEFGHIJ

$\endgroup$
  • $\begingroup$ Can you show all the groupings for the 16 conversations? It is hard to follow. $\endgroup$ – Trenin Dec 8 '14 at 19:51
  • $\begingroup$ Also, your solution Jane finds out in the 15th minute, so there are 14 minutes of conversation before she finds out right? $\endgroup$ – Trenin Dec 8 '14 at 19:55
  • $\begingroup$ Jane actually finds out in the 16th grouping by my thought $\endgroup$ – JonTheMon Dec 8 '14 at 20:04
  • $\begingroup$ Now FHI is used twice. $\endgroup$ – Trenin Dec 9 '14 at 12:31
  • $\begingroup$ So was H on the line. $\endgroup$ – JonTheMon Dec 9 '14 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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