М. Мамикон
Многим читателям хорошо известна следующая классическая задача о фальшивых монетах, поражающая тем, что она разрешима:
Задача о мешке с фальшивыми монетами
Имеются 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–1 |
N–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.
Пример
В приводимой ниже таблице указаны веса монет, содержащихся в пяти мешках. Сверху дана нумерация мешков справа налево (это и есть обратный порядок), а под мешками указаны сорта монет. Они являются искомыми.
4 |
3 |
2 |
1 |
0 |
номер мешка j |
11 г |
12 г |
10 г |
12 г |
10 г |
содержимое мешка m + Δj |
1 |
2 |
0 |
2 |
0 |
сорт монеты Δj |
81 |
27 |
9 |
3 |
1 |
количество взятых монет 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 г.) рассматривается также случай двух мешков с фальшивыми монетами и приводится решение этой задачи при помощи двух взвешиваний.
Классическая задача о фальшивых монетах в последнее время нашла применение в теории кодирования и информации – для обнаружения ошибки в коде.
Другие работы по теме:
История банков и денег в Древнем Риме
Древнейшим общим эквивалентом у римлян при обмене был скот — быки и овцы. Кстати, слово «деньга» (pecunia) произошло от латинского «pecus» — «скот». Но это было неудобно, и ввели металлический эквивалент — медь и бронзу в слитках, которые измеряли по весу. Считается, что царь Сервий Туллий первым предложил делать знаки на весовых деньгах.
История банков и денег в Древнем Риме
Чеканка монет как важное государственное дело в Древнем Риме, ограны чеканки и виды монет: ауресы (золотая монета), денарии (серебренная), сестерции (бронзовая), допундции. Развитие банковского дела от меняльных контор до сложных финансовых операций.
Задача по Физике
С помощью принципа возможных перемещений (общего уравнения динамики) определить ускорение центра масс тела А. С помощью принципа Даламбера найти натяжение нити на всех участках. Рассмотрев динамическое равновесие последнего тела, сделать проверку правильности выполненных расчётов.
Медный бунт в Москве
Перед бунтом. Тайна древних сосудов. На Красном дворе. Фальшивые копейки. Клады медных денег.
Украинская символика
1.Вступ. 2.Українська державна символіка . 3.Висновок. ВСТУП Історія національно-визвольних рухів свідчить , що в моменти їхнього піднесення суспільна увага зосереджується на проблемі джерел історії та симантики національної символіки . Це цілком природно , бо національні символи - не випадкові значки і барви .
Задачи по теории вероятности 2
Работа №1 Случайные события 6 вариант. Задача 1.1. Бросают три монеты. Найти вероятность того, что только на двух монетах появится ''герб''. Исследуемое событие А – только на двух монетах из трех будет герб. У монеты две стороны, значит всего событий при бросании трех монет будет 8. В трех случаях только на двух монетах будет герб.
по Математическому анализу
Задача 1. Вычислить предел последовательности. Ответ: Задача 2. Вычислить предел последовательности. Ответ: 0 Задача 3. Вычислить предел последовательности.
Нумизматика
Основателем первого мюнцкабинета в России был Петр Великий , купивший в 1721 г. в Гамбурге нумизматическое собрание Модерса (см. Минцкабинеты) для кунсткамеры. Скоро после того было напечатано академиком Байером и первое нумизматическое сочинение.
Герб
Слово «герб» происходит от немецкого «эрбе» — наследство. Гербом называют изображение, которое в условной форме показывает исторические традиции государства или города.
Ратушная, Лариса Степановна
Лариса Степановна Ратушная (Ляля Ратушная) (9 января 1921, Тывров, Винницкая область — 18 марта 1944, Винница) — советская подпольщица, Герой Советского Союза (1965, посмертно).
Княжеский камень
Введение 1 Интронизационный церемониал 2 Исторические тени Список литературы Введение Княжеский камень (нем. Fьrstenstein; слов. Knežji kamen) — перевёрнутое основание античной ионической колонны из Цолльфельдской долины, которое играло ключевую роль в церемониале венчания на престол герцогов Каринтии и, предположительно, правителей одного из самых ранних славянских государств — Карантании.
Пенни Финляндия
Введение 1 История и описание Список литературы Введение Пенни (фин. penni, p) — в прошлом производная денежная единица и разменная монета Финляндии достоинством в одну сотую финской марки[1] с 1860-х годов XIX века до перехода страны на Евро с 1 января 2002 года.
Аврелий Валерий Валент
(Валент I, лат. Aurelius Valerius Valens, ?-317 г.) — римский император с конца 316 года по 1 марта 317 года. Единственное, что известно об этом человеке до его прихода к власти — что он был командующем на границе (лат. dux limitanis) в Дакии[1] (которая в то время контролировалась Лицинием). После того как во время первой своей войны с Константином I Лициний потерпел сокрушительное поражение в битве при Цибале 8 октября 316 года[2] (некоторые исследователи её относили к 314 г.[3]), он бежал к Адрианополю, где с помощью Валента собрал новую армию.
Куджула Кадфиз
Монета Куджулы Кадфиза в римском стиле, легенда на кущанском: ΚΟΖΟΛΑ ΚΑΔΑΦΕϹ ΧΟϷΑΝΟΥ ΖΑΟΟΥ («Kozola Kadaphes Koshanou Zaoou»): «Кудхуда Кадфиз, правитель Кушан».
Характеристика священного символа Германии
вященный символ Германии Орел На гербе Федеративной Республики Германия изображен орел. Эта птица прославлялась людьми с древнейших времен. Орел был символом мужества, жизненной силы и солнца. Он был тотемным символом многих древних племен и народов. Даже отдельные органы орла использовались в качестве торжественных украшений.
Privilegium Maius
Введение 1 Предпосылки 2 Состав 3 План Введение 4 Значение Введение «Privilegium Maius» (лат. Большая привилегия; 1358) — сборник фальшивых писем и указов императоров Римской и Священной Римской империй, предоставляющих особые права монархам Австрии и закрепляющих фактическую независимость австрийского государства от Германии.
Индо-римская торговля
первоначально осуществлялась сухопутными путями через Анатолию и Персию, что существенно ограничивало её объём. До римского завоевания Египта монополией на морскую торговлю обладали Птолемеи. Присоединение Августом Египта активизировало торговые и культурные контакты Древнего Рима с Индией.
Канишка I
(на кушанском языке: ΚΑΝΗϷΚΙ, древнекитайское 迦腻色伽) — наиболее известный царь Кушана, правивший в начале II века н. э. При Канишке Кушанское царство достигло апогея своего развития, превратившись в крупную империю со столицей в Пешаваре (древнее название города — Пурушапура), включающую значительную часть Средней Азии (Бактрия и юго-восток Согдианы с Бухарой и Самаркандом), Ферганскую долину, часть Восточного Туркестана (бассейн Тарима, современный Синьцзян-Уйгурский автономный район КНР с Яркендом, Хотаном и Кашгаром), современные Афганистан и Пакистан, а также северную Индию.
Герб Российской республики
Государственный герб Российской республики — официальная эмблема России (с 14 сентября — Российской республики) с 21 марта 1917 года до 10 июля 1918 года . Эскиз герба был разработан группой специалистов, в которую входили известные геральдисты и художники Владислав Лукомский, Сергей Тройницкий, Георгий Нарбут и Иван Билибин.
Банкивская джунглевая курица
План Введение 1 Внешний вид 2 Распространение 3 Образ жизни 4 Человек и банкивская джунглевая курица 5 Прмечания Введение Ба́нкивская джу́нглевая ку́рица[1] (Gallus gallus; ранее — лат. Gallus bankiva), — центральный вид в роде джунглевых кур, (Gallus) и в отряде курообразных (Galliformes), дико живущий в Юго-Восточной Азии, от которого, вероятно, происходят домашние куры.
Стальная корона Румынии
Стальная корона королевства Румынии — румынская королевская регалия. Корона была отлита в Бухаресте из стали трофейной турецкой пушки, захваченной румынами во время войны за независимость против Османской империи (1877—1878) во время битвы под Гривицей 30 августа 1877 года.
Знаки Рюриковичей
План Введение 1 Письменные источники 2 Изображения княжеских знаков 3 Происхождение 4 Закат личных княжеских знаков 5 Литовский след 6 Современное использование
Филипп Младший
Марк Юлий Север Филипп [1], Филипп II или Филипп Младший (лат. Marcus Iulius Severus Philippus, 237(8)—249) — сын и соправитель римского императора Филиппа Араба. Его матерью была Марция Отацилия Севера, происходившая из знатного рода Отацилиев, в то время как отец был происхождения низкого и к тому же варвар.
Отражение культа Геракла в монетном деле Херсонеса
Нумизматический материал представляет собой одну из важнейших категорий источников по культу Геракла в Херсонесе. Так, монеты характеризуют политический, религиозно-идеологический, художественный аспекты истории Херсонесского государства.
Сакральная иконография византийских монет
Евангельский сюжет, решивший вопрос о правах мирской власти ссылкой на "денарий кесаря" - монету с именем и ликом римского принцепса и поэтому принадлежащую ему, тем самым сделался моделью, по которой можно было отмерять отпущенное Богом земному владыке.
Последние шаги в преобразовании Римской Империи
Последним шагом в преобразовании Римского государства стал эдикт императора Каракаллы. В 212 г. он распространил римское гражданство на всё население империи с одновременной обязанностью уплаты налогов.
Войнаровская, Ванда-Цезарина Константиновна
Ванда-Цезарина Константиновна Войнаровская (польск. Wanda Cezaryna Wojnarowska, 1 мая 1861, Каменец-Подольский — 15 апреля 1911, Париж) — польская социалистка, участница российского, польского и французского революционного движения.
Деньги России в 1920 1930-х гг.
Муниципальное общеобразовательное учреждение № 70. Реферат по истории на тему: Деньги России в 1920 – 1930-х гг. Выполнили: Новосёлова Т. Суслова Н. Суплотова Т.
Золото
Золото (лат. Aurum), Аu, химический элемент I группы периодической системы, атомный номер 79, атомная масса 196,9665.