Задача с монетами

[Инна]

Комиссия знает, что 8 представленных внешне неразличимых монет имеют вес 1, 1, 2, 2, 3, 3, 4, 4 граммов, но не знают, где какая монета.
Вы знаете, где какая монета, и хотите показать это комиссии, используя весы с чашами без гирь (показывающих либо равенство, либо содержимое какой чаши тяжелее).
Сколько взвешиваний вам потребуется?

То же самое с 10 монетами веса 1, 1, 2, 2, 3, 3, 4, 4, 5, 5.

То же самое с 12 монетами веса 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6.

[Юляша]

Первая задача вроде разбирается за три взвешивания.

1. 4=2+1+1 - идентифицирована одна четверка и состав монет на другой чашке
2. остальные монеты 4+2=3+3 - идентифицированы обе тройки
3. 2=2 - идентифицированы все оставшиеся монеты

---
Третья - тоже за три взвешивания.
1. 6=2+2+1+1 - идентифицирована одна шестерка и состав монет на другой чашке
2. из остальных монет 6=3+3 - идентифицированы вторая шестерка и обе тройки
3. 5+5=4+4+1+1 - идентифицированы все оставшиеся монеты

[Инна]

Есть ли другие варианты?

[Юляша]

Есть, конечно))) А вот уверенности в оптимальности решений1 пока что нет.

[Чива Ротсен]

Решил за два взвешивания. Офигенная задача.

[Инна]

И для 8, и для 10 и для 12 монет?

[Юляша]

Для 8 я подтверждаю, действительно можно за два.

1133 = 44
1122 = 33

Для 12

112233 = 66
61144 = 5533

[Инна]

Для 8 я подтверждаю, действительно можно за два.

Ну вот, осталось для 10 что-то придумать...