There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?
Any certificate (proof) of distinctness that uses only <, = and > must include comparisons between each pair of adjacent elements in the sorted order. Therefore any certificate of distinctness gives enough information to sort and hence the standard information-theoretic lower bound for sorting applies to any deterministic distinctness algorithm as well.
I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on n numbers requires Ω(n log n) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).
[Ben83] Michael Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 80–86, April 1983. http://doi.acm.org/10.1145/800061.808735
[DL79] David P. Dobkin and Richard J. Lipton. On the complexity of computations under varying sets of primitives. Journal of Computer and System Sciences, 18(1):86–91, Feb. 1979. http://dx.doi.org/10.1016/0022-0000(79)90054-0