Задачи на логику — Кин-дза-дза!

Господин ПЖ · : 22-08-2007, 17:33 Тема: Задачи на логику

Есть 12 монет. Среди них одна фальшивая. Все монеты одинаковые с виду (все 12) и вес 11 монет одинаков, а вот 12 монета отличается по весу неизвестно в какую сторону.
Как за 3 взвешивания с помощью рычажных весов выявить фальшивую?

Дарья · : 01-04-2008, 00:13 Тема:

2 монеты откладываем в сторону, остается 10 монет, далее делим 10 монет на 2 кучки, после чего взвешиваем их, в результате получаем:
1. если они равны, то монета находится в тех, двух, которые мы отложили, производим взвешивание 2 монет и вычисляем какая из них фальшивая
2. если одна кучка весит меньше другой, у нас 5 монет, и 2 попытки. одну монету откладываем в сторону, взвешиваем по 2 монеты, если одинаково весят, то значит отложенная монета и есть фальшивая.. если одна из них весит меньше.. путем 3 попытки, взвешиваем оставшиеся 2 монеты и вычисляем фальшивую монету.

Господин ПЖ · : 01-04-2008, 09:28 Тема:

Дарья

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

Пришелец Прораб · : 08-05-2008, 17:07 Тема:

Господин ПЖ,ку.Такой вариант: берётся 6 монет на одну чашу ложатся 3 и на другую три, если какая-нибудь перевешивает
значит та монета которую мы ищем в этой шестерки,иначе в другой.Потом из той 6 где мы выивили монету берется 3 монеты
и берется 3 монеты из той 6 в которой все монеты равны,сравнивается и из этого мы можем сделать два вывода:
1)если опять неравенство на весах то монета в этой 3 или же в другой.
2)мы узнаем точно в какую сторону отличается монета так как эта тройка либо перевесит либо наоборот.Соответсвенно монета либо тяжелее либо легче.
А дальше ваще просто есть 3 монеты и последняя попытка и мы знаем например што монета оказалась тяжелее.Сравниваются две из этой тройки находиться тяжелая либо они равны значит это та монета которую мы не сравнивали.Спасибо за вниманию.
Просьба еще что-нибудь. Чтоб проникать в мозги.

Пришелец Прораб · : 08-05-2008, 18:13 Тема:

а вы говорите капа

Господин ПЖ · : 08-05-2008, 18:35 Тема:

Молодец, Прораб!

Господин ПЖ · : 08-05-2008, 19:37 Тема:

А по этой задаче воттебе каверзный вопрос:

Есть N монет. За сколько взвешиваний (минимум) можно определить фальшивку?

Tytgrom · : 09-05-2008, 00:47 Тема:

Опять некорректное условие. Минимум 2 взвешивания. Если угадаешь.
Взять две монеты, если повезет, то одна из них окажется тяжелеее другой. Тогда вторым взвешиванием определяется какая именно фальшивая.

Летели два крокодила. Один зеленый, другой на север.
Сколько весит килограмм гвоздей, если у поезда отвинтить две гайки.

Пришелец Прораб · : 09-05-2008, 08:59 Тема:

Думаю Tytqrom прав 2 взвешивания.Или тут формулу надо выводить.

Tytgrom · : 09-05-2008, 19:43 Тема:

Формула есть, причем с логарифмом. Пробовала вывести - не вышло.

А на мою загадку кто-нибудь ответит?

Господин ПЖ · : 09-05-2008, 21:33 Тема:

Tytgrom · : 10-05-2008, 10:05 Тема:

log(3)N- число монет округленный в большую сторону.
где N - число монет
Мы же все время делим на три группы. Поэтому количество взвешиваний - это 3 возведенное в определенную степень.

Господин ПЖ · : 10-05-2008, 10:38 Тема:

Tytgrom

Абсолютно верно! Сама решила?

1. Делим все монеты на 3 части. Треть откладываем, треть взвешиваем (разделив пополам).
2. Если равенство (с вероятностью 1/3), то мы понизили порядок задачи втрое за 1 взвешивание. Если неравенство, то в полтора раза понизили.
3. Теперь с обеих чашек весов снимаем по 1/3 монет и откладываем (не перемешивая). Оставшиеся монеты делим пополам (на каждой чашке) и половины меняем с другой чашкой весов.
4. Если равенство, то мы опять понизили порядок задачи втрое.
Если неравенство осталось прежним, то можно отбросить отложенную треть и перенесенные монеты с одной чашки на другую, что в сумме дает еще треть!
Т.о. порядок задачи опять уменьшается втрое.
Если знак неравенства поменялся на противоположный, то остаются только перемещенные монеты, а их опять же 1/3 и опять порядок задачи уменьшается втрое!
Итак, начиная со второго взвешивания, порядок задачи с каждым разом уменьшается втрое!
Итак, для N монет нам надо log3 N взвешиваний! Однако, это справедливо только для больших N, т.к. при малых, мы стоклкнемся с тем, что число монет нацело не делится на 3 и придется округлять.

(это моё решение, возможно есть более простое)

Пришелец Прораб · : 12-05-2008, 10:00 Тема:

формула не совсем коректна

Господин ПЖ · : 12-05-2008, 10:09 Тема:

Пришелец Прораб

Согласен, она корректна для N кратных 3. Но и для прочих N она примерно такова. Возможно, потребуется log3 N +1 взвешиваний.