[боян] Задача о 12-ти шарах

а зачем это нужно? за это залпатят? или я узнаю ночную дату апокалипсиса?

А тем временем баяны продолжали лопаться с оглушительным треском...

>Мне слабо :(

Неудачник. 1) на 6 и 6. 2) 3 и 3 3) 1 и 1 (> < ==)

Нужны весы с 11 чашками:

Один шар оставляем, остальные раскладываем по чашкам. Будет три исхода:

1) В нижнем положении два шара, один в верхнем - он "фальшивый".

2) В верхнем положении два шара, один в нижнем - он "фальшивый".

3) Весы в равновесии, "фальшивый" шар на столе.

Эмм, взвешивание потребуется всего одно.

4 4 4 => 1 1 2 => 1 1 (если понадобится)

>1) В нижнем положении два шара, один в верхнем - он "фальшивый". 2) В верхнем положении два шара, один в нижнем - он "фальшивый". 3) Весы в равновесии, "фальшивый" шар на столе.

А мозг в жопе...

И что, 4 4 4? Если весы уравновесятся, то всё понятно. А если нет - в какой из четвёрок находится аномальный шар?

> Неудачник. 1) на 6 и 6. 2) 3 и 3 3) 1 и 1 (> < ==)

Недоумок - нам не известно тяжелее аномальный шар или легче, чем остальные. Как ты будешь аномальную кучку выбирать?

>Неудачник. 1) на 6 и 6. 2) 3 и 3 3) 1 и 1 (> < ==)

прочитай задание еще раз

Я знаю как это сделать за три взвешивания. Но точность метода - 50 % :))

>А если нет - в какой из четвёрок находится аномальный шар?

две четверки равны - в третье косяк.

а если не равны?

> Неудачник. 1) на 6 и 6. 2) 3 и 3 3) 1 и 1 (> < ==)

Ага, и какую шестёрку ты выберешь после первого захода? Неудачник.

> а зачем это нужно? за это залпатят? или я узнаю ночную дату апокалипсиса?

Говорят, эту задачу часто используют при приёме на работу. Это как тест на нестандартное мышление.

Решение задачки тупое и нудное. Обычно люди ожидают чего-то простого, но тут не так. Короткого и красивого решения не существует.

Если я правильно понял речь о трех чашах весов

Блин, а решение то какое? Пойду в гугл

>Т.е. в данном случае задача однозначно решается для шаров меньше или равно 8-ми. Частный случай, т.н. "если повезет", когда можно однозначно найти дефектный шар по трем взвешиваниям, указан у Андрюшки и Валентины Лаптевой. Алгоритма, при котором результат гарантирован, не существует (доказательство этому, по-моему, существует. Сейчас недосуг искать или делать самому). Если неповезет, придется делать четвертое взвешивание. См. еще мои комментарии к ответам Андрюшки, Валентины Лаптевой и Klamm.

>Говорят, эту задачу часто используют при приёме на работу. Это как тест на нестандартное мышление.

это где видоно, чтоб такие вопросы давали на должность дворника O.o

Могу за одно взвешивание - делов то - весы с 12ю чашами

Ну-ка, ну-ка. Давай-ка именно на 12-чашечных весах забабахай решение.

Делим на четыре тройки. 1) тройки 1 и 2 против троек 3 и 4; 2) тройки 1 и 3 против троек 2 и 4; к этому моменту ясно, тяжелее или легче аномальный шар и в какой тройке он находится. 3) два шара из этой тройки.

> к этому моменту ясно, тяжелее или легче аномальный шар

откуда?

1. Взвешиваем 3 и 3. 1а)Если равны, берём вместо одной тройки ещё одну из оставшихся. 1б)Если не равны, точно так же берём ещё одну тройку из оставшихся. 2. Взвешиваем эти новые тройки. 2а)Если равны, аномальный шар в оставшейся тройке. Если не равны - в свежевзятой. 2б)Если равны - аномальный в только что отложенной тройке. Если не равны - аномальный в той тройке, что взвешивалась оба раза. 3. Теперь у нас есть три шара, кроме того, мы знаем - легче аномальный шар или тяжелее ( из результатов прошлых взвешиваний ). Вот и всё.

Если чашки имеют независимую подвеску?

Делаем прогон с тройками:
1) 1,2 vs 3,4 -> 1,2 тяжелее
2) 1,3 vs 2,4 -> 1,3 тяжелее
Тут два варианта: либо в первой тройке тяжёлый шар, либо в 4-й лёгкий. Так что не катит.

>Делим на четыре тройки.

нет. Это если бы было известно легче или тяжелее аномальный шар

>Ну-ка, ну-ка. Давай-ка именно на 12-чашечных весах забабахай решение.

Ну вобщем то легко. В задаче нет никаких пояснений про механизм весов. Так что фантазировать можно сколько угодно - допустим весы хоть и имеют несколько чашек, не коромыслового типа, а с индивидуальной подвеской каждой чашки. Вот реальное Enterprise решение. Можно и на основе гравитации весы намутить, запустив шары в открытый космос, только вот чашки будут условностью скорее...

http://www.google.com/search?q=%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0+12+%D0%BC%D
0%BE%D0%BD%D0%B5%D1%82&hl=ru&start=10&sa=N

Некто очень хреново гуглит. Вот к примеру:
http://faqs.org.ru/games/logic/golovol.htm

.6  Взвешивание  12 монет

     Q:  У  Вас  есть  12  монет,  одна из которых фальшивая и она либо
легче,   либо   тяжелее  настоящей.  Как  с  помощью  трёх  взвешиваний
балансировочных  весах  (которые  показывают  больше-меньше) определить
фальшивую монету и то, легче она или тяжелей настоящей?
     A:  Решений  много.  Как  мне кажется, приведенное здесь - одно из
самых  коротких.  Обозначим  монеты  следующим образом: FAKE MIND CLOT.
Взвешиваем  одну  четверку  против  другой  (буквы  обозначают  монеты,
входящие в каждую четверку):
     MA  DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто
найти  фальшивую  монету:  к примеру, если результаты взвешивания были:
слева  легче, равно, слева легче, то фальшивой может быть только монета
"A", которая легче других.
     * Примечание ОП: Если монет 13, то всё ещё можно определить, какая
из них фальшивая, но уже нельзя ответить, легче она или тяжелее настоящей.
Тринадцатая монета просто не участвует во взвешиваниях.
Если монет (3^N)/2, то задача решается за N взвешиваний.

c 11 она решается элементарно, в толксах уже обсуждали.

> к этому моменту ясно, тяжелее или легче аномальный шар

>откуда?

Прикупи мозгу.

>Прикупи мозгу.

Пошол за мозгом и за волосами на разные места заодно.

> В задаче нет никаких пояснений про механизм весов. Так что фантазировать можно сколько угодно

Ага, особенно при приёме на работу пофантазируешь :)

>Т.е. в данном случае задача однозначно решается для шаров меньше или равно 8-ми

если тройки равны, а потом еще раз равны, то мы не знаем тяжелее ли аномальный шар.

>Ага, особенно при приёме на работу пофантазируешь :)

При приеме на работу, подобным решением ты покажешь, что предпочитаешь законченые и оптимальные для каждой задачи решения. Разве те так?

а вот это решение, похоже.

Можно так: Делим на 4 тройки (a,b,c,d)

a / b - если a = b - аномалия в c или d взвешиваем a / c - a = c -> в d аномалия - a != c -> в с аномалия - если a != b - ищем аномальную тройку аналогично предыдущему решению (только a меняем на с, а b - на d)

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

Один шар можно заранее выкинуть.

> При приеме на работу, подобным решением ты покажешь, что предпочитаешь законченые и оптимальные для каждой задачи решения. Разве те так?

Это один из вариантов. Другой вариант - тебя просто пошлют нафиг :) Работодатели разные бывают.

Это будет ясно после второго взвешивания. Так что все нормально.

Не, ступил. Может и не повезти.

боян

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

Да взлетит он, сколько можно обсуждать...

Вряд ли у задачи есть решение. Минимальное количество шаров, которые необходимо отсечь для последующего решения - 9. То есть все 3 взвешивания совершить с 3 шарами. 1vs2 - больше или меньше и сравнить любой из них с 3 шаром, чтобы понять, тяжелее ли аномальный шар или легче.

Херня какая-то. Ставлю нормальную задачу - есть документ, который должны завизировать 12 равномерно распределённых по поверхности земного шара рыл. Времени на сбор закорючек - 1 час, потом - доклад в правительстве.

Есть смелые бойцы?

>12 равномерно распределённых по поверхности земного шара рыл.

8 рыл водоплавающие?

> 8 рыл водоплавающие?

Ты с дярёвни чтоль? Многие люди отдыхают на собственных яхтах, не говоря уже о воздушном транспорте.

Да, прокосячил :(