Determine the minimum number of coin-weighings
I had a brief look at this paper, and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.