Форум умных людей

Представьте весы из трёх чашек - букву Y с углами 120 градусов и плечами равной длины, центр которой подвешен за нить, а на концах расположены чаши для грузов.  Положив на такие весы любые три груза, сразу видим как они упорядочиваются по весу.
Имеются N монет, среди которых 2 фальшивых, отличных по весу, причём обе фальшивые монеты, взятые вместе, весят как две настоящие.  Разрешено сделать 3 взвешивания, чтобы найти фальшивые монеты.  При каких N вы сможете решить задачу?

N=5

Стэйси, очень мало.
Бука, можно больше.

N =  Показать скрытый текст

Нашел ошибку. Получается  Показать скрытый текст

Вот это:

верно.
Вот тут:
N может быть больше.

для 10 монеток - 2 взвешивания
для 19 монеток - 3 взвешивания

Вот этому не верю. Не слишком смело?

1_т 2_л 3 4 5 6 7 8 9 10 (монетки 1 и 2 фальшивые:1 тяжелее, 2 легче)

1) 1_т 2_л 3 = 4 5 6 = 7 8 9, 10 монетка в сторонке
по одной монетке из каждой кучки откладываем в сторону, а потом взвешиваем монетки след.образом:
например, отложим монетки - 3 6 и 9
2)1_т 4 > 2_л 7< 5 8
        т        л       ср
если бы тяжелой монеткой была 4, то легкой должна быть 5я монетка, но она находится в кучке со средним весом и не может быть легкой, то есть тяжелая монетка 1
если бы 7 была легкой, то 8 должна была тяжелой, но она так же находится в кучке со средним весом то есть 2 легкая фальшивка

теперь, если бы мы отложили в сторону например 1_т 6 и 9
2) 2_л 4 < 3 7 = 5 8
две одинаковые по весу кучки, это только монетки настоящие, так как 2 и 4 легче, то одна из них легкая, вопрос в том, какая тяжелая из оставленных - 1 или 6
если бы была 6, то 5 должна быть легкой, но этого быть не может (кучка с 5 тяжелее кучки 2 и 4), то есть тяжелая монетка 1

А почему не 6-ая, например?
А почему не 9-ая, например?
А почему не 4-ая и тогда бы во втором взвешивании было бы тройное равенство.
P.S. Подгоном "попахивает". :)

в данном случае имеем след.картину с тремя возможными результатами в весе

                                2_л 7
                   5 8
   1_т 4
если бы 4 была тяжелой, тогда 1 и 2 были бы настоящими, следовательно, 2 и 7 имелибы одинаковый вес с 5 и 8, но в данном случае, вес отличается

пока писала, ты время зря не терял  :laugh:

Так это все понятно. А как быть с моими вопросами?

если бы была 9 тяжелой, то 1 и 4 = 5 и 8, у нас другой результат на весах

уточни о чем ты

Хех, это я об этом:
2л4т=37=58, но я забыл про первое взвешивание - тогда бы там не было равновесия. :yesgirl:
Так, а если изначально 4л, а 6т?
Почему же? Допустим 9т, 8л, тогда бы не было равновесия, ну тогда бы 8 легко определялась.  :yesgirl:
P.S. Все - я спать. :zzz:
Завтра продолжим критику. :)
Споки. :peace:

я до завтра все забуду  :laugh:
споки  :zzz: я тож пойду

тогда так:
1) 1 2 3 = 4л 5 6т = 7 8 9
2) 1 4л  <    2 7  =    5 8
легкая либо 4, либо 1
если 1л, то приплыли ....  :(

buka, Илья, как у вас для 9 за 2 взвешивания получается? По-моему, только для 8 возможно. Всю голову сломал, для 9 не придумал решение.

Если фальшивые монеты в парах АБ или ГД. Как вторым взвешиванием определить в какой именно паре они?

Так мы же их разъединяем, весы все покажут. Одна монетка легче, другая тяжелее, вместе как две настоящих.

АГЗ > ЖВЕ > ДБИ .  Какая пара фальшивая?

Либо А и Д, либо И и З. Не определить.  :-\
Так, надо подумать.

Вот так:
АБ--ГД--ЖЗ, если нет равновесия, то либо сразу определяется, какая тяжелая, а какая легкая, либо определяется одна из них, вторым взвешиванием легко определяется вторая.
Если равновесие, то второе взвешивание будет такое: АВ--ГЕ--ЖИ
Равновесия точно не будет и с помощью анализа ситуаций определяем какая из них легкая, а какая тяжелая.

Шаманство начинается, когда надо определить из 20 монет и более.
У меня есть решение (не мое) для 23 монет, но там не определяется, какая конкретно тяжелее, а какая легче, да по условию этого и не требуется, а точно определяется фальшивая пара.

Илья, можешь поделится этим решением?

Да, могу. Подвижек все равно не наблюдается. Бука застрял на 16. Интересно было бы посмотреть на решение Тианы в 19 монет. Тем не менее, решение для 23 монет:
Показать скрытый текст

Спасибо. Вечером попробую разобраться.

Поскольку я тоже набрёл на это решение и обсуждение этой проблемы, то уже не рыпался :)

