Реферати українською » Математика » Узагальнена задача про фальшиві монетах


Реферат Узагальнена задача про фальшиві монетах

М.Мамикон

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

Завдання про мішку з фальшивими монетами

Є 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

Їх сумарна вага P.S на терезах дорівнюватиме

>N–1 >N–1
P.S = (>m +j )>k j =m·M + >jk j.
>j=0 >j=0

Оскільки завждиj <k, друга сума правій частині

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

є переклад числа з десяткової системи числення (у якій працюють ваги) до системи числення з повним правом, рівнимk. У цьому системі записується як числа з такою послідовністю цифр:

> >N–1N–2 ...210 .
(*)

Ми, кожна цифра цього запису показує сорт монети в послідовності мішків, взятої у зворотному напрямку. У цьому полягає суть нашого рішення.

Отже, з сумарного ваги P.S всіх вибраних M монет віднімаємо величинуMm – вагу тієї самої кількості монетнаилегчайшего сорти і що залишилося число = P.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 монету. Сукупний їх вагу на терезах дорівнюватиме P.S = 1351 р.Вичитая величинуM·m = 121·10, одержимо = 141 р. Перекладаючи втроичную систему

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

одержимо число 12020, послідовність цифр якого збігаються з вихідної послідовністю сортів,приведенной в таблиці.

Якщоk = 10, то потреба перекладу з однієї системи числення до іншої відпадає. Для випадкуk = 3 є кілька яка від нашої інтерпретація виконання завдання. Знайти її надаємо читачеві.

Трохи історії

>Классическую завдання про один мішку з фальшивими монетами можна знайти в багатьох популярних книжках з математики. Кажуть, що під час Другої світової війни англійці «скинули» це завдання над німецькими солдатами з метою їхнього дезорганізації І що ті втратили над її рішенням понад 40000 людино-годин.

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

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


Схожі реферати:

  • Реферат на тему: Сузір'я Стрілець
    Спостерігаючи галактики, подібні за будовою з нашої зоряної системою, ми переконуємося, що їх
  • Реферат на тему: * Алгебри та їх застосування
    Дипломна робота фахівця Таврійський національний університет ім. В.І. Вернадського Сімферополь 2003
  • Реферат на тему: Сузір'я Центавр
    Чи давно мореплавці користуються картами за зоряним небом? Принаймні, аргонавти мали таку карту,
  • Реферат на тему: Чарівний світ Пуанкаре
    Люди звикли, що геометрія оперує нашим реальним простором І що простір описується евклідовій
  • Реферат на тему: Сузір'я Змія, Змієносець
    Змія Як зазначалося, сузір'я Змії і двох які пов'язані між собою частин. Західна частина

Навігація