Загадки от хера Эбенхарда

а) [:]||||||||[:]

http://www.linux.org.ru/jump-message.jsp?msgid=773585

Нельзя вычислить

баян http://www.linux.org.ru/jump-message.jsp?msgid=773585

Суслятина

но там правада небыло про 13

Задача несложная, если не бояться смешивать шарики из разных групп.

1. Шаг, тривиальный:

1111 - 2222 : 3333

означает, что мы взвешиваем шары 1111 и 2222, остаются 3333

если 1111 = 2222 => легко, так как тогда кривой шар в 3333 и остануться 4 шара на два взвешивания с учетом того, что есть эталон (11112222 являются нормальными эталонными шарами, обозначаем их буквой "Э") . Берем 333:ЭЭЭ и если равенство, то осается один шар 3, который кривой и еще есть взвешивание, чтобы сравнить его с эталоном на предмет легче он или тяжелее. Если 333>ЭЭЭ, то остается три шара и мы знаем, что кривой шар тяжелее. Или наоборот. А если три шара и одно взвешивание - то все элементарно.

Итак, надо лишь рассмотреть случай, когда 1111 < 2222.

2. Пусть 1111 < 2222 : ЭЭЭЭ

Взвешиваем

11122 - ЭЭЭЭ2 : 12

Если они равны, то они все Э, а кривой шар между 12. Осталось сравнить 1 и Э. Тогда если равны, то 2 и он тяжелее, а если 1 будет легче (тяжелее он быть не может), то кривой 1 и он легче.

Если

11122 > ЭЭЭЭ2 : ЭЭ => ЭЭЭ22 > ЭЭЭЭЭ : ЭЭ

то осталось два шара, мы знаем что кривой - это тяжелый и одно взвешивание с эталоном даст ответ какой из них.

Последнее если

11122 < ЭЭЭЭ2 : ЭЭ => шар 2 справа - тяжелый кривой.

Все случаи рассмотрены, задача решена за 3 минуты, записана за 5. ;)

Про 13 думаю. Задача интереснее.

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

Действительно, имеет смысл взвешивать лишь равные куски. Тогда для 13 мы должны взвесить пять и пять, останется 3. Худший случай, когда ЛЛЛЛЛ<ТТТТТ : ЭЭЭ (причем неравенство нам ничего не дает, ибо мы не знаем в какой группе ЛЛЛЛЛ или ТТТТТ лежит кривой шар). Либо четыре и четыре - опять будут эталоны и пять неизвестных. В случае другого любого взвешивания неизвестных становится даже больше.

Итак, у нас два взвешивания на пять шаров и есть эталон.

Возможно взвесить один и один, останется три. И если 1 и 1 равны, то из трех мы ничего не сможем сделать, ибо не знаем, а тяжелее этот гад или легче. Если взвесить два и два, то в случае неравенства мы опять у разбитого корыта.

Итак, 13 - никак.

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

Обозначения
x - неизвестное, 
E - нормальный (эталон), 
L может быть только легче эталона, 
H - только тяжелее эталона,
A - ответ. Если A>E, то он больше эталона, иначе - меньше
V - процесс взвешивания, знаки < и > имеют очевидный смысл
: - разделяет взвешиваемые от отдыхающих ;)
=> - знак следствия, в скобках стоят номера случаев,

первое взвешивание
xxxx V xxxx : xxxx =>

(1) xxxx < xxxx : xxxx => 
    LLLL < HHHH : EEEE
    
    второе взвешивание 
    LLLHH V EEEEH : LH =>
       (1.1) LLLHH < EEEEH : LH => EEEEE < EEEEA : EE => A > E
       (1.2) LLLHH > EEEEH : LH => EEEHH > EEEEE : EE =>
             H V E : H => очевидно все находим.

(2) xxxx = xxxx : xxxx =>
    EEEE = EEEE : xxxx

    второе взвешивание
    xxx V EEE : x =>
    (2.1) xxx > EEE : x => HHH > EEE : E => очевидно
    (2.2) xxx < EEE : x => LLL < EEE : E => очевидно
    (2.3) xxx = EEE : x => EEE = EEE : x
         третье взвешивание x V E => очевидно

    

за баян sorry
atoku - sehr gut!
Есть ещё одна задачка, но совсем простая. Завтра нацарапаю

a) Берём 12 шаров, делим на две равные группы по 6 шаров. Взвешиваем их. Одна из групп будет тяжелее. Выкидываем другую, а оставшуюся делим пополам - по три шара и взвешиваем ещё раз. Одна из групп опять будет тяжелее. Выкидываем вторую и получаем группу из 3 шаров, один из которых "кривой". Откладываем один шар и взвешиваем группу. Если весы показывают равенство, то отложенный шар - тяжёлый, иначе - весы покажут на тяжёлый шар.

б) В случае 13 шаров один шар откладываем, остальные делим на две группы по 6 шаров и взвешиваем. Если весы показывают равенство, то отлиженный шар - тяжёлый. Иначе - отбрасываем лёгкую группы и отложенный шар. После этого смотрим в решение предыдущей задачи и решаем её для 6 шаров.

Элементарно, господа!

Не дано, что он тяжелее. Надо узнать, легче он или тяжелее.

Признаю, что я не прав и посыпаю голову пеплом

анонимус от 05.05.2005 1:41:16

угу, элементарно ...

.б) В случае 13 шаров один шар откладываем, остальные делим на две группы по 6 шаров и взвешиваем. Если весы показывают равенство, то отлиженный шар - тяжёлый. Иначе - отбрасываем лёгкую группы и отложенный шар. После этого смотрим в решение предыдущей задачи и решаем её для 6 шаров.

всё верно - только надо поправить - типа отложили любой шар и если весы показали равенство - то отложенный шар - наш клиент ... берём любой из "нормальных" шаров и взвешиваем с отложенным ... вот и всё ... и в зависимости от того куда склоняца весы - то будет и ответ =)

ЗЫ если отложенный шар не тот - то по аналогии ...

Решение за дачи за ОДНО взвешивание!

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

>Возможно решить задание а) с 13 шарами

Теоретически - да. У нас 13*2=26 вариантов и 3**3=27 ответов по результатам взвешивания. Осталось решить задачу распиливания шара на 3 равные части без существенной потери массы.