большая тёрка

Тёрка в тагах


Друзья

Его(39) Общие(0) Хотят дружить(3)


  • Agrail

  • AI

  • Alstein

  • AVanGarD

  • bolonia

  • Borizzz

Ещё →

Враги

Его(5) Общие(0) Обиженные(3)


  • C-Liana

  • Exploited

  • GOLDEN-BOY

  • GreenStyle

  • jastreb49

  • N00BLO

Ещё →

Большая Тёрка / Мысли / Личная лента TATOSHCA /


TATOSHCA

История

Школа на школу 2010

Эта история случилась давным‑давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем — султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет. «О, великий Саладин, — обратился тогда к султану рыцарь, у которого за душой не было ни гроша, — ты лишаешь последней надежды. У меня на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет — сумма выкупа удваивается!»
«Да будет так, — ответил Саладин, и сам обожавший головоломки. — Слушай же. Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания. Hе справишься с задачей до утра — пеняй на себя!» А вы смогли бы выкрутиться?

8 комментариев

B-52

TATOSHCA, разбиваем двенадцать монет на три равные кучки взвешиваем первые две

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

если опять равновесны‑значит фальшивая монетка одна из остальных двух, сравниваем любую из них с любой из первой кучи(где все монеты заведомо золотые) и в зависимости от того, равновесны чаши или нет определяем, какая из двух фальшивая

если одна из чаш тяжелее, убираем две монеты с одной чаши, одну с другой, вместо них добаляем три с третьей кучи(где монеты заведомо золотые), тоесть 1133–2223 (где номера‑обозначают кучу, в которой монеты были изначально), меняем местами монеты так: 1223–1323

если чаши равновесны‑фальшивая одна из убранных

если положение весов не изменилось, то одна из тех, которые не меняли местами

если изменилось, то одна из тех, которые меняли

Итак, определили тройку, в которой находится фальшивка

Вспомним положение весов, когда на одной чаше лежало две монеты из этой тройки, а на второй‑оставшаяся, уберем одну из двух‑вместо нее положим золотую, еще одну подозрительную поменяем на золотую из другой чаши, взвешаем:

если равновесие‑значит фальшивка убранная

если положение изменилось‑значит, фальшивая монета, которую меняли

если не изменилось‑монета, которую не меняли

3 комментария

TATOSHCA

B‑52, первый точно верен. второй проверю на практике :).

2 комментария

Erazm

1. Делим на три кучки по 4 монеты в каждой.

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

3. определив что одна из четырех фальшивая, взвешиваем по одной.

в идеале можно уложиться и за два взвешивания.

1 комментарий

TATOSHCA

Erazm,

Не получится. вы же не знаете,тяжелее или легче монета фальшивая. В таком случаем вам только 2 взвешивания,что бы определить,в какой из кучек по 4 монетки,у вас фальшивка. Получается за осташиеся взвешивание,надо определить какая из 4 фальшивая,тут извиниет косяк,не получится со 100 процентной веороятностью,следовтаельно ваш ход решения не верен.


TATOSHCA

Ответ:

Эта задача была блестяще разобрана К. Л. Стонгом в майском номере журнала Scientific American за 1955 год. Одно из ее решений (а их довольно много) связано с троичной системой. Сначала запишите все числа от 1 до 12 в троичной системе. Замените в каждом числе цифру 2 на 0, а 0 на 2 и запишите рядом результат. У вас получится три столбца чисел:

   1    001   221

   2    002   220

   3    010   212

   4    011   211

   5    012   210

   6    020   202
   7    021   201
   8    022   200
   9    100   122
   10   101   121
   11   102   120
   12   110   112

Внимательно изучив эти числа, вы обнаружите все числа, в которых встречаются сочетания 01, 12, 20. Каждой из двенадцати монет поставим в соответствие одно из этих чисел.
При первом взвешивании на левую чашу весов кладем четыре монеты, обозначенные числами, которые начинаются с 0, а на правую чашу весов кладем те четыре монеты, которым соответствуют числа, начинающиеся с 2. Если монеты уравновесят друг друга, вы можете утверждать, что число, которое отвечает фальшивой монете, начинается с 1. Если перевесит левая чашка, то искомое число начинается с 0, а если правая — то с 2.
Взвешивая монеты второй раз, их надо распределять в зависимости от средней цифры. Если в центре стоит 0, монета кладется на левую чашу, если 2 — на правую. Вторая цифра числа, обозначающего фальшивую монету, определяется точно так же, как определялась его первая цифра при первом взвешивании.
Производя последнее взвешивание, вы кладете налево те монеты, которые обозначены числами, оканчивающимися на 0, а монеты, соответствующие числам, имеющим на конце 2, вы кладете на правую чащу весов. Таким образом вы узнаете последнюю цифру нужного вам числа.

1 комментарий

B-52

TATOSHCA, отдельная задача‑это понятно написать решение: что и как взвешивать) С троичной системой очень изящно, но суть все та же: одну выбрасываем, одну перекладываем, одну оставляем на месте и смотрим на динамику изменений. Сначала так с тройками монет, потом с самими монетами.

Скорей всего, кто‑нибудь сформулировал и решил эту задачу для любого натурального числа и соответствующего количества взвешиваний

ВКонтактeTwitterFacebook