Задача 98259

Темы:    [ Взвешивания ] [ Троичная система счисления ]

Сложность: 4+ Классы: 7,8,9,10

Условие

Автор: Толпыго А.К.

Геологи взяли в экспедицию 80 банок консервов, веса которых все известны и различны (имеется список). Через некоторое время надписи на консервах стали нечитаемыми, и только завхоз знает, где что. Он может это всем доказать (то есть обосновать, что в какой банке находится), не вскрывая консервов и пользуясь только сохранившимся списком и двухчашечными весами со стрелкой, показывающей разницу весов.
Докажите, что для этой цели ему
  а) достаточно четырёх взвешиваний и
  б) недостаточно трёх.

Решение

  а) Для простоты рассуждений мысленно добавим одну пустую банку (массой 0). Первое взвешивание завхоз организует так: на одну чашку кладёт 27 самых тяжёлых банок, а на другую – 27 самых лёгких. Получается разность, наибольшая из всех возможных. Остальные члены экспедиции должны признать, что разбиение на три группы проведено правильно (27 самых лёгких, 27 средних и 27 самых тяжёлых). Завхоз помечает банки буквами "т", "с" и "л".
  Второе взвешивание и последующие организуются аналогичным образом. Пусть банки после k-го взвешивания разбиты уже на 3^k групп по 3^4–k банок, помеченных некоторым k-буквенным словом из букв "т", "с" и "л". Из каждой группы берётся треть самых тяжёлых и треть самых лёгких; тяжёлые кладутся на одну чашу весов, лёгкие – на другую. В результате каждая треть каждой группы определяется однозначно и образует группу следующего ранга, а банки помечаются ещё одной (k+1)-й буквой "т", "c" или "л".
  После четвёртого взвешивания группы будут состоять из одной банки; при этом все банки помечаются словом из четырёх букв. Четвёрка букв однозначно указывает, с какой банкой мы имеем дело, и задача завхоза решена.

  б) Пусть проведено три взвешивания. Каждая банка при первом взвешивании либо оказалась на той чашке весов, которая перевесила, либо более лёгкой, либо находилась в стороне. В зависимости от этого пометим банку одной из букв "т", "с", "л" ("с" означает, что банка не взвешивалась). Аналогичным образом, ставим эти буквы в результате второго и третьего взвешиваний. Слов из трёх букв всего 27, а банок – 80. Значит, найдутся по меньшей мере две банки с одинаковой маркировкой. Это означает, что мы не получили никаких сведений, которые позволяют различить эти две банки между собой, так что трёх взвешиваний недостаточно.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Номер	16
Дата	1994/1995
вариант
Вариант	весенний тур, основной вариант, 8-9 класс
Задача
Номер	7
журнал
Название	"Квант"
год
Год	1995
выпуск
Номер	4
Задача
Номер	М1508
олимпиада
Название	Московская математическая олимпиада
год
Номер	58
Год	1995
вариант
Класс	9
задача
Номер	6