Дано логическое выражение, зависящее от 6 логических переменных:
¬ x1 ∨ ¬ x2 ∨ ¬ x3 ∨ x4 ∨ x5 ∨ x6
Сколько существует различных наборов значений переменных, при которых выражение истинно?

Заметим, чтобы сгенерировать строку, нужно знать только предыдущую строку. Будет генерировать по порядку от 1 до n-ой строки.

Программа:

var
  n, i: integer;
  cur_str, prev_str: string;
begin
  read(n);
  prev_str := '';
  for i := 1 to n do {Генерируем строки по порядку от 1 до n}
  begin
    str(i, cur_str); {Записываем в текущую строку её порядковый номер}
    cur_str := prev_str + prev_str + cur_str; {Дописываем предыдущую строку два раза в начало}
    prev_str := cur_str; {Записываем текущею строку вместо предудущей}
  end;
  writeln(cur_str);
end.

1. Делим на кучки 333, 333 и 334 монеты. Взвешиваем кучи по 333. Если они равны - монета в куче с 334. Если нет - то в той, которая легче. Дальше все аналогично: взвешиваем 2 одинаковые кучи. если они одинаковые - то монета в третьей. Иначе в легкой.
2. Далее 333/334 монеты делим на кучки по 111/112
3. 111/112 делим на кучи по 37 / 38 монет
4. кучку 37/38 монет делим на 2 кучи по 12 монет и 1 кучу 14/13 монет
5. Кучку из 12, 13 или 14 монет делим на 2 кучи по 4 монеты и одну 4-6 монет.
6. Кучку из 4-6 монет делим на 2 по 2, либо 2 по 2 и 1 оставшаяся монета. либо 3 кучки по 2.
7. Из кучек по 2 монеты выбираем 1 нефальшивую.

Док-во примерное: для однозначного определения, в какой кучке монета фальшивая, нужно делить их на 2 или 3 кучки. На 4 -уже нельзя будет однозначно определить. Каждым взвешиванием мы уменьшаем кол-во монет, из которого нужно выбрать фальшивую, в 3 раза. На последнем взвешивании должно остаться минимум 3 монеты. Т. е. 3^6-максимальное кол-во монет, из которого можно выбрать 1 фальшивую за 6 взвешиваний. Это 729, что меньше 1000. Т. е. из 1000 монет однозначно определить фальшивую можно только 7ю взвешиваниями.