Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


Обобщённая задача о фальшивых монетах

Тип Реферат
Предмет Математика
Просмотров
955
Размер файла
17 б
Поделиться

Ознакомительный фрагмент работы:

Обобщённая задача о фальшивых монетах

М. Мамикон

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

Задача о мешке с фальшивыми монетами

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

Вот как решается эта задача. Мешки последовательно нумеруются и из каждого мешка берется количество монет, равное номеру этого мешка. Суммарный вес всех взятых таким образом монет будет «не дотягивать» до веса такого же количества нормальных монет (который нам известен) на количество граммов, равное номеру именно того мешка, который содержит фальшивые монеты. (Эта задача решается – правда, хитрее – и в том случае, когда вес нормальной монеты неизвестен и разновесков нет. Подумайте, как.)

Раздумывая над этой задачей, я пришёл к более удивительному выводу о том, что одним взвешиванием может быть решена и более сложная задача:

Задача о нескольких мешках с фальшивыми монетами

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

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

Задача о мешках с тяжёлыми и лёгкими монетами

Среди N мешков имеются некоторое (неизвестное) количество мешков с тяжёлыми и некоторое (тоже неизвестное) количество мешков с лёгкими монетами. Лёгкая монета на 1 г легче нормальной, а тяжёлая, наоборот, на 1 г тяжелее нормальной. Требуется при помощи одного взвешивания на весах с разновесками узнать, какие мешки содержат нормальные монеты, какие – тяжёлые, а какие – лёгкие. (Напомним, что внутри данного мешка все монеты одинакового веса и что вес нормальной монеты известен.)

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

Задача о мешках с разносортными монетами

Пусть имеются N мешков и в каждом достаточное количество монет. Имеются монеты разных сортов, но в каждом мешке содержатся монеты только одного сорта. Количество мешков с монетами данного сорта произвольное, и нам оно неизвестно. Монеты разных сортов отличаются друг от друга по весу, причём на целое число граммов. Вес монеты каждого сорта нам известен. Требуется при помощи одного взвешивания на весах с разновесками определить, к какому сорту принадлежат монеты в каждом мешке.

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

Решение задачи о мешках с разносортными монетами

Перенумеруем последовательно мешки от 0 до N – 1. Обозначим вес самой лёгкой монеты через m. Пусть мешок под номером j содержит монеты веса m + Δj, то есть Δj определяет сорт монеты в j-м мешке. Пусть в зависимости от сорта монеты величины Δ могут принимать (целые) значения 0, 1, 2, ..., меньшие k, то есть количество сортов монет равно k.

Теперь возьмем из мешка с номером j количество монет, равное k j, то есть из первого мешка – одну монету, из второго – k, ..., из последнего – kN–1 монет. Всего взятых монет будет

N–1
M =k j = 1 + k + k2 + ... + kN–1 =

kN – 1

k – 1

.
j=0

Их суммарный вес S на весах будет равен

N–1N–1
S =(m + Δj )k j = m·M +Δj k j.
j=0 j=0

Поскольку всегда Δj < k, вторая сумма в правой части

N–1
Δ =Δj k j = Δ0 + Δ1 k + Δ2 k2 + ... + ΔN–1kN–1
j=0

представляет собой перевод числа Δ из десятичной системы счисления (в которой работают весы) в систему счисления с основанием, равным k. В этой системе Δ записывается в виде числа со следующей последовательностью цифр:

Δ → ΔN–1 ΔN–2 ... Δ2 Δ1 Δ0.
(*)

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

Итак, из суммарного веса S всех выбранных M монет вычитаем величину Mm – вес того же количества монет наилегчайшего сорта и оставшееся число Δ = S – Mm переводим в систему счисления с основанием k (разлагаем по степеням k, начиная со старшей). Тогда мы получим число вида (*). Его j-я цифра с конца (счёт ведётся от нуля) показывает сорт монеты Δj в мешке под номером j.

Пример

В приводимой ниже таблице указаны веса монет, содержащихся в пяти мешках. Сверху дана нумерация мешков справа налево (это и есть обратный порядок), а под мешками указаны сорта монет. Они являются искомыми.

43210 номер мешка j
11 г 12 г 10 г 12 г 10 г содержимое мешка m + Δj
12020 сорт монеты Δj
8127931 количество взятых монет kj

