Олимпиада имени Леонарда Эйлера 2023-2024 учебный год, II тур заключительного этапа

У ювелира есть 100 золотых монет. Покупатель знает лишь, что веса этих монет равны 1, 2, $\ldots$, 100 г в каком-то порядке, а ювелир знает, какая сколько весит. Как ювелиру за два взвешивания на чашечных весах без гирь доказать покупателю, что известная ювелиру однограммовая монета действительно весит 1 г, но при этом не дать покупателю возможности определить вес никакой другой монеты? ( К. Кноп )

Комментарий/решение

Суммарный вес $9$ монет не превосходит $92 +...+ 100=864$. Суммарный вес $41$ монеты не меньше,чем $1 + ... + 41=861$. Легко проверить, что, кроме указанного, наборов из $41$ монеты с суммарным весом меньше ,чем $864$, есть еще только три: $1,...,40,42;$ $1,...,40,43$; и $1,...,39,41,42.$ При этом только два последних набора обладают тем свойством, что имеются два входящих в набор числа $a<b$ и одно число $c$ ,не входящее в набор ,такие , что $a+c<b$, и для каждого набора такая тройка чисел только одна: $1+41<43$ и $1+40<42$.

Первым взвешиванием сравним монеты $1, ..., 40,43$ с монетами $92, ..., 100.$ Так как чаша с $9$ монетами перевесила , на другой чаше может быть только один из четырех описанных выше наборов из $41$ монеты.Вторым взвешиванием сравним монеты $43$ и $41+1$. Так как чаша с одной монетой перевесила, на другой чаше может быть только набор $1+41$ или $1+40$ . При этом в обоих случаях монета $1$ использовалась в первом взвешивании , а монета , лежащая на чаше с ней , нет.Поэтому покупатель сможет определить монету $1$, а понять ,взвешивалась с ней монета $40$ или $41$ , не сможет.Очевидно, он не сможет определить и ни одну из других монет.