Мешки с монетами.

[Edward_Tur]

Есть несколько достаточно вместительных мешков с монетами. В некоторых из них (меньше половины всех мешков) все монеты фальшивые, в остальных - настоящие. Все настоящие и фальшивые монеты одинаковые по форме. Все настоящие монеты одного веса, все фальшивые монеты также одного веса, но отличаются от веса настоящих.
Двумя взвешиваниями на точных весах с гирьками определить все мешки с фальшивыми монетами.

[Профессор Снэйп]

Не совсем понял условие. Если я положу на одну чашу весов несколько монет, а на другую буду постепенно подкладывать гирьки до тех пор, пока весы не покажут равенство весов на обоих чашах, то это будет считаться за одно взвешивание или нет?

[Руст]

Усовие неверное. Никакими взвешиваниями нельзя определить легче фальшивые или настоящие. Если это известно и известно насколько тяжелее или легче фальшивая по сравнению с настоящим, достаточно одного взвешивания (берём с первого ящика 1, со второго 2, с k-го $2^{k-1}$ монет и взвешиваем). Два взвешивагия нужно только для определения насколько легче или тяжелее. Но без вышеуказанного условия (о том, что фальшивая легче или тяжелее) задача не разрешима.

[Профессор Снэйп]

Руст писал(а):

Усовие неверное. Никакими взвешиваниями нельзя определить легче фальшивые или настоящие.

Там в условии сказано, что мешков с фальшивыми монетами меньше половины.

[Edward_Tur]

Цитата:

Если я положу на одну чашу весов несколько монет, а на другую буду постепенно подкладывать гирьки до тех пор, пока весы не покажут равенство весов на обоих чашах, то это будет считаться за одно взвешивание или нет?

Такое действие считаем за одно взвешивание

[maxal]

Из условия непонятно, могут ли эти весы использоваться для определения точного веса монет. Например, можно ли положить на одну чашу монеты, а на другую только гирьки и по ним понять какой вес имеют монеты? Если это возможно, то можно ли предполагать, что вес гирек и и всех монеток - это целые числа?

Добавлено спустя 16 минут 16 секунд:

А вообще, если это возможно, то решение по сути указано Рустом. Только 2 надо заменить на суммарный вес $M$ монет, взятых по одной из каждого мешка (первое взвешивание). Результат второго взвешивания в $M$-ичной системе счисления будет иметь всего лишь две различные цифры, причем та, которая появляется чаще соответствует настоящим монетам, а та, что реже - фальшивым. При этом позиции цифр однозначно укажут на мешки.

[neo66]

maxal писал(а):

А вообще, если это возможно, то решение по сути указано Рустом. Только 2 надо заменить на суммарный вес $M$ монет, взятых по одной из каждого мешка (первое взвешивание). Результат второго взвешивания в $M$-ичной системе счисления будет иметь всего лишь две различные цифры, причем та, которая появляется чаще соответствует настоящим монетам, а та, что реже - фальшивым. При этом позиции цифр однозначно укажут на мешки.

Если веса целые, то достаточно одного взвешивания: в качестве $M$ берем просто максимальное "физически" возможное число.
Если веса не целые, сильно сомневаюсь, что условие задачи выполнимо.

[maxal]

neo66 писал(а):

Если веса целые, то достаточно одного взвешивания: в качестве $M$ берем просто максимальное "физически" возможное число.

В абстрактной задаче нет "физических" ограничений, и никакого "максимального физически возможного числа" тоже. Но тем не менее, ограничение на веса монет можно найти, используя дополнительное взвешивание, как я указал выше.

[TOTAL]

1)
Слева - куча из по $(n+1)^i$ монет из $i$-го мешка
Справа - столько же монет из последнего мешка
Находим разницу в весе $P_1$

2)
Слева - куча из по $(n+1)^i+1$ монет из $i$-го мешка
Справа - столько же монет из последнего мешка
Находим разницу в весе $P_2$

