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

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

Задачи на взвешивание — тип олимпиадных задач по математике, в которых требуется установить тот или иной факт (выделить фальшивую монету среди настоящих, отсортировать набор грузов по возрастанию веса и т. п.) посредством взвешивания на рычажных весах без циферблата. Чаще всего в качестве взвешиваемых объектов используются монеты. Реже имеется также набор гирек известной массы.

Очень часто используется постановка задачи, требующая определить либо минимальное число взвешиваний, потребное для установления определённого факта, либо привести алгоритм определения этого факта за определенное количество взвешиваний.

Реже встречается постановка, требующая ответить на вопрос, возможно ли установление определённого факта за некоторое количество взвешиваний. Часто такая постановка является не очень удачной, так как при положительном ответе на вопрос задача чаще всего сводится к построению алгоритма, а отрицательный почти не встречается в олимпиадной практике.

При решении задач на взвешивание часто совершается типичная ошибка: требуется определить минимальное количество взвешиваний. При решении строится алгоритм, который, позволяет решить задачу за N шагов. При этом N действительно является верным ответом на вопрос «каково минимальное количество взвешиваний», но этот факт в решении не доказан. Иногда эта ошибка допускается и самими составителями задач.

Анализ с точки зрения теории информации

При решении этих задач часто используется следующее соображение: весы могут пребывать в одном из тёх состояний

  • перевесила левая чашка
  • перевесила правая чашка
  • чашки находятся в равновесии

Таким образом, единственное взвешивание сообщает нам один разряд в троичной системе счисления, а N взвешиваний позволяют разделить не более чем 3^N различных ситуаций. Особенно это соображение полезно при доказательстве минимальности необходимого количества взвешиваний и при доказательстве невозможности определить некий факт за данное количество взвешиваний (в последнем случае обычно требуется комбинаторный анализ пространства возможных ответов).

Пример: за два взвешивания невозможно наверняка выделить самую тяжелую из 10 гирек, поскольку два взвешивания дают возможность разделить только 9 возможных ответов, а самой тяжёлой может оказаться любая из 10 гирек.

Знания о системах счислений не являются, вообще говоря, необходимыми; достаточно тривиального комбинаторного соображения типа «набор длины N, в каждом из которых m вариантов, даёт N^m комбинаций».

Иногда совершается ошибка, когда производятся вообще говоря правильные рассуждения, но упускается из виду «нейтральное» положение весов, и считается, что при каждом взвешивании сообщается один из двух, а не один из трёх возможных результатов.


«Нестандартные» задачи на взвешивание

Иногда встречаются «нестандартные» задачи на взвешивание, например:

  • в них фигурируют весы, непосредственно показывающие вес
  • в них фигурируют рычажные весы с циферблатом, показывающим разность веса грузов на чашах
  • в них фигурирует безмен
  • в них фигурируют неравноплечие весы

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Задачи на взвешивание" в других словарях:

  • Олимпиадные математические задачи — Олимпиадные задачи в математике  термин для обозначения круга задач, для решения которых обязательно требуется неожиданный и оригинальный подход. Содержание 1 Описание 2 Примеры 3 Типы задач …   Википедия

  • КОНСУЛЬТАЦИЯ — КОНСУЛЬТАЦИЯ. Содержание: Исторические данные ..............659 Структура К...................660 Методика работы ............■ . . 662 Консультация педагогическая..........664 Воздушно солнечная площадка К........667 Консультация для детей …   Большая медицинская энциклопедия

  • МЕТОДЫ ВРАЧЕБНОГО ИССЛЕДОВАНИЯ — І. Общие принципы врачебного исследования. Рост и углубление наших знаний, все большее, и большее техническое оснащение клиники, основанное на использовании новейших достижений физики, химии и техники, связанное с этим усложнение методов… …   Большая медицинская энциклопедия

  • Пористый кремний — (por Si или ПК)  кремний, испещренный порами, то есть имеющий пористую структуру. Содержание 1 История 2 Классификация 3 Получение …   Википедия

  • Автоматизация производства —         процесс в развитии машинного производства, при котором функции управления и контроля, ранее выполнявшиеся человеком, передаются приборам и автоматическим устройствам. А. п. основа развития современной промышленности, генеральное… …   Большая советская энциклопедия

  • АНАЛИТИЧЕСКАЯ ХИМИЯ — наука об определении хим. состава в в и, в нек рой степени, хим. строения соединений. А. х. развивает общие теоретич. основы хим. анализа, разрабатывает методы определения компонентов изучаемого образца, решает задачи анализа конкретных объектов …   Химическая энциклопедия

  • ОЦИФРОВКА КАЧЕСТВЕННЫХ ПРИЗНАКОВ — приписывание градациям признаков неких разумных в рамках решаемой задачи количественных значений, называемых метками. Как правило, оцифровка производится с целью дальнейшего использования статистич. методов, рассчитанных на количественные шкалы.… …   Российская социологическая энциклопедия

  • Земские учреждения — I образованы для заведования делами о местных пользах и нуждах губерний и уездов. Мысль о необходимости образования особых органов местного хозяйственно распорядительного управления возникла одновременно с составлением положений об освобождении… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Основные — 1.    Основные положения системы сельской телефонной связи. М., ЦНИИС, 1974. 145 с. Источник: Руководство: Руководство по проектированию сети электросвязи в сельской местности 16. Основные положения по учету труда и заработной платы в… …   Словарь-справочник терминов нормативно-технической документации

  • ГОСТ 7.73-96: Система стандартов по информации, библиотечному и издательскому делу. Поиск и распространение информации. Термины и определения — Терминология ГОСТ 7.73 96: Система стандартов по информации, библиотечному и издательскому делу. Поиск и распространение информации. Термины и определения оригинал документа: 3.2.5 автоматизированная информационно поисковая система: ИПС,… …   Словарь-справочник терминов нормативно-технической документации


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»