The condom problem

Today I'm going to share a problem which I learned from Prof Vishnu Jejjela . As usual I won't spoil the solution for a few days so that people can mull over it. In the mean time I'll lay out the problem and a few special cases which I think are worth thinking about.

n men and m women want to have sex with each other. In particular they want all mn pairings to occur. The problem is that they all have a different STD and they all want to avoid getting anyone else's STD. For this they have condoms, these condoms have some fairly well defined properties.

1. They can be nested.
2. They can be used in either direction.
3. They never break.
4. Diseases never get through them.
5. On the other hand if a side of condom A is in contact with a side of condom B with disease x then disease x jumps to condom A.
6. If a person with disease y uses condom C then disease y appears on the side of condom C actually used.

The problem of course is to minimize the number of condoms used. The naive solution of course involves using mn condoms (1 for each encounter).

Two classically special interesting cases are
1. m=n=2.
2. n=1, m an arbitrary odd integer.

Happy New Year!!!

Happy new year guys (yes both of you). Anyway it's 2015 and I'm going to try to be a more active blogger this year (yes, yes easy to say at the start of the year when everything else going on is comparatively quite).

Anyway what better way to kick of the year than with the 2015 problem of the year . I've played with it a bit but I think I'll leave the ones I have out for a bit. There are a few nice tricks which I don't really want to spoil for anyone reading. I'll leave it for a commenter to spoil. :-)