Отсюда находим количество мешков с отличными (от монет последнего мешка) монетами,
количество отличных монет (взятых в первом взвешивании) и где они находятся.

Чтобы не трудиться с доказательством, лучше заменить $(n+1)$ на "достаточно большое число" (зависит от $n$ - числа мешков)

[Профессор Снэйп]

Приведу тогда уже и своё решение.

Пусть всего $n$ мешков. Предлагается сделать так:

1) При первом взвешивании на левую чашу весов кладём $n$ монет из первого мешка, на вторую --- по одной монете из каждого мешка. Затем, докладывая грузики на одну из чаш, добиваемся того, чтобы весы пришли в равновесие. Фиксируем вес доложенных грузиков.

2) При втором взвешивании на левую чашу кладём $(n^n-1)/(n-1)$ монет из первого мешка, а на вторую --- $n^{i-1}$ монет из $i$-го мешка для каждого $i$ от $1$ до $n$. Снова докладываем грузики на одну из чаш и, добившись равновесия, фиксируем вес положенных грузиков.

По результатам этих двух взвешиваний мы можем определить, в каких мешках лежат монеты, вес которых отличается от веса монет, лежащих в первом мешке.

Действительно, пусть $u_i$ --- это вес монеты, лежащей в $i$-ом мешке . Пусть $S(u_1, \ldots, u_n) = \{ i : u_i \neq u_1 \}$. Пусть также

$$ a(u_1, \ldots, u_n) = \sum_{i=1}^n (u_i - u_1) $$

и

$$ b(u_1, \ldots, u_n) = \sum_{i=1}^n n^{i-1} (u_i - u_1) $$

Нам необходимо показать, что каковы бы не были последовательности $u_1, \ldots, u_n$ и $v_1, \ldots, v_n$, составленные из положительных чисел и такие, что множества $\{ u_1, \ldots, u_n \}$ и $\{ v_1, \ldots, v_n \}$ двухэлементны, если $S(u_1, \ldots, u_n) \neq S(v_1, \ldots, v_n)$, то и пары $\langle a(u_1, \ldots, u_n), b(u_1, \ldots, u_n) \rangle$, $\langle a(v_1, \ldots, v_n), b(v_1, \ldots, v_n) \rangle$ различны.

Предположим, что $a(u_1, \ldots, u_n) = a(v_1, \ldots, v_n) = a$ и $b(u_1, \ldots, u_n) = b(v_1, \ldots, v_n) = b$. Пусть $\delta = a/|S(u_1, \ldots, u_n)|$ и $\varepsilon = a/|S(v_1, \ldots, v_n)|$. Имеем $|a|/(n-1) \leqslant |\delta|, |\varepsilon| \leqslant |a|$. Пусть $i_0$ --- наибольшее число, лежащее в объединении $S(u_1, \ldots, u_n) \cup S(v_1, \ldots, v_n)$. Если $i_0$ принадлежит $S(u_1, \ldots, u_n)$ и не принадлежит $S(v_1, \ldots, v_n)$, то

$$ |b(u_1, \ldots, u_n)| \geqslant n^{i_0-1} |\delta| \geqslant n^{i_0-1} a/(n-1) > $$

$$ > |a| \sum_{i=1}^{i_0-1} n^{i-1} \geqslant \sum_{i=1}^{i_0-1} n^{i-1} |v_i-v_1| = |b(v_1, \ldots, v_n)| $$

что невозможно. Аналогично доказывается, что невозможен случай $i_0 \in S(v_1, \ldots, v_n) \setminus S(u_1, \ldots, u_n)$. Значит, $i_0$ принадлежит каждому из множеств $S(u_1, \ldots, u_n)$ и $S(v_1, \ldots, v_n)$.

Теперь предположим, что $|\delta| < |\varepsilon|$. Так как $\delta, \varepsilon \in \{ a, a/2, \ldots, a/(n-1) \}$, то $|\delta|/|\varepsilon| \leqslant (n-2)/(n-1)$ и

