Задача на взвешивание и сортировку

Задача. Имеется n одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более n/2) одинаковых. Сделав не более n взвешиваний, найти хотя бы один камень из этого большинства. Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству. Указание. Если найдены два различных камня, то их оба можно выбросить - хотя бы один из них плохой и большинство останется большинством. Решение. Программа просматривает камни по очереди, храня в переменной i число просмотренных камней. (Считаем камни пронумерованными от 1 до n.) Помимо этого программа хранит номер "текущего кандидата" c и его "кратность" k. Смысл этих названий объясняется инвариантом: если к непросмотренным камням (с номерами i+1..n) добавили бы k копий c-го камня, то наиболее частым среди них был бы такой же камень, что и для исходного массива. Получаем такую программу:

k:=0; i:=0
 while i < > n do begin
 | if k=0 then begin
 | | k:=1; c:=i+1; i:=i+1;
 | end else if i+1-ый камень одинаков с c-ым then begin
 | | i:=i+1; k:=k+1;
 | | {заменяем материальный камень идеальным}
 | end else begin
 | | i:=i+1; k:=k-1;
 | | {выкидываем один материальный и один идеальный камень}
 | end;
 end;
 искомым является c-ый камень

Замечание. Поскольку во всех трех вариантах выбора стоит команда i:=i+1, ее можно вынести наружу.