0
$\begingroup$

n people named i are invited to a party. They are a(i) years old.
We want to position them on some tables by obeying the following criteria:

  • Each guest must sit around a table.
  • Each table should have at least 3 guests around.
  • The sum of age of each two adjacent guests around a table should be a prime number.

We need to solve it with the least possible number of tables or inform that it is impossible. For example, if we have 10 guests that all of them are 20 years old, then it is impossible to position them without violating the constraints.

It is a problem related to Max Flow Network. I think we should consider guests as vertices and create edges between them if and only if the sum of their edges is prime, but I'm not sure about the rest of the solution. So, how to solve it with Max Flow Network approach?

Feel free to ask for more information. Any help would be appreciated.

$\endgroup$
6
  • $\begingroup$ Feel free to ask for more information What is your question? $\endgroup$
    – greybeard
    Dec 30 '21 at 16:20
  • $\begingroup$ @greybeard As I mentioned in the title, how to solve this problem by using Max Flow Network approach? $\endgroup$
    – AriyaDey
    Dec 30 '21 at 17:03
  • 2
    $\begingroup$ Can you share the original source where you encountered this task? $\endgroup$
    – D.W.
    Dec 30 '21 at 19:14
  • 1
    $\begingroup$ Just so you know, in general graph Hamiltonian cycle problem is $\mathsf{NP}$-hard. $\endgroup$ Dec 30 '21 at 20:16
  • 1
    $\begingroup$ I am skeptical whether this is solvable. Based on Inuyasha Yagami's comment, it looks to me like the only hope is to use something special about the prime numbers and the resulting graph. I can see that the graph is triangle-free but I'm not seeing how that would help. Can you please share the source where you encountered this task? What is the motivation for your question? $\endgroup$
    – D.W.
    Dec 31 '21 at 21:12

Your Answer

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

Browse other questions tagged or ask your own question.