$$ |b(u_1, \ldots, u_n)| \leqslant \sum_{i=1}^{i_0} n^{i-1} |\delta| = |\delta| \frac{n^{i_0}-1}{n-1} \leqslant $$

$$ \leqslant |\varepsilon| \frac{(n^{i_0}-1)(n-2)}{(n-1)^2} < |\varepsilon| n^{i_0-1} \leqslant |b(v_1, \ldots, v_n)|, $$

чего не может быть. Аналогично доказывается, что неравенство $|\varepsilon| < |\delta|$ также невозможно. Значит, $|\delta| = |\varepsilon|$, а так как эти числа одного знака, то $\delta = \varepsilon$ (и $|S(u_1, \ldots, u_n)| = |S(v_1, \ldots, v_n)|$).

Наконец, предположим, что $S(u_1, \ldots, u_n) \neq S(v_1, \ldots, v_n)$. Пусть $i_1$ --- наибольшее число, принадлежащее в точности одному из этих множеств. Пусть

$$ c = \sum_{i=i_1+1}^n n^{i-1} (u_i - u_1) = \sum_{i=i_1+1}^n n^{i-1} (v_i - v_1) $$

Если $i_1$ принадлежит $S(u_1, \ldots, u_n)$ и не принадлежит $S(v_1, \ldots, v_n)$, то

$$ |b(u_1, \ldots, u_n)-c| \geqslant n^{i_1-1} |\delta| > |\varepsilon| \sum_{i=1}^{i_1-1} n^{i-1} \geqslant |b(v_1, \ldots, v_n) - c| $$

и получаем противоречие. Аналогично устанавливается, что $i_1$ не может лежать в $S(v_1, \ldots, v_n) \setminus S(u_1, \ldots, u_n)$. Таким образом любое $i$ от $1$ до $n$ либо не лежит ни в одном множестве $S(u_1, \ldots, u_n)$, $S(v_1, \ldots, v_n)$, либо лежит в обоих множествах и эти множества равны.

Таким образом, по результатам двух взвешиваний мы можем разбить множество мешков на 2 подмножества, в каждом из которых вес монеты, лежащей в мешке, одинаков. Выбрав из них меньшее по количеству элементов множество, получаем в точности множество мешков с фальшивыми монетами.

P. S. Интересно, а можно ли по двум взвешиваниям не просто выделить мешки с фальшивыми монетами, но и установить точный вес монеты в каждом мешке? Ясно, что это можно сделать за 3 взвешивания. Ну а за два?

Добавлено спустя 10 минут 41 секунду:

maxal писал(а):

Из условия непонятно, могут ли эти весы использоваться для определения точного веса монет. Например, можно ли положить на одну чашу монеты, а на другую только гирьки и по ним понять какой вес имеют монеты? Если это возможно, то можно ли предполагать, что вес гирек и и всех монеток - это целые числа?

Я так понял из разъяснения автора темы, что весы тут скорее не с грузиками, а с индикатором, который показывает точную разницу между весами содержимого левой и правой чаш весов. Веса --- это произвольные положительные вещественные числа.

[Edward_Tur]

