4
$\begingroup$

My sister (a high school teacher) came and asked me the following question:

"Hi bro I'm having 28 new students in my class. They need to know each other. So I want everybody to work together in small groups. I'm thinking splitting them in groups of 4 and having 9 rounds. Then everyone meets 3 people in every round and after 9 rounds they have been in a group with everybody. Isn't that pretty. But I'm just missing an algorithm to set up the groups and you are a CS-master that must a be a job for you!"

I have been trying to figure it out, but the combinatoric search space is to big. Do you have a good suggestion for a way to create these groups.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This frankly sounds more like a question for Math.SE (it's some kind of combinatorial design). But if you want to try to solve it with CS methods, you could express it as an instance of SAT and see if a SAT solver is able to find a solution for you. $\endgroup$
    – D.W. ♦
    Aug 23, 2022 at 19:52

1 Answer 1

Reset to default
1
$\begingroup$

You can solve it with satisfiability. Here i have created the SAT formula for you. Sorry i deleted this answer earlier because i forgot to add a formula, i fixed it, it should be correct now.

enter image description here enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Notice that all the formula is in conjunctive normal form $\endgroup$
    – LLL
    Aug 25, 2022 at 1:04
  • $\begingroup$ Edited the post to add explanation on why p-3 amount of Ati,j $\endgroup$
    – LLL
    Aug 25, 2022 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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