Suppose each of N people has a distinct sexually transmitted infection (STI). Suppose they then shag in pairs, such that in any given encounter:
1. Exactly two people (A and B) are involved;
2. After the encounter, A has all the STIs he or she had initially, plus all those of B, and vice versa.
What is the minimum number of encounters needed to infect everyone with everything? Prove your answer to be optimal.
Hint:
If M of the N people are male and F are female (M+F = N), and we narrow-mindedly allow only heterosexual encounters, then 2M + 2F - 4 instances of hot diseased action can be shown sufficient to infect everyone. Can you think of a way to do it more quickly? Does the requirement of heterosexuality affect the optimum strategy in a meaningful way?
Originally posted by ChronicLeakyHey, not knowing how to play hasn't stopped many people here, including me🙂 welcome anyway. Never too late to learn, as I keep telling myself. Are your puzzles all math oriented? I like physical kind of puzzles as you will see if you look at my so-called contributions here.
I've actually made several posts over in the "Spirituality" forums today; see my profile.
Originally posted by sonhouseThis puzzle is all about getting physical.
Hey, not knowing how to play hasn't stopped many people here, including me🙂 welcome anyway. Never too late to learn, as I keep telling myself. Are your puzzles all math oriented? I like physical kind of puzzles as you will see if you look at my so-called contributions here.
Assuming homosexuality, I think the lowest number necessary is 2N-3 (N>=2).
Start with what would happen with 2 people, 1 and 2. 1 pair is needed to ensure everyone has everything.
3 people, 3 pairs are necessary. (1-2;1-3;2-3)
4 people, 5 pairs are necessary. (1-2;1-3;2-4;1-4;2-3)
5 people, 7 pairs are necessary. (1-2;3-4;1-5;2-3;4-5;1-2;1-3)
This seems to imply a sequence with nth term 2N-3 (N>=2). I can't think of a way to prove this is the case.
Originally posted by itisi4 people:
Assuming homosexuality, I think the lowest number necessary is 2N-3 (N>=2).
Start with what would happen with 2 people, 1 and 2. 1 pair is needed to ensure everyone has everything.
3 people, 3 pairs are necessary. (1-2;1-3;2-3)
4 people, 5 pairs are necessary. (1-2;1-3;2-4;1-4;2-3)
5 people, 7 pairs are necessary. (1-2;3-4;1-5;2-3;4-5;1-2;1-3)
This s ...[text shortened]... imply a sequence with nth term 2N-3 (N>=2). I can't think of a way to prove this is the case.
1 shags 2
3 shags 4
2 shags 3
1 shags 4
After the first three steps, 2 and 3 have all the diseases, while 1 has diseases 1 and 2 and 4 has diseases 3 and 4. After the fourth step, they each have all diseases, and we're done. Thus only 4 trysts are necessary.
Working out a general method of shag-arranging that improves on your method (2N-3 is not optimal) is not hard; proving the new method is optimal is trickier.