6
$\begingroup$

I am running a training course and I want to arrange a set of 1:1 meeting periods between the participants such that at the end of the day there is a maximum of 2 degrees of separation between any of the participants. What is the minimum number of meeting periods required for a given number of participants?

Rules: 1. During each meeting period each participant can meet one other participant; Thus with 20 participants, in a meeting period there can be 10 meeting events 2. There can be an odd number of participants -- in this case only 1 person can sit out from a meeting event 3. No two participants should meet twice

$\endgroup$

closed as off-topic by Rubio Mar 2 at 21:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ "2 degrees of separation" means in this context that everyone has either met another participant or has met someone who has met them. $\endgroup$ – Cormalu Mar 2 at 15:22
  • $\begingroup$ Just out of curiosity, is this an actual situation, or is it a sort of "background" for the puzzle? $\endgroup$ – Brandon_J Mar 2 at 15:26
  • $\begingroup$ This is an actual situation. Many people go on training courses to network, but most people are not great at meeting others. If I can organise short fun meeting events during the day, then everyone leaves with some connections to others and they know that they can get to anyone else who was there on the day through one of their buddies $\endgroup$ – Cormalu Mar 2 at 16:07
  • 3
    $\begingroup$ I like this one though, and it seems too puzzle-y to really be a math problem (probably sitting just on the fence, with the puzzliness of the final answer being what tips it into either territory), so I'm going to pretend I don't see the lozenge next to the closer's name, and nominate the question for reopening. $\endgroup$ – Bass Mar 3 at 12:28
  • 1
    $\begingroup$ It currently appears that 20 people will require 5 meetings and all answers are in agreement with this. You might want to consider extending the question to ask for an algorithm that actually gives the pairings $\endgroup$ – Adam Mar 3 at 13:48
3
$\begingroup$

Here is a good solution for 8 people:

enter image description here

Only 3 meetings are necessary:
AB,CD,EF,GH
BC,DE,FG,HA
AE,BF,CG,DH

I don't have a general solution for larger numbers yet.

$\endgroup$
  • $\begingroup$ Looks like this is better than my pattern predicts. Have an upvote. $\endgroup$ – Brandon_J Mar 2 at 16:08
3
$\begingroup$

Very partial solution

Suppose there are an even number of people: say 2n. (Call them A1..An and B1..Bn.) Then as per Brandon_J's conjecture

we can do the thing with n meeting periods. We'll arrange for all the As to meet all the Bs, which obviously gets us a minimum separation of 2. Number the meeting periods 0..n-1; in period k, A(j) meets B(j+k), wrapping around in the obvious way. Done.

However,

this is definitely not best possible in general. For instance, consider the famous Petersen graph with 10 vertices. The 4-colouring of its edges shown on the linked Wikipedia page shows that in four meeting-periods (one per colour) you can have 10 people meet one another according to the edges of the Petersen graph; but that graph has diameter 2, which is exactly the "maximum of 2 degrees of separation" condition here. So you can do 10 people with only 4 meeting periods. In fact the not-so-famous Chvátal graph shows that you can do 12 people with only 4 meeting periods: it has diameter 2 and edge-chromatic number 4, just as the Petersen graph does.

We can get a lower bound on the number of meeting periods needed from

a theorem (the so-called "Moore bound") that says that if a graph has diameter $k$ and maximum degree $d$, then it has no more than $\frac{d(d-1)^k-2}{d-2}$ vertices. In our case we're looking at $k=2$, and $d$ meeting periods can't bring any degree above $d$ (in fact there's a theorem that a graph with maximum degree $d$ needs either $d$ or $d+1$ meeting periods -- it's called Vizing's theorem), so we have $n \leq \frac{d(d-1)^2-2}{d-2} = \frac{d^3-2d^2+d-2}{d-2} = d^2+1$. So the number of meeting periods needed is definitely always at least $\sqrt{n-1}$.

Here's a construction that's not too bad, though in general it's far from optimal.

Suppose you have $n$ people and let $m=\lceil\sqrt{n}\rceil$. Label each person with a pair of numbers $a,b$ from 1 to $m$. Now have $m-1$ meeting periods in which each person meets everyone else with the same $a$, and then $m-1$ meeting periods in which each person meets everyone else with the same $b$. At the end of this, the "2 degrees of separation" condition is met: you can get from $a_1,b_1$ to $a_2,b_2$ via either $a_1,b_2$ or $a_2,b_1$. (But wait! Those people might not exist, because we don't necessarily have $n=m^2$! True. But if you do the labelling in the obvious way then one of them must exist.) So we can do $n$ people with at most $2\lceil\sqrt{n}\rceil-2$ meeting periods. E.g., 100 people with at most 18 meeting periods.

[EDITED to add:] No, wait, I'm not sure $m-1$ is doable -- as Jaap points out in comments to another solution that proposes essentially the same algorithm as above in the special case where $n$ is a square. I think that to get everyone to meet everyone else with the same $a$ actually takes $m$ sessions if $m$ is odd. So in the worst case you need to add 2 to the upper bound on the number of meeting periods above. (If $m$ is even, you don't. And if $\lfloor\sqrt n\rfloor\lceil\sqrt n\rceil\geq n$, which is true about half the time, you only need to add 1.) Again, though, this is only a bound and I'm fairly sure that the best you can do is usually substantially better.

$\endgroup$
  • $\begingroup$ Gareth, you have a square root in your formula -- do you round that up? $\endgroup$ – Cormalu Mar 2 at 16:40
  • $\begingroup$ Also, is it possible to generate what the meetings should be? $\endgroup$ – Cormalu Mar 2 at 16:40
  • $\begingroup$ Gareth, Jaap showed a way to solve for 8 participants with 3 meeting periods. 2*root8-2 = 4 periods -- assuming root8 rounds up to 3 $\endgroup$ – Cormalu Mar 2 at 16:43
  • 1
    $\begingroup$ I'm not sure which formula you have in mind in each case. The first one -- $\sqrt{n-1}$ -- is only a lower limit. You can round it up to the next integer if you like, since the number of meeting periods is always an integer. There's no guarantee that you can achieve that bound, so definitely no algorithm for doing so. Jaap's solution for n=8 doesn't conflict with this because sqrt(8-1) isn't bigger than 3. [... continues] $\endgroup$ – Gareth McCaughan Mar 2 at 18:01
  • $\begingroup$ The second one -- $2\lceil\sqrt{n}\rceil-2$ -- is a number that's definitely (and fairly straightforwardly) achievable, and I sketch a way to do it via the business with labelling everyone with two numbers. And yes, the $\lceil\cdots\rceil$ notation means to round up. Rounding up $\sqrt8$ gives you 3, and $2\cdot3-2=4$ which is unsurprisingly worse than Jaap's 3. I don't think $2\lceil\sqrt{n}\rceil-2$ is ever the best you can actually do. $\endgroup$ – Gareth McCaughan Mar 2 at 18:04
3
$\begingroup$

EDIT: Just to let you know before you read this, this actually isn't the solution at all. I've made lots of assumptions and serious mistakes! :)

The way to think about this problem is

actually backwards. Given that the guy with the lowest amount of meetings has met the problem conditions, then what is the maximum number of people he could have met?

My algorithm is really simple:

Say you know there were 3 meetings. The maximum number of people A could have met is 3 (BCD). Now, each of those 3 people could have met with 2 other people. 3*2 = 6. For a total of 1+3+6 = 10 people. The problem now is to prove that all the other people have also met the problem conditions.

Notice that

B, C, and D are all connected through A. The only problem is with the other people that they meet. Say B met EF, C met GH, and D met IJ. Each of the people BCD met has two more meetings they can do that we haven't accounted for yet. The solution is then for E to meet G and H. And for F to meet I and J. That way B will connect with everyone. Do the same for GH and IJ. Now everybody is connected.

This algorithm is generalizable

This algorithm works for any amount of meetings. So we can have a pattern for the maximum number of people if we know there were N meetings:
$1 + N + N * (N - 1) = N^2 + 1$
And it looks like this: 2, 5, 10, 17, 26, 37

From this it's easy to see that

If you have X people you will need the next highest number of meetings. So if you have 23 people, you will need 5 meetings. This translates to $\lceil\sqrt{X-1}\rceil$

And that's it.

$\endgroup$
  • $\begingroup$ This gives an upper bound on how many people you can manage with that many meetings, but I believe the bound is only attainable when the number of meetings is 2, 3, 7, or 57. (2,3,7 are definitely possible; no one knows, last I heard, whether 57 is possible or not.) $\endgroup$ – Gareth McCaughan Mar 2 at 16:38
  • $\begingroup$ I'm not sure I understand. I can definitely achieve the upper bound with 4 meetings. I just did it on paper. The problem I see now is if one person is missing then the algorithm breaks down and needs adjustment. I'll work on that. $\endgroup$ – Amorydai Mar 2 at 16:49
  • $\begingroup$ Oh, I see what you mean. Having 17 people means one person will sit out at each meeting time. Nevermind. $\endgroup$ – Amorydai Mar 2 at 17:01
2
$\begingroup$

Let's start with simple situations, work our way up to more complicated scenarios, and then see if we can uncover a pattern.

1 person

Duh. No meetings required.

2 people

One meeting period required.

3 people

Two meeting periods required. (A meets B, B meets C)

4 people

Two meeting periods required (A meets B and C meets D, A meets C and B meets D)

5 people

Three meeting periods required (A meets B and C meets D, A meets E and B meets C, E meets D and A meets C)

This is getting rather complicated now, but it seems that there is a pattern. My guess is that for sessions with more than one person,

The number of meeting periods is exactly one-half the number of people, rounded up for odd-numbered groups.

If anyone can prove this, that would of course be better, but I think that this is a start. Also, even-numbered solutions seem much simpler to arrange than odd-numbered solutions.

