задачка

[109]

ну что, теперь моя очередь задачки задавать :-)

первая - простая.

имеется десять сундуков с монетами. в каких-то сундуках лежат только фальшивые монеты, в каких-то - только настоящие. настоящая монета весит 10 грамм, фальшивая - 9. требуется за одно взвешивание сказать, в каких сундуках лежат фальшивые, а в каких - настоящие.

я даже дам подсказку: сначала найдите решение для случая если только один сундук фальшивый.

комменты будут временно скриниться, чтобы первый правильно ответивший не испортил остальным удовольствие.

Update: ответили правильно (в порядке поступления ответов):

untimed pesec bacek

у вас ещё есть шанс попасть в десятку! уже нет :-)

Update #2: приём ответов на эту задачу закончен! то ли все такие умные, то ли слишком понятно сформулировал :-)

сейчас расскриню все комменты.

Comments

[ex-zadoff59.livejournal.com]

гыгы.

шаг номер один - релятивизируем понятие "одно взвешивание"

[109.livejournal.com]

ты хотел сказать - дефинируем?

взвешивание есть помещение объекта на весы и считывание численного значения его веса с индикатора.

[some41.livejournal.com]

если только в одном, то тривиально - из суднука номер N кладем на весы N монет. отличае общего веса от 10*10 и даст нам номер сундука.

если сундуков больше, то нужно класть на N, а N^M монет, где M > 2. теорема Ферма должна спасти нас от коллизий.

[109.livejournal.com]

теорема Ферма поможет, если только два сундука. про a^m + b^m + c^m теорема ничего не говорит.

[name-fa.livejournal.com]

А что взвешивать-то полагается? Сундуки или монеты?

[109.livejournal.com]

а что хочешь. хочешь - сундуки, а хочешь - монеты. но взвешивание только одно.

[alexf.livejournal.com]

Если в одном сундуке лежит 10 фальшивых монет, а в другом 9 настоящих, то путём взвешивания сундуков их не различить даже за миллион взвещиваний. То есть ответ для интервью - задача не решаема. :)

[109.livejournal.com]

ответ неверный. как минимум испытуемый должен спросить, разрешается ли монеты из сундуков вынимать (да, разрешается). а более смышлёный и так догадается, спрашивать не станет :-Р

[meet.livejournal.com]

скрининг зря

[109.livejournal.com]

чтобы первый правильно ответивший не испортил остальным удовольствие.

[109.livejournal.com]

мнэ... в партии не дураки сидят, сундуки - открытые!

[wind-bbc.livejournal.com]

если один ящик, то брать из первого ящика - одну монету, из второго - две монеты, из третьего - три и т.д. потом все взвесить и по разнице будет понятно, где лежат фальшивые.
если ящик с фальшивыми не один, то увеличим порядок: из первого - одну, из второго - двадцать, из третьего - триста и т.д. утомиться, но можно определить за одно взвешивание.
вроде так)
спасибо за интересную задачу)

[109.livejournal.com]

верно! только двадцать и триста - это перебор. достаточно 1, 2, 4...

[karaidel.livejournal.com]

Всё просто. Если фальшивый сундук один, то берётся из первого сундука одна монета, из второго - две, из третьего - три и так далее. Все вместе взвешиваются. Это 55 монет. Если бы все они были настоящими - они бы весили 550 грамм. Но поскольку один сундук с фальшивыми монетами, вес будет меньше. Разница и есть номер фальшивого сундука.
Если таких сундуков несколько, задача тоже решается за одно взвешивание. Из первого сундука берётся одна монета, из второго - две, из тертьего - четыре и так далее, по степеням двойки. Разница в весе (сейчас "идеальным" весом было бы 10230 граммов) в двоичном представлении укажет на все фальшивые сундуки.

[109.livejournal.com]

верно!

[navy-99.livejournal.com]

из первого 1 монету,и з второго 2, из 3его - 3.Итд. Из десятого - ноль. По суммарному весу теперь легко определить

[109.livejournal.com]

это если один. а если несколько с фальшивыми?

:)

[alexis-m.livejournal.com]

Вынимать из каждого сундука по монете и взвешивать на точных весах. :)

Re: :)

[109.livejournal.com]

за одно взвешивание надо.

[dpak0h.livejournal.com]

вообще-то это самая обычкновенная математическая задачка для школьника 6-7 класса.

[109.livejournal.com]

ат-лично. а где решение?

[honeyman.livejournal.com]

