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 ChronicLeaky I've actually made several posts over in the "Spirituality" forums today; see my profile.

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.

Originally posted by sonhouse 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 itisi 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.

4 people:

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.