Задачи на взвешивание

Возьмем два любых кубика и сравним их на весах. Возможны такие два случая:
1) кубики имеют разный вес;
2) кубики имеют одинаковый вес.
В первом случае сразу же становится известным один железный кубик — тот, который тяжелее. Далее разделим оставшиеся 8 кубиков на 4 пары и вес каждой из них сравним с весом двух первых кубиков. Если выбранная пара кубиков окажется тяжелее, то в ней оба кубика железные, если она такого же веса, то в ней один кубик железный, а второй — алюминиевый, и наконец, если — легче, то в рассматриваемой паре оба кубика алюминиевые. По результатам проведенных взвешиваний уже будет нетрудно подсчитать число как железных, так и алюминиевых кубиков. Заметим, что в этом случае для решения задачи потребуется лишь 5 взвешиваний.
Рассмотрим теперь второй случай. Будем последовательно сравнивать вес первой пары кубиков с весом каждой из оставшихся четырех пар кубиков до тех пор, пока не будет найдена пара кубиков другого веса (такая пара обязательно найдется, поскольку среди имеющихся 10 кубиков есть как железные, так и алюминиевые кубики). Если новая пара окажется тяжелее, то первые кубики — алюминиевые, а если легче, то — железные. Поиск указанной пары кубиков потребует от одного до четырех взвешиваний.
Сравним на весах между собой вес кубиков новой пары (еще одно взвешивание) и возьмем тот из них, который отличается по весу от кубиков первой пары.
Составим пару из кубиков разного веса и сравним с ней все остальные пары (если такие еще есть). Нетрудно подсчитать, что для выполнения указанных действий достаточно произвести 6 взвешиваний.

На одну чашу весов положить 2 монеты из второго мешка, 3 монеты — из третьего, ..., 7 монет — из седьмого мешка, а на вторую чашу весов положить 8 монет из восьмого мешка, 9 монет — из девятого и 10 — из десятого.
Если фальшивые монеты находятся в первом мешке, то чаши весов будут находиться в равновесии, указатель разновеса покажет 0, так как на каждую чашу положены монеты, общий вес которых составляет ровно по 270 граммов.
Если же первый мешок содержит настоящие монеты, то указатель разновеса укажет на ненулевую величину разности весов монет, находящихся на чашах весов. При этом на более легкой чаше весов находятся фальшивые монеты, а порядковый номер мешка, из которого они взяты, равен показанию разновеса.

Последовательность операций по переливанию молока между имеющимися емкостями представлена в следующей табличке.

	8	5	3
0	8	0	0
1	3	5	0
2	3	2	3
3	6	2	0
4	6	0	2
5	1	5	2
6	1	4	3
7	4	4	0

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

	10	7	3
0	10	0	0
1	7	0	3
2	7	3	0
3	4	3	3
4	4	6	0
5	1	6	3
6	1	7	2
7	8	0	2
8	8	2	0
9	5	2	3
10	5	5	0

Последовательность операций по заполнению ведер водой и их опорожнению представлена в табличке:

	9	4
0	0	0
1	9	0
2	5	4
3	5	0
4	1	4
5	1	0
6	0	1
7	9	1
8	6	4
9	6	0

Первое взвешивание (без гирь): разделить крупу на две равные части по 4,5 кг.
Второе взвешивание (без гирь): одну из получившихся частей разделить пополам — по 2 кг 250 г.
Третье взвешивание: от одной из частей весом в 2 кг 250 г при помощи двух имеющихся гирь отвесить 250 г.

Нельзя.
В результате всех переливаний из одной бочки в другую будет перелито v = m(2 - √2) + n√2 литров жидкости, где m и n — целые числа. Если m = n, то v = 2m — четное число, а если m ≠ n , то v — иррациональное число. Поэтому в любом случае значение не может быть равно 1.

