Hide and search games with multiple objects
Richard Weber
Talk at Sidney Sussex College (6.30pm, Old Library) November 6, 2012
You have mislaid \(k\) objects (such as your keys, wallet, mobile phone, etc). Each is in lost in one of \(n\) (\(>k\)) locations (such as coat pocket, desk drawer, under bed, gym locker, etc.). It will cost \(c_i\) to search location \(i\) and you want to minimize the expected cost in finding all your objects. “Sod’s law” predicts that the objects are distributed amongst the locations with whatever probability distribution makes your task most difficult. What is this “Sod’s law” distribution? In what order should you search the locations? I will discuss this and some similar problems.
Another cute one is this: “In how many places should a forgetful squirrel hide his nuts?”
Practical and worthwhile search problems include “rescue at sea”, “researching for a cancer cure”, and “oil exploration”.
