|
|
 |
Условие
На витрине ювелирного магазина лежат 15 бриллиантов. Рядом с ними стоят таблички с указанием масс, на которых написано 1, 2, ..., 15 карат. У продавца есть чашечные весы и четыре гирьки массами 1, 2, 4 и 8 карат. Покупателю разрешается только один тип взвешиваний: положить один из бриллиантов на одну чашу весов, а гирьки — на другую и убедиться, что масса на соответствующей табличке указана верно. Однако за каждую взятую гирьку нужно заплатить продавцу 100 монет. Если гирька снимается с весов и в следующем взвешивании не участвует, продавец забирает её. Какую наименьшую сумму придётся заплатить, чтобы проверить массы всех бриллиантов?Решение
Пример.
| Какие гири покупаем | Что взвешиваем | Сколько монет мы заплатили |
|---|---|---|
| 1 | 1=1 | 100 |
| 2 | 1+2=3, 2=2 | 200 |
| 4 | 2+4=6 | 300 |
| 1 | 1+2+4=7, 1+4=5, 4=4 | 400 |
| 8 | 4+8=12 | 500 |
| 1 | 1+4+8=13 | 600 |
| 2 | 1+2+4+8=15, 2+4+8=14, 2+8=10 | 700 |
| 1 | 1+2+8=11, 1+8=9, 8=8 | 800 |
Оценка. Переходя к каждому взвешиванию, мы либо покупаем одну или несколько гирек, либо отдаём их продавцу. Поэтому мы в сумме купили и отдали N≥15 гирек. При этом после последнего взвешивания у нас на руках есть хотя бы одна гирька, так что мы купили больше, чем отдали. Это значит, что мы купили более половины от N, т. е. как минимум 8 гирек, а значит, заплатили жадному продавцу не менее 800 монет.
Оценка (другой способ.) Представим себе, что плата за каждую гирьку разделена на две части: 50 монет покупатель платит, когда берёт гирьку, а ещё 50 — когда отдаёт. Если считать, что в конце все гирьки возвращаются продавцу, то при таком способе расчёта суммарная плата не изменится.
Рассмотрим 16 моментов: начало, когда покупатель берёт первые гирьки, 14 интервалов между взвешиваниями, и конец, когда покупатель отдаёт оставшиеся гирьки. В каждый из этих моментов покупатель производит какое-нибудь действие (что-то берёт или что-то отдаёт), поэтому должен заплатить не менее 50 монет, а всего ему придётся заплатить не менее 50·16 = 800 монет.
Комментарий. Из решения видно, что оптимальный порядок взвешивания перебирает все возможные наборы гирек, причём соседние наборы отличаются добавлением или удалением ровно одной гирьки. Такая последовательность наборов называется кодом Грея.
Зачем были придуманы коды Грея? Представьте себе, что нам почему-то хочется знать положение вращающегося диска. Если его хочется знать совсем приблизительно, то можно покрасить одну половину диска в чёрный цвет, а другую в белый и поставить фотодатчик. Теперь мы всегда знаем, какой половиной диск повёрнут к датчику.
Но пусть мы хотим большей точности. Можно поставить несколько фотодатчиков и покрасить на диске несколько колец, а в каждом секторе написать его номер чёрными и белыми полосами как двоичным кодом (см. рис. слева).
Но тогда на границе секторов датчики могут сработать не совсем одновременно, и между 001 и 010 мы «увидим» 011 или 000. Для такой ситуации и были придуманы коды Грея: если на границе двух секторов меняется цвет только одного из колец, то в любом случае получить можно только код одного из этих секторов.
Любое оптимальное решение задачи оказывается кодом Грея
для 4 колец и 16 секторов (на рис. справа использован код Грея
из решения задачи).