у меня вроде получилось для 18, решение для 23 пока не читал..
зы: "вроде" потому, что, по обыкновению, решал в уме, пока гулял с собакой, так что мог где-то потеряться... :roll:

Так возможно или нет?
И интересно было бы увидеть решение для 19 монет.  :read:

10 не получилось, а решение для 19 не помню куда записала, но оно скорей всего тоже не правильное, надо  :think:

1   7   13
2   8   14
3   9   15
4  10  16
5  11  17
6  12  18  19

кладем на каждую чашу по 6 монет (1)
покажу наиболее сложный на мой взгляд момент, когда чаши при этом равны.

тогда кодируем (перераспределяем) следующие монеты,
1   7   13
2   8   14
3   9   15,

указанным ниже образом, добавляем к ним монеты 4, 10. 16 в прежнем их расположении и взвешиваем (2):
1    2     3
7    8     9
13  14  15
4    10  16
если снова весы показывают равенство, тогда мы понимаем, что фальшивые монеты могут находиться исключительно в следующих парах:
1/4 5/6 8/10 11/12 15/16 17/18 (см. начальное расположение монет на весах)
тогда мы угладываем монеты из этих пар на весы по 3 следующим образом и снова взвешиваем (3):
1   4    6
5  11  12
8  15  17
------------
10. 16. 18 - монеты лежат в сторонке
тепрь по получившемуся расположению весов мы легко можем определить пару фальшивых монет.
весы не могут быть равны, т.к. ни одна пара не попала на одну чашу весов.
если весы первая (левая) чаша весов легче (Л), то смотрим на 2 и 3 чаши. если 2 и 3 равны, тогда фальшивая монета идет в пару к 7 и это монета 10. если 1 чаша Л а 2 чаша Т, то фальшивая пара 1/4. если 1л и 3т то фальшивая пара 5/6. аналогично, если 1 чаша будет тяжелее (Т).
при таком раскладе, 19 монета выявляется настоящей по умолчанию после первого взвешивания (иначе небыло бы равенства на весах)

зы: если с этой частью все впорядке, то позже изложу вариант для случаев, когда весы не равны при 1 взвешивании, либо при 2.

* выделенное исправлено (спасибо Илья)

Если после первого взвешивания будет  А > B > C, то нужно найти 2 из 12 за 2 взвешивания.

я потому и показал самый, на мой взгляд, сложный из возможных вариантов взвешивания по 6, т.к. после первого взвешивания мы имеем 18 монет, из которых нужно определить фальшивые за те же оставшиеся 2 взвешивания.
после того, как не будет вопросов к предложенному мною частному случаю. я покажу свое видение разруливания оставшихся вариантов.

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

Здесь в рассуждениях ошибка.
1/4 - согласен
Дальше, если бы было 5/6, то весы при втором взвешивании были бы не равны.
Поэтому следующая подозрительная пара: 3/5
7/10 - аналогично нет равновесия.
Следующая пара 8/10
Если 11/12 - то нет равновесия при втором взв.
Следующая пара 9/11
13/16 тоже не может быть
Следующая пара 11/15 и наконец 16/18
Итого: 1/4, 3/5, 8/10,  9/11, 11/15, 16/18 подозрительные пары.
Но это легко определить за 3-е взвешивание.
А вот что делать, когда во втором взвешивании нет равновесия?

извини, Илья, и все, чисто механическая ошибка, это понятно из того, что чуть выше я представил квадрат из 9 цифр, а в итоговый вариант ниже на 3 чашу поместил другие.

уже исправил

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

Я сегодня искал решение для 18, так получалось, что на третьем взвешивании из 6-ти пар кандидатов нужно найти.

С выделенным не согласен.
Добавка: 8/10, 15/16.

абсолютно верно. спасибо, Илья, я исправил.

Тогда я согласен с приведенным решением при равенстве в первом и втором взвешивании.
Рассматривать ситуацию, когда в первом взвешивании нет равенства думаю не стоит - все достаточно просто.
А вот случаи, когда нет равенства при втором взвешивании, рассмотреть стоит. :nyam:

 убрал вопрос

начну с простого из тяжелых: при втором (2) взвешивании чаши весов (слева направо) распределились как 1<2<3.
тогда просто взвешиваем монеты 4, 7, 16 и к более легкой ищем пару на противоположной чаше весов исходя из первоначального (!) распределения монет.
например:
4 - легкая. потенциальные пары к ней 1 и 3, но 1 не может быть, значит 3.
7 - легкая. пара 9
16 - тяжелая. пара 13 (15 быть не может)

С 4-ой согласен.
С 7-ой тоже.
А вот с 16-ю недочет. 16 может быть тяжелая, как и 15, а вот легкая 13.
То есть взвешиваем 4 7 и 13, но тогда если 13 легкая непонятно какая тяжелая: либо 15, либо 16.

правильно, спасибо Илья. иммелось ввиду таки да, если 16 - т, то 13 - л.

на этом этапе зачОт? :)

Почему 1 и 15 не может быть? Они при 1-ом взвешивании были в своих группах, а при 2-ом по одной из них в разных группах образовали возможные пары 1-3 и 4-3. Также и 15, 16, 13. И если проверить только 4, 7, 16 то возможно равенство.

То есть, а если равенство 4--7--16, то фальшивая пара 13 и 15.
А как быть с парой кандидатом 1/3?

Я имел ввиду, что две пары 1-3 и 13-15 остаются непроверенными, поэтому на весах возможно равенство

имеем потенциальные пары (слева к примеру легкие, справа - тяжелые):
  1-- 3
      /
  4
  7-- 9
13--15
    \
      16

1 и 15 изначально были в разных группах, а поскольку первое взвешивание показало равенство на весах, то 1 и 15 не могут быть парой, иначе равенства быть не могло.
равенства 4, 7, 16 тоже не может быть, т.к. 4 и 7 по итогам второго взвешивания оказались в группе потенциально легких, а 16 - потенциально тяжелых.

1 может быть только легкой у нее пара 3т
у 15т может быть 13л
Да, если взвешивать 4 7 16, то остаются не удел 1 и 13, что я уже и написал выше.

точнее, если равенство, то все монеты на весах настоящие и фальшивая пара 1/3

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

Может, если фальшивая пара 1/3 или 13/15.
Согласен.

да, нужно добавить еще одну потенциально фальшивую монету и две настоящих по чашам, как показано ниже:
1   2   3 - чаши
----------
4   7  16
н  15  н

тогда:
если 1<2=3 - пара 3/4
1=2<3 - 13/16
1=3>2 - 7/9
1=2=3 - 1/3
1=3<2 - 13/15

Смит, ошибок не нашел.

осталось два варианта: 
1) когда при 2 взвешивании одна из чаш легче а две других равны (например, 1<2=3) - тогда перебор пойдет между 4 потенциально легкими и 6 потенциально тяжелыми.
2) когда при 1 взвешивании чаши не равны

зы: по ним постараюсь отписаться в ближайшее время

waleriy, Илья, спасибо за поправки!

На самом деле во втором пункте еще могут быть такие варианты:
а)1=2<3
b)1>2>3 - но этот случай аналогичен 1<2<3
c)1>2=3
d)1=2>3
2) про первое взвешивание, я уже говорил - его не обязательно рассматривать.

Илья, варианты а) с) и d) также аналогичны тому, который я написал 1<2=3 (т.е. две чаши равны, а одна - отличается л/т), поэтому, вероятно, имеет смысл рассмотреть какой то один.

Да, верно. Ждем с нетерпением решения. И можно ставить зачет для 19 монет.

когда при 2 взвешивании одна из чаш легче, а две других равны (например, 1<2=3) имеем:
1,4,7,13 - потенциально легкие
5,6,11,12,17,18 - потенциально тяжелые

тогда расклад на весах при третьем взвешивании такой:

 1   2    3 - чаши весов
-------------
 6  12  18 - потенциально тяжелые
13  4    7  - потенциально легкие

всего возможно 8 потенциально фальшивых пар: 1/5, 1/6, 4/5, 4/6, 7/11, 7/12, 13/17, 13/18.

теперь варианты результатов взвешивания:
1<2=3 - 13л и к ней в пару 17, т.к. 18 - показало бы на весах (13/17)
1<2<3 - 13л и 18т (13/18)
2<1=3 -  4л и 5т (4/5)
2<3<1 -  4л и 6т (4/6)
3<1=2 -  7л и 11т (7/11)
3<1<2 -  7л и 12т (7/12)
1>2=3 -  6т и 1л (1/6)
1=2=3 -  1л и 5т (1/5)

вот, как-то так...
зы:вроде сростается? :tomato:

Тут все верно. Осталось совсем немного.

А как же 19-я? Забыли? Тогда в список пар-кандидатов автоматически добавляются еще 4 пары: 1/19, 4/19, 7/19, 13/19.

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

waleriy, я помню о вашем вопросе с самого начала, просто считал, что это наиболее легкий вариант и рассматривать его имеет смысл если все остальное сростется. вот, вроде все срослось, а ответа на ваш вопрос у меня пока нет, во всяком случае придумать его быстро у меня не получается.  :-\
так что есть над чем подумать ;)

значит, если при первом взвешивании получается 1<2<3 то далее действуем так:

2 взвешивание:

 1     3      5
 2     4      6
13    н      н
14    н      н
15    н      н

16,17,18 - в сторонке

тогда, если весы равны - потенциальные пары в 1 чаше. если 2 или 3 чаша легче, соответственно в пару к ним идут отложенные монеты, а если например расклад 1>2>3 то в пару к легким монетам 5,6 идут монеты 14,15.
 :)

т.о., в любом случае, по результатам второго взвешивания имеем 2 легкие и три тяжелые монеты (например, 1,2 и 7,8,9).

тогда третье взвешивание (3):

7 8 9
н 1 н        2 - в сторонке.

если весы равны, то это пара 8/1, еcли просто какая-то чаша легче, то это пара - легкая монета из этой чаши и монета 2.

Smith, замечательно!  :bravo2: Все работает.

Здесь исправьте пожалуйста знаки ">" на "<" (для читателей)

спасибо  :cool4:
интересно, далее следует думать над 20  :roll: или над 24? :o

 Смит, спасибо.

Думаю нереально.

я Вас правильно понял, но снова не правильно исчправил :tormoz:

зы: вобщем, спасибо, все исправил :peace:

это навеяно тем, что решение для 23 выдалось достаточно замороченным, или есть реальные предпосылки к невозможности решить данную задачу для 24 (25) монет?

24 монеты.

Первое взвешивание (1):
1    9    17           
2   10   18           
3   11   19             
4   12   20               
5   13   21             
6   14   22                   
-----------------
7   15   23    - под чертой оставшиеся монеты (6шт.), лежат в сторонке.         
8   16   24             
Если весы равны, тогда второе взвешивание (2):
 8     6    3           
 9    10   11           
17   18   19             
 4     5     7               
12   15   13             
23   20   21                   
-----------------
1,2,16,14,22,24 - под чертой оставшиеся монеты (6шт.), лежат в сторонке.         
Если снова весы равны, то имеем потенциальные пары:
8/23, 9/12, 6/5, 18/20, 11/13, 19/21 и две пары 1/2 и 16/24 из оставшихся монет (всего 8 пар), и тогда третье взвешивание (3):

... в процессе разработки  :wall:

Если при втором взвешивании имеем например 1<2=3, то:
- потенциально легкие монеты (чаша 1): 4,8,9,12,17,23
- потенциально тяжелые монеты (отложенные при втором взвешивании): 1,2,16,14,22,24
- потенциально фальшивые пары (всего 9 пар):
4/1, 4/2
9/14, 12/14
17/22
8/16, 8/24, 23/16, 23/24
Тогда третье взвешивание (3):

 8л   23л   9л
12л  17л   4л
 1т    2т   16т
22т   24т   н = нормальная монета, 14 - лежит в сторонке.
Теперь при любом положении весов мы определяем фальшивую пару, если весы равны, то фальшивая пара 23/24.

 

прошу прощения, в первой части решения для 24 монет при третьем взвешивании сначала не учел две потенциально фальшивые пары.

затем учел, и кое-что исправил, но решения для третьего взвешивания в первой части, (когда весы при втором взвешивании равны) пока нет.

решение для 1<2=3 работает с учетом уже исправленного в первой части.

кстати, пока исправлял ошибки, выяснил нечто интересное для себя. когда приступал к варианту с 24 монетами, то понимал, что можно найти пару фальшивых из 6 пар "непонятных" и из 8 пар, когда известно легче/тяжелее. оказалось, что можно определить фальшивую пару из 7 "непонятных" и из 9 пар легче/тяжелее (кстати, полагаю последнее - не предел). но вот чего пока не осилил - это определение фальшивой пары из 8 "непонятных". но даже если 7 "непонятнных" - предел, то это не значит, что нельзя 24. тогда просто нужно привести решение к известным "штампам" :tianchik:

Смит, есть ли продвижение для 24?  :-\

спасибо за вопрос, 24 - на повесстке дня, пытаюсь выкроить время между всем..
например, пришел к тому, что взвешивание на двух чашах весов из трех в определенной ситуации может иметь успех.

зы: готового решения для "когда равно" пока нет

интересно, можно ли доказать (или опровергнуть) возможность определить фальшивую пару из 8 потенциально фальшивых?  :roll: