The Combinatorics of Discovery

A vampire and his paramour, a medusa, wish to rendezvous in a large museum. Alas, the vampire cannot abide any rooms with direct sunlight, while the medusa must stay away from any rooms with human occupants, lest she turn them to stone. Thankfully, there is a dark, unoccupied room. How can they be sure to visit the room at the same time?

We’ll discuss the combinatorics of such discovery problems, drawing a connection to the Ramsey numbers and Cayley expander graphs.