Решение : Пронумеруем все мешки: $1,2, \ldots ,n$.
Первое взвешивание: положим на левую чашу весов $n$ монет – по одной из каждого мешка, а на правую – $n $ монет из первого мешка. Пусть весы покажут разность в $\Delta _1 $ грамм.
Второе взвешивание: положим на левую чашу весов $n^1 + n^2 + \ldots + n^n $ монет – по $n^k $ из $k$ -ого мешка, а на правую – $n^1 + n^2 + \ldots + n^n $ монет из первого мешка. Пусть весы покажут разность в $\Delta _2 $ грамм.
Положим $x_k = 0$, если монеты с первого и из $k$-ого мешков одинаковые по весом и $x_k = 1$ в противном случае. Понятно, что
$\frac{{\Delta _2 }}{{\Delta _1 }} = \frac{{x_1 n^1 + x_2 n^2 + \cdots + x_n n^n }}{{x_1 + x_2 + \cdots + x_n }}$.
Докажем, что произвольное число можно представить в таком виде не больше, чем одним способом. Действительно, пусть
$\frac{{x_1 n^1 + x_2 n^2 + \cdots + x_n n^n }}{{x_1 + x_2 + \cdots + x_n }} = \frac{{y_1 n^1 + y_2 n^2 + \cdots + y_n n^n }}{{y_1 + y_2 + \cdots + y_n }}{\rm{ }}(x{}_k,y_k = 0{\rm{ }} \vee {\rm{ }}1)$
$x_1 \sum {y_i } n^1 + x_2 \sum {y_i } n^2 + \cdots + x_n \sum {y_i n^n } = y_1 \sum {x_i } n^1 + y_1 \sum {x_i n^2 } + \cdots + y_n \sum {x_i } n^n $
Поскольку $x_k \sum {y_i } \le n – 1$ и ${\rm{y}}_k \sum {x_i } \le n – 1$ (во всех мешках не могут быть монеты одного веса!), то в силу единства записи натурального числа в системе исчисления с основанием $n$, имеем: $x_k \sum {y_i } = {\rm{ y}}_k \sum {x_i } $. Отсюда $x_k = y_k \cdot const \Rightarrow x_k = y_k $, что и требовалось доказать.
Теперь произвольным образом для числа $\frac{{\Delta _2 }}{{\Delta _1 }}$ находим все $x_k$ (например, простым перебором $2^n $ вариантов). Тогда $k$-ый мешок содержит фальшивые монеты тогда и только тогда, когда $x_1 + x_2 + \ldots + x_n < n/2$ и $x_k = 0$ или $x_1 + x_2 + \ldots + x_n > n/2$ и $x_k = 1$.

[Профессор Снэйп]

Edward_Tur писал(а):

Решение : Пронумеруем все мешки: $1,2, \ldots ,n$.
Первое взвешивание: положим на левую чашу весов $n$ монет – по одной из каждого мешка, а на правую – $n $ монет из первого мешка.

Второе взвешивание: положим на левую чашу весов $n^1 + n^2 + \ldots + n^n $ монет – по $n^k $ из $k$ -ого мешка, а на правую – $n^1 + n^2 + \ldots + n^n $ монет из первого мешка.

Точно такое же решение, как у меня

[maxal]

Профессор Снэйп писал(а):

Затем, докладывая грузики на одну из чаш, добиваемся того, чтобы весы пришли в равновесие.
...
Веса --- это произвольные положительные вещественные числа.

С произвольными положительными вещественными числами, "доложить" гирьки до равновесия получится отнюдь не всегда. Причем, для любого набора гирь, коль скоро он несоразмерим с набором весов монет.

[Профессор Снэйп]

maxal писал(а):

Профессор Снэйп писал(а):

Затем, докладывая грузики на одну из чаш, добиваемся того, чтобы весы пришли в равновесие.
...
Веса --- это произвольные положительные вещественные числа.

С произвольными положительными вещественными числами, "доложить" гирьки до равновесия получится отнюдь не всегда. Причем, для любого набора гирь, коль скоро он несоразмерим с набором весов монет.

Ну у нас же нет ограничения на количество гирек. Почему бы тогда не предположить, что всего имеется континуум гирь, по одной на каждый возможный вес

[maxal]

Профессор Снэйп писал(а):

Ну у нас же нет ограничения на количество гирек. Почему бы тогда не предположить, что всего имеется континуум гирь, по одной на каждый возможный вес

Тогда какой смысл в докладывании? Если мы "на глаз" знаем какую гирю нужно доложить, то и докалывать ничего не надо. А если не знаем, то "доложить" не получится даже с континуумом гирь, потому как "докладывание" превратится бесконечный процесс.