Proofs based on narrowing down sets of possibilities

Question

Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.

First, the comparison sorting lower-bounds proof was recited:

1. For $n$ distinct numbers, there are $n!$ possible orderings.
2. There is only one correct sorted sequence of the $n$ numbers.
3. We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
4. So $\log_2(n!)$ comparisons are required.

Then, the argument was generalized:

1. Define a space of input possibilities
2. Define the goal space, a subset of the input space
3. Define the amount of information that is gained at each step of the computation
4. Calculate the information difference between the space of possibilities and the goal space and divide by the information gain per step to yield the lower bound on the number of steps.

Both arguments above rely on information arguments to prove a lower bound on the number of steps.

Question: are there proofs and/or proof strategies like the above which:

1. prove lower bounds,
2. define an input space,
3. define a goal space which is a subset of the input space, and
4. do not rely on information arguments?

Answer 1

The more general argument is an example of an adversary argument. A nice example is a lower bound for the number of comparisons needed to find the minimum and the maximum at the same time. Said number is $\lceil 1.5 n \rceil - 2$. You can try to construct the algorithm and prove its optimality, or just have a look at the paper.