Читать статья по математике: "Обобщённая задача о фальшивых монетах" Страница 2


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

содержит монеты веса 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 – 1k – 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 существует несколько отличная от нашей интерпретация решения задачи. Найти её мы предоставляем читателю.

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

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



Интересная статья: Основы написания курсовой работы