Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A_1,A_2$ with no edges between them. It is consistent that all elements in $A_1$ are smaller than all elements in $A_2$, in which case the maximum is in $A_2$. Similarly, the maximum could be in $A_1$. The algorithm cannot tell which is which, hence will be wrong on at least one of these scenarios.



The exercise was probably aiming at the following simpler argument: if less than $\lceil n/2 \rceil$ comparisons are made, then there is at least one element which is not compared at all. Hence for all we know, it could be the maximum, or the minimum (if these are different!); indeed, it could be at any position at all. This argument works as long as $n &gt; 1$.