а) 1 звено. Следует разомкнуть четвертое звено цепочки. Образуются разновесы в 1, 3 и 9 граммов.
Действительно, любое целое число отрезка [1,13] можно представить в виде алгебраической суммы чисел 1, 3 и 9 (знак минус означает, что соответствующий разновес помещается на ту же чашку весов, что и взвешиваемый груз).
1 = 1, 2 = 3 - 1; 3 = 3; 4 = 3 + 1, 5 = 9 - 3 - 1, 6 = 9 - 3, 7 = 9 -3 + 1, 8 = 9 - 1, 9 = 9, 10 = 9 + 1; 11 = 9 + 3 + 1, 12 = 9 + 3, 13 = 9 + 3 + 1.
б) Наименьшее количество звеньев цепочки длины N, размыкания которых достаточно для выполнения требования задачи, равно наименьшему натуральному числу, при котором выполняется неравенство
(1)
Доказательство. После размыкания цепочки в m местах, дополнительно к m раскрытым звеньям будут получены еще m + 1 куска этой цепочки, состоящие из n₁, n₂, ..., n_m, n_{m + 1} звеньев. Очевидно, если цепочка состояла из N звеньев, то
m + n₁ + n₂ + ... + n_{m + 1} = N, (2)
а порядковый номер t_i ее i-го размыкаемого звена можно вычислить по формуле
t_i = t_i-1 + n_i + 1 для любого i = 2, 3, ...,m, (3)
а t₁ = n₁ + 1. Поэтому, приняв во внимание равенство (2),
t_m + n_m+1 = N (4)
Не ограничивая общности, можно считать, что
n₁ ≤ n₂ ≤...≤ n_m
(длину (массу) n_{m + 1} последнего куска N-звенной цепочки можно определить из равенства (2) или (4)).
Используя m разомкнутых звеньев цепочки на чашечных весах, можно уравновесить груз, выраженный в граммах любым целым числом от 1 до m.
Если же использовать m разомкнутых звеньев цепочки и ее n₁ -звенный кусок, то можно уравновесить груз, выраженный в граммах любым целым числом из интервала и [1,m] и [n₁ - m, n₁ + m] (здесь предполагается, что n₁ > m). Если при этом n₁ = 2m + 1, то, используя лишь указанные части цепочки, можно уравновесить груз, масса которого в граммах выражается любым целым числом из интервала [1, Зm+1]. Этот интервал представляет собой объединение непересекающихся интервалов [1,m] и [n₁ - m, n₁ + m] и имеет длину m + n₁ = 3m + 1.
Руководствуясь аналогичным правилом, можно подобрать длину n₂ второго куска цепочки: значение n₂ должно быть таким, чтобы, во-первых, используя лишь m разомкнутых звеньев цепочки и ее n₁- и n₂-звенные куски, можно было бы уравновесить груз, масса которого в граммах выражается любым целым числом из интервала [1, n₂ + n₁ + m] и, во-вторых, чтобы интервал [n₂ - n₁ - m, n₂ + n₁ + m] не имел общих точек с непересекающимися интервалами [1,m] и [n₁ - m, n₁ + m]. Эти условия, очевидно, выполняются в том и только в том случае, когда n₂ - n₁ - m = n₁ + m + 1, то есть, если n₂ = 2n₁ + 2m + 1 = 3n.
В общем случае длина n_i+1 (i+1)-го куска цепочки должна быть такой, чтобы, используя лишь m ее разомкнутых звеньев и куски длины {n_j}, j = 1, ..., i, можно было бы уравновесить груз, выраженный в граммах любым целым числом из интервала , и чтобы интервал не имел общих точек с интервалом . Отсюда следует, что , и поэтому
(6)
Итак, используя m разомкнутых звеньев заданной цепочки и ее куски длиной n₁, n₂ ..., n_m, на чашечных весах можно уравновесить груз, величина которого в граммах принимает любое целочисленное значение из интервала . Учитывая соотношения (6) и то, что n₁ = 2m + 1, максимальная масса P_m такого груза равна
(7)
Пусть P — масса в граммах уравновешиваемого груза, выражаемая любым целым числом из интервала [1, N]. Достаточно рассмотреть лишь случай, когда P > P_m, т. е. Р = P_m + p, где p — произвольное целое число отрезка [1, n_m+1].
Предположим для определенности, что на левую чашку весов поместили указанный груз P, а на правую, чтобы этот груз уравновесить, (m+1)-й кусок цепочки и некоторое сочетание разновесов общей массой, составленной из имеющихся разомкнутых звеньев и кусков цепочки. Чашки весов находятся в равновесии тогда и только тогда, когда выполняется равенство Р = n_m+1 + x, т. е., если
(8)

Отсюда, так как 1 ≤ p ≤ n_m+1, имеем

(9)
Условие, выражающее возможность составить из имеющихся разновесов (без последнего (m + 1)-го куска цепочки) массу х, состоит в выполнении неравенства
(10)
(отрицательное значение х означает, что система разновесов размещается вместе с грузом P на левой чашке весов). Из этого неравенства следует требование n_m+1 ≤ 2P_m + 1, которое, учитывая равенства P_m + n_m+1 = N и (7), эквивалентно неравенству (1)

и, значит,
(11)
Таким образом, для заданного N можно вычислить минимальное значение m, для которого выполняется неравенство (11), и затем уже по формуле (6) вычислить «длины» кусков {n_i} требуемых разновесов, а по формуле (3) — порядковые номера размыкаемых звеньев цепочки.
Заметим, правая часть N_max неравенства (11) есть точная верхняя оценка максимального числа N звеньев у цепочки, размыкание m звеньев которой позволит выполнить требование задачи. Приведем значения N_max для нескольких значении m.

m	1	2	3	4	5
Nmax	13	67	283	1093	4009

Из этой таблички следует, что для изготовления указанных в задаче разновесов из цепочек, состоящих, например, из 60 и 150 звеньев, достаточно разомкнуть не более двух и трех звеньев соответственно. Соотношения (3) и (6) позволяют определить номера этих звеньев: в 60-звенной цепочке необходимо разомкнуть 6-е и 22-е звенья, а в 150-звенной - 8-е, 30-е и 94-е. При этом из 60-звенной цепочки будут получены 5 разновесов, состоящих из 1, 1, 5, 15 и 38 звеньев, а из 150-звенной цепочки - 7 разновесов, в которых соответственно 1, 1, 1, 7, 21, 63 и 56 звена. Покажем, как при помощи разновесов, изготовленных из 60-звенной цепочки, на чашечных весах можно уравновесить груз, масса которого в граммах может принимать любое целочисленное значение между 22 и 38 (уравновешивание груза другой массы, допустимой в задаче, сложности не вызывает).
23 = 38 - 15
24 = 38 - 15 + 1
25 = 38 - 15 + 1 + 1
26 = 38 - 15 + 5 - 1 - 1
27 = 38 - 15 + 5 - 1
28 = 38 - 15 + 5
29 = 38 - 15 + 5 + 1
30 = 38 - 15 + 5 + 1 + 1
31 = 38 - 5 - 1 -1
32 = 38 - 5 - 1
33 = 38 - 5
34 = 38 - 5 + 1
35 = 38 - 5 + 1 + 1
36 = 38 - 1 - 1
37 = 38 - 1