FINDING THE MAXIMUM AND MINIMUM

We consider the problem of finding the maximum out of a list of n orde red items with binary comparisons where the pth fraction of the answer s may be false. It is shown that the maximum can be determined iff p < 1/2 and that a successful strategy needs Theta(1/1-p)(n) questions. A few similar problems are also discussed, including the problem of fin ding the maximum and minimum simultaneously with lies and in the nuts and bolts model.