ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98259
Темы:    [ Взвешивания ]
[ Троичная система счисления ]
Сложность: 4+
Классы: 7,8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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

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

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .