Задача про 12 шаров и 3 взвешивания

[ZlCosh]

Условия:
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать

Необходимо определить какой из шаров - имеет аномальную массу

(с)перто отсюда - alexeymas.livejournal.com/27119.html

у меня ушло 37 минут))) вроде, правильно)))

@темы: Интересности

Comments

[Арджи Линсе]

Элементарно же.
Сначала кладёшь по 6 шаров в каждую чашу. Те, среди которых прячется тяжёлый - перевесят.
Разделяешь их на две кучки по три шара - снова взвешиваешь. определяешь, в какой тройке тяжёлый.
Из тройки берёшь любые два. если один тяжелее - тут и думать не надо. Если взвешиваемые шары равны, значит тяжёлый - тот, который остался.

[ZlCosh]

Oscuro azul
неправильно)))

12-й либо тяжелее, либо легче (это неизвестно)

[Арджи Линсе]

ZlCosh, если 12 шар легче - значит, просто выбирать более лёгкую половину.

[ZlCosh]

Oscuro azul
неизвестно - легче шар или тяжелее.
в этом и сложность задачи)))

[Арджи Линсе]

ZlCosh, мда...

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

[ZlCosh]

Oscuro azul
взвешиваний только три)))
но сама идея правильная)))
сама так же примерно решала

[Арджи Линсе]

ZlCosh, ну, если повезёт - то в три можно уложиться. *смеётся*

[ZlCosh]

Oscuro azul
это если повезет)))
при моем решении - если повезет, то и двух хватит)))

[Арджи Линсе]

ZlCosh, здорово... а как?

[ZlCosh]

Oscuro azul

Решение:
делим шары на 3 кучки по 4 шара: 1+2+3+4, 5+6+7+8, 9+10+11+12.
взвешиваем первые две (первое взвешивание). Дальше начинается разница:
А. 1+2+3+4=5+6+7+8
тогда убираем с первой чашечки шарики 2+3+4.
на первую чашечку ложим 1+9+10+11, и опять сравниваем с 5+6+7+8 (второе взвешивание). если "равно", то аномальный - 12 шарик, если нет, то узнаем больше или меньше вес аномального (допустим, больше).
затем сравниваем 9 и 10 шарики (3 взвешивание). аномальный либо один из них (который больше), либо 11 (если 9-10).

Б. если 1+2+3+4 не равно (больше, но с меньше то же самое) 5+6+7+8 (1 взвешивание)
сравниваем по весу 1 и 5 шарик (2 взвешивание):
Б.1. если равны, то мы точно знаем, больше-меньше аномальный (допустим, больше, и больше вес первой кучки шариков), поэтому сравниваем вес 2 и 3 шарика (3 взвешивание), если они равны, то аномальный 4, если нет, то тот, который больше.
Б.2. Если 1 и 5 шарики (2 взвешивание) НЕ равны, то сравниваем вес любого из них с любым другим (3 взвешивание). Аномальным будет либо 1, либо 5

на все потрачено 37 минут))) секунды на компе не видно.

[Гость]

ZlCosh у тебя Б1 не правильно определить если аномальный шар меньше весит нормального.
Допустим аномальный шар номер 6 и он легче других, то 1+2+3+4>5+6+7+8 ...

[ZlCosh]

Гость
пасяб)))
ушло думаьб дальше)))