Mathematical conversation-starters

It comes up, from time to time, in discussions we have with each other. You're chatting with that long-suffering creature, the Intelligent Layperson, and you feel the urge to explain your professional interests to him/her. And, it has been established that n×n chessboards just don't cut it, or even 100×100 chessboards.

It's time to identify some topics that really work - here's one I tried recently. Consider the following quote from the beginning of the paper Minimal Subsidies in Expense Sharing Games by Meir, Bachrach and Rosenschein, to appear in SAGT.

Three private hospitals in a large city plan to purchase an X-ray machine. The standard type of such machines cost $5 million, and can fulfill the needs of up to two hospitals. There is also a more advanced machine which is capable of serving all three hospitals, but it costs $9 million. The hospital managers understand that the right thing to do is to buy the more expensive machine, which will serve all three hospitals and cost less than two standard machines, but cannot agree on how to allocate the cost of the more expensive machine among the hospitals. There will alway be a pair of hospitals that (together) need to pay at least $6 million, and would then rather split off and buy the cheaper machine for themselves.

The question you ask your audience is, what will be the outcome of the negotiation between the hospitals? Hopefully, someone will begin by saying that 2 hospitals will share a $5M machine, and with any luck, someone else will suggest that the 3rd hospital will offer to share a $5M machine with one of the first two, and pay more than 50%. At this stage, you are in good shape.

Now, you might object that this has nothing to do with computational complexity, which is sort of true, however you can introduce some later on in the discussion if you feel the urge (non-constant number of hospitals or machines). What makes this a nice mathematical topic is that - assuming your audience start to consider a sequence of offers and counter-offers - it raises the issue of making a proper mathematical model of the negotiation (so, if 2 hospitals make an agreement, is it meant to be binding? Presumably not if the 3rd one can "attack" it with a more attractive offer. But if it's not binding, how can the process come to an end?) Finally, despite the fact the problem is ill-posed, there is still a cute answer that is analogous to the answer to this ill-posed problem: when asked what the outcome should be, you say "by symmetry, the hospitals will share a $9M machine". (Actually, don't use the phrase "by symmetry".)