0
$\begingroup$

I have been introduced to this problem recently which to me resembles of round robin, but with an additional rule which might make no solution plausible.

The idea is to find combinations of groups of people, where each person interacts with at least each other person by the end of the rounds, and each person only has to "pay" once.

So consider a group of 9 people that are trying to organize a pizza paying system. Is it possible to divide the 9 people into subgroups of 3 people, where 1 member of each group has volunteered to pay for the pizza, and never have to pay for pizza for any subsequent rounds, in addition to eating with each other person?

Is such a solution possible?

Consider for example the group

1, 2, 3, 4

For the first round we will have

paid  unpaid
 1  ,   2 
 3  ,   4

But then for the second round, because 1 and 3 have already paid, we need 2 and 4 to be both paying and be in a unique group

So the only solution is

 2 , 3
 4 , 1 

But then we cannot have a situation like

1 , 3
2 , 4

so clearly not every person has interacted with each other person. Therefore a solution does not exist.

Are there any circumstances which a solution exists? If so would it have to be a square number or a special number? I was beginning to try to code a solution for this and I quickly realized that it is far more comlpicated than I initially gave credit for.

$\endgroup$
2
$\begingroup$

Let's say you have $n^2$ people eating pizza, divided into $n$ tables of $n$ people each. At every round you have $n$ people paying and each person interacts with other $n-1$ people at the same table. But there are $n^2-1$ people to meet, so you need at least $(n^2-1)/(n-1)=n+1$ rounds for anyone to meet all the others. You need then $n(n+1)$ people paying, which is more than $n^2$.

$\endgroup$
  • $\begingroup$ Ah thanks! This very eloquently put why a solution is so hard to come by. At least $n$ people will have to pay twice in with an additional round in order to meet every other person. $\endgroup$ – aMat Nov 27 '15 at 8:11
  • $\begingroup$ Just as an addendum, if we had $n+1$ seats, then even though some people would see each other more than once, you would have a maximum of $n^2$ paying once (you actually would have $n$ people not having to pay since it would be $n^2 - n$) $\endgroup$ – aMat Nov 27 '15 at 8:15
  • $\begingroup$ Yes, you could have for instance $n(n+1)$ people divided into $n$ tables with $n+1$ seats. With $n+1$ rounds everybody would pay once and would meet $n(n+1)$ people, one more than needed. I'm not sure however you can actually construct a solution where everyone meets all the others. $\endgroup$ – Aretino Nov 27 '15 at 9:17

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.