LINUX.ORG.RU
Форум — Talks  

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


0

0



Короче на лекции INFO 2 получаем раз в неделю листик с заданиями. Там кроме прочих заданий имеется всегда одно "для дурачков"

Вот очередное:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Есть 12 билльярдных шаров, среди которых один отличается весом от всех остальных.
а)Вычисли этот шарик за три попытки взвешивания на весах. (незнаю как такие весы по-русски называются, ну типа где взвешивают при помощи противовеса, как раньше в гастрономе). Легче или тяжелее этот шар чем остальные ?
б)Возможно решить задание а) с 13 шарами ? Обаснуй!
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Дерзайте мозганы лора ! (-:

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

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

Keiko
()

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

Суслятина

linux_newbe ☆
()

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

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

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. ;)

atoku ★★★
()

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

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

atoku ★★★
()

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

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

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

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

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

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

atoku ★★★
()
Ответ на: Re: Загадки от хера Эбенхарда от atoku

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

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

Обозначения
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 => очевидно

atoku ★★★
()

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

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

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

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

anonymous
()

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

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

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

anonymous
()
Ответ на: Re: Загадки от хера Эбенхарда от anonymous

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

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

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

bugagaga
()
Ответ на: Re: Загадки от хера Эбенхарда от bugagaga

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

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

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

anonymous
()

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

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

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

DonkeyHot ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Talks