Что взвешиваем вообще? Сундуки? - тогда, скорее всего, решить нереально. Монеты, случайно выбранные из сундуков (выбираем сами)? - тогда чрезвычайно простая задача. Сундуки и эталонные гирьки?

[109.livejournal.com]

монеты, сами выбираем из сундуков. пишите решение, если есть.

[dmierkin.livejournal.com]

мне позавчера на работе задавали. решил !
из первого сундука берём 1 монету, из второго - 2, и т.д. взвешиваем, получаем А. отнимаем от предполагаемой "правильной" суммы, получаем номер ящика.

[109.livejournal.com]

гы, это облегчённый вариант, для первоклассников :-)

как насчёт оригинальной задачи, где произвольное количество фальшивых сундуков?

[zfog.livejournal.com]

не понял. всего взвешивание сколько ? одно вообще ? или для каждого сундука одно ?

[109.livejournal.com]

вообще одно. взвешивать можно монеты, не обязательно сундуки :-)

[realloc.livejournal.com]

Берём из первого N моенток, их второго N-1 и так далее до 1. По разнице в весе от идеального варианта узнаем номер сундука в виде разницы в весе.

[109.livejournal.com]

а теперь для случая нескольких фальшивых сундуков!

[dimfin.livejournal.com]

поскольку сундуков всего десять, то можно поступить так: взять из сундука n 2^(n-1) монет. И взвесить их общий вес. Поскольку фальшивая монета на 1 грам легче общий вес будет меньше чем вес такого же количества настоящих монет на сумму степеней двойки. Зная показатели при степенях, определить сугдуки с фальшивыми монетами не представляет труда.

[109.livejournal.com]

верно!

[the-white-man.livejournal.com]

Ну берем 1, 2, 4,...,2^N монеток из каждого сундука, взвешиваем и раскладываем полученное число в бинарное ...

[109.livejournal.com]

ну, не само число, а разницу между... но идея правильная, и это главное!

[upstartn.livejournal.com]

Довольно просто, но не уверен, что во всех сундуках хватит монет.
Из первого сундука берем одну монету, из второго - 10, ..., из N-того 10^N-1 монет.
Соответственно после взвешивания мы получим некоророе число каждая цифра десятичного представления которого показывает, есть ли в соответствующем сундуке фальшивые монеты

[109.livejournal.com]

да! именно так и я решил. на самом деле, достаточно степеней двойки: 1, 2, 4...

[fatb0y.livejournal.com]

Боюсь сморозить глупость, но по-моему, если брать не n, а 2^n монет из каждого сундучка, то по разнице в весе можно будет определить какие сундучки фальшивые аналогично упрощенному варианту задачи, т.к. каждой разнице будет соответствовать уникальная комбинация сундучков. Сморозил?

[109.livejournal.com]

ответ верный! начинать можно и с нуля, и с единицы, не принципиально.

[fatb0y.livejournal.com]

к предыдущему ответу: сундучки нумеруем с ноля, или если с единицы, то берем 2^(n-1).

[puzanov.livejournal.com]

Из каждой кучики монет требуется взять именно столько, какой порядковый номер у кучи, то есть по номеру кучи - из первой одну, из второй две и так далее.

Если бы фальшивых монет не было, то вес составил 550 грамм. А так он будет меньше, причем разница в весе покажет нам номер кучки (разница 1 Гр).

[109.livejournal.com]

это решение вспомогательной задачи. а основной?

[am-baal.livejournal.com]

Брать из каждого сундука простое число монет, затем см. задачу с одним фальшивым сундуком ?

[109.livejournal.com]

и что нам даст сумма нескольких простых чисел?

[untimed.livejournal.com]

1+2+4+8+16+32+64+128+256+512 монет из сундуков. Если во всех сундаках монеты настоящие, то получится 1023*10, если в первом фальшивые - 1023*10-1, если в пятом - 1023*10-16, в общем разницу между 1023*10 и полученной массой раскладываем по двоичным разрядам...

[109.livejournal.com]

верно!

[raa.livejournal.com]

считаем, что монет в сундуке>2**9 ;) тогда из n-го сундука берем 2**(n-1). методом пристального всматривания в двоичное представление разницы преполагаемого и получившегося весов находим ответ.

[109.livejournal.com]

верно!

[drneo.livejournal.com]

Когда несколько фальшивых сундуков, то надо брать из первого - 1 монету, из второго - 2, из третьего - 4, 8, 16, 32, и т.д. - степени двойки. Тогда не будет пересечения сумм масс любого количества любых подмножеств кучек монет, достанных из разных сундуков.

[109.livejournal.com]

верно!