$\endgroup$
  • $\begingroup$ I don't know the mathematics but my instinct is that it is less than that. If you have a group of 100 people then after 10 meetings, 1 person has met 10 people, each of which have met another 10 people -- that's 100 people with 2 degrees of separation after 10 meetings. I realise that is a lower bound because all 100 of my buddies buddies need to be different, but I think 50 is too high. $\endgroup$ – Cormalu Mar 2 at 16:22
  • $\begingroup$ yeah, probably @Cormalu - also I don't know the mathematics, either. $\endgroup$ – Brandon_J Mar 2 at 16:24
  • $\begingroup$ So far I've got a solution where 100 people require 15 meetings. There is room for improvement definitely however near the start of the function it follows n/2 so it wasn't a bad estimate $\endgroup$ – Adam Mar 2 at 16:31
2
$\begingroup$

With $N=i^{2}$ people I can do it in a maximum of $2(i-1)$ rounds. Still thinking through the case of N not a perfect square, but think this solution can be extended to that case.

Think of having our n participants on a two dimensional grid (i.e., a large chessboard). First, we arrange meetings between all the participants on each row. With $i$ participants on each row, this takes at most $i-1$ rounds. The repeat the same process for each column. Then for any two arbitrary participants, either they are on the same row or column (and have met), or we can find a third participant who is on the same row as one participant and the same column as the other, who would have met both.

$\endgroup$
  • $\begingroup$ I'd like to see how you'd organise the $i-1$ meeting sessions to make $i$ people all meet each other. If $i$ is odd, I think you need $i$ sessions (and there is an easy method to do so) because in each session one person can't take part. For even $i$ I have no doubt it can be done in $i-1$ sessions but I don't see an easy generalizable method off hand. Apart from that, I think your solution is excellent. $\endgroup$ – Jaap Scherphuis Mar 2 at 17:19
  • $\begingroup$ If N isn't a square, just take the next square larger than N and use that. Cut squares from a corner of your chessboard, such that you can still find a connecting person for each pair of persons on different rows and columns. For example, if you have between 50 and 64 people, use a traditional chessboard and cut H8, then H7, G8, H6, G7, F8, ... If E8 wants a connection to H5, they can't use H8 because that participant doesn't exist, but they can connect via E5 who must exist because they are above the direct line between E8 and H5. $\endgroup$ – Sumyrda Mar 2 at 21:25
1
$\begingroup$

I'm instead going to consider the best possible scenario

Lets assume that everyone takes part, always and that no one has to meet someone already linked to them by a separation (2nd degree).

Using this scenario we can then say that

For a person that has meet $n$ people, the $n$ people they have meet - have meet a unique $n-1$ people, so the total amount of people connected to a person when they have meet $n$ people will be $x=n+n(n-1)$. So for you to meet $x$ people you must have $n$ meetings giving $x=n^2$ however you don't need to meet yourself so using $s$ as the group size, $s=n^2+1$ and so the number of meetings required is $n=\sqrt{s-1}$ in a perfect scenario. This perfect scenario only holds for when $s$ is even and $s-1$ is a square number. I would guess that for when $s$ is odd and $s-1$ is square, the perfect scenario would instead be at $s-1$, making the perfect scenarios follow the sequence: $0,2,4,10,16,26,36,50,64...$ :which is the same as $4i^2$ and $4i^2+4i+2$ alternating with $i \in \mathbb{Z}$. You can then fit these functions so that $i$ follows this sequence which unsurprisingly leaves us with $i^2$ and $i^2+1$. This would give us an upper bound of $i^2$ and a lower bound of $i^2+1$ and translates to $n=\lceil\sqrt{s-1}\rceil,n=\lceil\sqrt{s}\rceil$. (If this assumption is true, I currently don't know why)

We can now extrapolate to a weaker scenario

We make it so that one person never has to sit out more than once and that only one person sits out at a time. Someone sitting out will lose many connections however lets assume that they are only one meeting behind everyone else. This would then require us to add another meeting where the unfortunate lagging behind get the chance to finish their connections. Sticking to the rules so that no more than one person is left out at the final meeting, we would have everyone that is finished meet with a random available person currently linked by 2nd degree.

Im now going to make a bold assumption and conclude that

A group requires the amount of meetings equivalent to the nearest perfect group greater than or equal to its size.

So, if my assumptions are true, the solution should (at most) be

$n=\lceil\sqrt{s}\rceil$

$\endgroup$
0
$\begingroup$

If the graph has $6n$ vertices, then a solution is:

In $n+2$ meetings:
$v_{2k-1}\to v_{2k}$
$v_{2k}\to v_{2k+1}$
Then $v_k\to v_{3a+1}$ (i.e. vertices $4,7,10,13,\dots$)
Repeat the last step for $a=1$ to $a=n$ due to symmetry.

The rest can be solved by adding imaginary people to the group.

$\endgroup$

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