Договоримся для простоты описания: назовём монету отличающийся весом от других "фальшивой", а остальные настоящими.
Разделим 9 монет по 3 на 3 группы.
1-взвешивание: положим на 1-ю чашу весов первую группу монет, а на 2-ю чашу весов вторую группу монет. Возможны случаи:
1-а) весы равны, тогда фальшивая монета в третьей группе. Продолжим для этого случая взвешивание.
2-взвешивание: положим на 1-ю чашу весов первую монету, а на 2-ю чашу весов вторую монету из третьей группы монет. Возможны случаи:
аа) весы равны, тогда фальшивая монета - это третья монета. Продолжим взвешивание и на 2-ю чашу весов положим фальшивая монету: узнаем легче или тяжелее чем настоящая монета из первой чаши;
аб) весы не равны, тогда один из монет фальшивая - оба монеты перенесём на 2-ю чашу. Отсюда, все монеты вне чаши - настоящие. Продолжим для этого случая взвешивание.
3-взвешивание: положим на 1-ю чашу весов 2 настоящие монеты: узнаем легче или тяжелее вместе фальшивая и настоящая монета чем настоящие монеты из первой чаши. Отсюда, если настоящие монеты тяжелее, то фальшивая легче, или если настоящие монеты легче, то фальшивая тяжелее.
1-б) весы не равны, тогда все монеты третьей группы настоящие. Продолжим для этого случая взвешивание.
2-взвешивание: оставим на 1-й чаше весов монеты, а на 2-ю чашу весов положим все монеты третьей группы, про которых знаем, что они настоящие. Возможны случаи:
ба) весы равны, тогда фальшивая монета находится в группе вне чаши весов, а в чашах находятся настоящие монеты. Монеты из 2-й чаши заменим с группой монет с фальшивой монетой.
3-взвешивание: если настоящие монеты в 1-й чаше тяжелее, то фальшивая легче, или если настоящие монеты легче, то фальшивая тяжелее.
бб) весы не равны, тогда если монеты в 1-й чаше тяжелее, то фальшивая тяжелее, или если монеты в 1-й чаше легче, то фальшивая легче. В этом случае 3-взвешивание не понадобился.
Пусть исходная последовательность 1, 2, 3, 4, 5 ... 100 При преобразовании четность чисел не меняется! Например если мы поменяли местами 2 и 4, то 4 окажется на 2 месте (на четном) и 2 тоже окажется на четном месте (4) Это инвариант! Однако чтобы отсортировать все числа в обратном порядке 1 должна оказаться на 100 месте, а 100 четное, что невозможно Если бы учеников было нечетное число (например 5) то это было-бы возможно: 1 2 3 4 5 -> 3 2 1 4 5 -> 3 2 5 4 1 -> 3 4 5 2 1 -> 5 4 3 2 1 ответ нельзя!
Договоримся для простоты описания: назовём монету отличающийся весом от других "фальшивой", а остальные настоящими.
Разделим 9 монет по 3 на 3 группы.
1-взвешивание: положим на 1-ю чашу весов первую группу монет, а на 2-ю чашу весов вторую группу монет. Возможны случаи:
1-а) весы равны, тогда фальшивая монета в третьей группе. Продолжим для этого случая взвешивание.
2-взвешивание: положим на 1-ю чашу весов первую монету, а на 2-ю чашу весов вторую монету из третьей группы монет. Возможны случаи:
аа) весы равны, тогда фальшивая монета - это третья монета. Продолжим взвешивание и на 2-ю чашу весов положим фальшивая монету: узнаем легче или тяжелее чем настоящая монета из первой чаши;
аб) весы не равны, тогда один из монет фальшивая - оба монеты перенесём на 2-ю чашу. Отсюда, все монеты вне чаши - настоящие. Продолжим для этого случая взвешивание.
3-взвешивание: положим на 1-ю чашу весов 2 настоящие монеты: узнаем легче или тяжелее вместе фальшивая и настоящая монета чем настоящие монеты из первой чаши. Отсюда, если настоящие монеты тяжелее, то фальшивая легче, или если настоящие монеты легче, то фальшивая тяжелее.
1-б) весы не равны, тогда все монеты третьей группы настоящие. Продолжим для этого случая взвешивание.
2-взвешивание: оставим на 1-й чаше весов монеты, а на 2-ю чашу весов положим все монеты третьей группы, про которых знаем, что они настоящие. Возможны случаи:
ба) весы равны, тогда фальшивая монета находится в группе вне чаши весов, а в чашах находятся настоящие монеты. Монеты из 2-й чаши заменим с группой монет с фальшивой монетой.
3-взвешивание: если настоящие монеты в 1-й чаше тяжелее, то фальшивая легче, или если настоящие монеты легче, то фальшивая тяжелее.
бб) весы не равны, тогда если монеты в 1-й чаше тяжелее, то фальшивая тяжелее, или если монеты в 1-й чаше легче, то фальшивая легче. В этом случае 3-взвешивание не понадобился.
При преобразовании четность чисел не меняется!
Например если мы поменяли местами 2 и 4, то 4 окажется на 2 месте (на четном) и 2 тоже окажется на четном месте (4)
Это инвариант!
Однако чтобы отсортировать все числа в обратном порядке 1 должна оказаться на 100 месте, а 100 четное, что невозможно
Если бы учеников было нечетное число (например 5) то это было-бы возможно:
1 2 3 4 5 -> 3 2 1 4 5 -> 3 2 5 4 1 -> 3 4 5 2 1 -> 5 4 3 2 1
ответ нельзя!