>но если к кажому из элементов массива
>можно обращаться только 1 раз,
>то это противоречит условию:
>"про любые два из которых можно сказать только
>равны они или нет"

Разумеется нет. Например, Вы можете запомнить
(скопировать) один из элементов и сравнить его
с любым другим. Грубо говоря, Вам дана функция
(предикат), которая на входе имеет два объекта,
а на выходе булево значение "равны/неравны".

>так как сравнивая 1й и 2й элементы,
>я уже обращаюсь к каждому из них по 1-му разу,
>и таким образом уже не могу сравнить ни один
>из них с 3-м.

Кто Вам мешает запомнить эти три элемента?
В условии нет ограничения на запоминание
трех элементов -- там всего лишь есть требование
незавимости используемого объема памяти от
количества элементов в массиве.