В этом случае k = 3 и количество взятых монет соответствует степеням тройки, как показано в последней строчке таблицы. Всего мы взяли M = 121 монету. Их общий вес на весах будет равен S = 1351 г. Вычитая величину M·m = 121·10, получим Δ = 141 г. Переводя Δ в троичную систему

Δ = 1·34 + 2·33 + 0·32 + 2·31 + 0·30,

получим число 12020, последовательность цифр которого совпадает с исходной последовательностью сортов, приведённой в таблице.

Если k = 10, то надобность перевода Δ из одной системы счисления в другую отпадает. Для случая k = 3 существует несколько отличная от нашей интерпретация решения задачи. Найти её мы предоставляем читателю.

Немного истории

Классическую задачу об одном мешке с фальшивыми монетами можно найти во многих популярных книжках по математике. Говорят, что во время второй мировой войны англичане «сбросили» эту задачу над немецкими солдатами с целью их дезорганизации и что те потеряли над её решением более 40 000 человеко-часов.

В книге Д. Бизама и Я. Герцега «Многоцветная логика» (М., «Мир», 1978 г.) рассматривается также случай двух мешков с фальшивыми монетами и приводится решение этой задачи при помощи двух взвешиваний.

Классическая задача о фальшивых монетах в последнее время нашла применение в теории кодирования и информации – для обнаружения ошибки в коде.


Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
142365
рейтинг
icon
3069
работ сдано
icon
1329
отзывов
avatar
Математика
Физика
История
icon
140128
рейтинг
icon
5849
работ сдано
icon
2647
отзывов
avatar
Химия
Экономика
Биология
icon
94278
рейтинг
icon
2018
работ сдано
icon
1266
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
52 793 оценки star star star star star
среднее 4.9 из 5
ЧКИ РУК
Реферат был сделан очень быстро, буквально за 5-10 минут. Работа была с антиплагиатом, всё...
star star star star star
Самгупс
Конечно текст был чисто из учебников, но приняли хотя бы и на этом хорошо, рада.
star star star star star
Московская международная академия
Работа сделана хорошо, очень высокая оригинальность, рекомендую исполнителя
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Написать доклад на тему "Принципы организации защищенного документооборота"

Доклад, информационная безопасность

Срок сдачи к 27 мая

только что

задачи

Решение задач, Химия

Срок сдачи к 25 мая

только что

Схема автогенератора с чм

Лабораторная, Радиопередающие устройства, электроника

Срок сдачи к 27 мая

1 минуту назад

Электродинамика

Решение задач, Физика

Срок сдачи к 30 мая

2 минуты назад

КР состоит из 5 разделов

Контрольная, Производственная стратегия, экономика

Срок сдачи к 28 мая

2 минуты назад
2 минуты назад

Расчетные упражнения

Другое, Микроэкономика

Срок сдачи к 31 мая

3 минуты назад

Доработать ВКР

Диплом, безопасность жизнедеятельности

Срок сдачи к 29 мая

3 минуты назад

Правоспособность и дееспособность субъектов...

Курсовая, Теория государства и права

Срок сдачи к 27 мая

3 минуты назад
3 минуты назад

Эссе по литературе

Эссе, Литература

Срок сдачи к 24 мая

3 минуты назад

Выбор системы элементов схемотехнического устройства

Лабораторная, Схемотехника

Срок сдачи к 31 мая

3 минуты назад

"Разработка электронной картотеки" Создать электронную картотеку

Курсовая, программирование на СИ

Срок сдачи к 28 мая

3 минуты назад

помочь и объяснить задания по лабораторным работам

Онлайн-помощь, параллельные методы и алгоритмы, математика

Срок сдачи к 27 мая

4 минуты назад

Курсовая

Курсовая, Веб дизайн

Срок сдачи к 27 мая

4 минуты назад

Ответить на вопросы и решить задачи кратко

Решение задач, административное право

Срок сдачи к 24 мая

4 минуты назад

Электродинамика

Решение задач, Физика

Срок сдачи к 30 мая

4 минуты назад

Пройти тест по английскому

Тест дистанционно, Английский язык

Срок сдачи к 25 мая

5 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно