To whoever's downvoting Eliezer's comment above (I know at least two people have):

If you think he was stupidly wrong to issue the original challenge, downvote that. If you think he was right to issue the original challenge and stupidly wrong to back down when I argued, downvote me since presumably I'm even wronger. But what the hell sense does it make to downvote someone for being prepared to change his mind in the face of disagreement?

Incidentally #1: For an exposition of Eliezer's slightly-unconventional (but, for the avoidance of doubt, neither insane nor desperately ignorant) views on randomized algorithms, and some interesting discussion, see http://lesswrong.com/lw/vp/worse_than_random/ and http://lesswrong.com/lw/vq/the_weighted_majority_algorithm/ .

Incidentally #2: For the multiple-choice test, even better than choosing random answers is to choose random answers and them check them for low Kolmogorov complexity (in so far as that's possible; there are some theorems restricting it) and generate new random answers if the results are bad. You could turn this into a not-at-all-random algorithm that performs even better, given sufficient (vast) computing power: enumerate, and execute, all "cheap enough" computations that produce sets of answers; use this to put some suitable probability distribution on answer-sets (so that answers generated by cheaper computations are more probable, and then (deterministically) choose your answers to minimize the probability of failure. This is the kind of thing Eliezer has in mind when he claims that every randomized algorithm can be beaten by a derandomized one.