Given 80 people, how do you arrange so that each person:

  • listens to exactly 12 other people
  • is listened to by 12 other people

This is an interesting question my friend posed and neither of us could find eh solution to. I feel like the answer is easy but still can't manage to figure it out. I've been trying by manually listing the combinations but there has to be a better way. Thanks in advance!


closed as off-topic by Aweygan, JMP, Antonios-Alexandros Robotis, Morgan Rodgers, Ben Sheller Oct 12 '17 at 3:21

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

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – JMP, Antonios-Alexandros Robotis, Morgan Rodgers, Ben Sheller
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What does it mean for a person to be listening to another? $\endgroup$ – mdave16 Oct 12 '17 at 0:47
  • $\begingroup$ oh i meant it as if each person and to present to each other, and listening would be to listen to someone's presentation. sorry about that $\endgroup$ – watermelon24 Oct 12 '17 at 1:08

Split the $80$ people into $5$ clusters of $16$.

Then, split each cluster of $16$ into $4$ groups of $4$, and have each person within any group of $4$ listen to all the other persons in all the other $3$ groups of $4$ within that cluster of $16$.

If you don't want to allow two people listening to each other, consider this alternative: have the $80$ people sit in a circle and have everyone listen to the $12$ people on their right.

Notice how this alternative will work for any number of people and any number of 'listening to and being listened to'. For example, with $37$ people in a circle, and everyone lostening to the $11$ people to their right, you are by symmetry guaranteed that everyone will be listened to by $11$ people as well.

In fact, you can even do weird things like 'have every listen to the 6th, 13th, 21st, 22nd, 34th, 41st, 43rd, 47th, 49th, 56th, 63rd, and 72nd person to their right': by symmetry, it will still be true that everyone will be listening to and be listened to the same number of people each.

  • $\begingroup$ oh I like this perspective too. thanks mate! $\endgroup$ – watermelon24 Oct 12 '17 at 1:09
  • $\begingroup$ @watermelon24 you're welcome! $\endgroup$ – Bram28 Oct 12 '17 at 1:12

Assuming you can listen to and be listened to by the same person, this would just be an undirected graph with exactly $12$ edges connected to each one of $80$ nodes.

For utility, label each person $1$-$80$ and arrange them in a circle.

First, connect each person to the person on their left and right (an offset of $1$). This graph so far has exactly $2$ edges coming from every vertex.

Next, connect each person to the person two to their left (offset of $2$). This will yield $4$ edges connected to each vertex.

Continue this process with offsets $3$-$6$ to get the graph with $12$ edges on each node.

  • $\begingroup$ thanks so much! doubt i would have come up with that on ym own. cheers! $\endgroup$ – watermelon24 Oct 12 '17 at 1:09
  • $\begingroup$ @watermelon24 Welcome to MSE! Please consider accepting an answer: it's the check under the vote counter :) $\endgroup$ – Austin Weaver Oct 12 '17 at 1:21
  • $\begingroup$ done! thanks again mate! $\endgroup$ – watermelon24 Oct 12 '17 at 1:48

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