Haystack hunting hints and locker room communication

We want to efficiently find a specific object in a large unstructured set, which we model by a random n-permutation, and we have to do it by revealing just a single element. Clearly, without any help this task is hopeless and the best one can do is to select the element at random, and achieve the success probability 1/n. Can we do better with some small amount of advice about the permutation, even without knowing the object sought? We show that by providing advice of just one integer in {0, 1, . . . , n−1}, one can improve the success probability considerably, by a Θ(log n/log log n) factor. We study this and related problems, and show asymptotically matching upper and lower bounds for their optimal probability of success. Our analysis relies on a close relationship of such problems to some intrinsic properties of random permutations related to the rencontres number.