У короля есть 10 больших мешков с золотыми монетами. В девяти из них монеты настоящие и весят по 2 г каждая, а в одном фальшивые весом 1 г каждая. У короля есть Королевские Весы с одной чашей, которые точно показывают вес в граммах. Как за 1 взвешивание определить мешок с фальшивками?

задан 28 Окт 12:06

3

Возьмите разное количество монет из каждого мешка и взвесьте. По величине недостачи и определите мешок с фальшивыми монетами

(28 Окт 12:12) spades
2

Есть ещё способ взять одну монету, 10 монет, 100 монет, и так далее. После взвешивания получится что-то типа 22212. Тогда сразу всё станет ясно. Но вообще-то здесь можно и меньшим количеством ограничиться.

(28 Окт 12:17) falcao

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

(28 Окт 12:25) spades

@spades: да, я с Вами согласен. Просто решил напомнить один приём, который в задачах такого типа бывает полезен. Ваш план с меньшим количеством монет тут явно лучше. А наименьшее количество тут, наверное, равно 0+1+...+9. Число монет везде разное, и тогда это наименьшая сумма.

(28 Окт 13:13) falcao

@falcao не. интересен вопрос о наименьшем числе монет при вашем способе, который позволяет определить сразу несколько мешков. К примеру берем из i-ого мешка по 3^i монет. Но это число не минимально. Теоретический минимум это 2^n-1

(28 Окт 13:28) abc

Погуглите об этом по словам "последовательность Конвея-Гая". Или по-английски. Еще помогает subset sum distinct problem

(28 Окт 13:41) knop

@knop, Conway-Guy sequence показывает минимум(?) максимального элемента множества с уникальными суммами подмножеств. Я же подразумевал минимум суммы элементов таких множеств. И да, он меньше 2^n -1

(28 Окт 14:24) spades
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×228
×165
×27

задан
28 Окт 12:06

показан
49 раз

обновлен
28 Окт 14:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru