Здравствуйте, kgd, Вы писали:

kgd>Здравствуйте, takTak, Вы писали:

T>>если вначале 12 элементов поделить на две группы, взвесить 6 и 6, найдётся та группа из 6, где находится более тяжёлая часть,
T>>потом эти 6 делятся на две группы по 3, опять находим группу, где находится более тяжёлая часть,
T>>наконец, в конце берём два любых элемента и взвешиваем- либо один из них тяжелее, а если нет, то тяжёлым является тот элемент, который не взвешивали

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

kgd>Тяжелее он или легче — понятно из первого взвешивания групп.

Т.е. одна группа легче, а другая тяжелее.
Это и я понял.
А что с неправильной монетой?
Она как?
Легче или тяжелее?

Каков Ваш вывод?
Говорите! Не стесняйтесь!

Здравствуйте, NovaMind, Вы писали:


NM>Каков Ваш вывод?
NM>Говорите! Не стесняйтесь!

Если при взвешивании определяется точный вес груза, я предлагаю разрезать монеты на доли. Тогда можно обойтись двумя взвешиваниями: в первом определяется вес неправильной монеты, во втором взвешиваются доли монет — 1/12 от первой монеты, 2/12 от второй и т.д. По точному весу можно получить нужную информацию.

Здравствуйте, NovaMind, Вы писали:

NM>Ну и как?
NM>Легче или тяжелее?

kgd>>Задачка не для поколения твиттера с памятью на 1 итерацию

NM>Ну-ну...

Здравствуйте, NovaMind, Вы писали:

NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
NM>Image: Libra2.jpg
Задача сводится к последующему взвешиванию (начиная со второго) с отбрасыванием 3х: перестановкой 2х c заменой одной на взвешенную.

Первое взвешивание:
4 x 4, если равно, то монета в остальных 4х: (fixed) решение для них тут: http://rsdn.org/forum/education/7677064

Автор: Vain
Дата: 10.03.20

Разность на весах покажет, что фальшивая монета на весах. Равно покажет — в оставшейся стопке.

Второй взвешивание:

(A)
         <проверяемые>         | <остаток>
  o  o  o  o   :   o  o  o  o  |  o  o  o  o
 x1 x2 x3 x4       y1 y2 y3 y4 |  z1 z2 z3 z4

Тут делаем финт ушами до такого:

(B)
         <проверяемые>         | <остаток>
  o  o  o      :   o  o  o     |  o  o  o
  x1 y1 y2         x2 x3 z1    |  x4 y3 y4

(C)
         <проверяемые>         | <остаток>
  o            :   o           |  o
  y3               x4          |  y4

+ у нас информация с предыдущего шага: больше или меньше, т.к. на равно мы уже проверили и монета бы была найдена среди z1..z4.

Первые два взвешивания:

монета | (A) | (B)
-------+-----+-----
x1 > < | > < | > <
x2 > < | > < | < >
x3 > < | > < | < >
y1 > < | < > | > <
y2 > < | < > | > <

Если (B) даёт равно, то взвешиваем (C):

монета | (A) | (C)
-------+-----+-----
x4 > < | > < | < >
y3 > < | < > | > <
y4 > < | < > |  =

Если (B) даёт разность, то осталось проверить x2, x3, y1, y2, т.к. x1 имеет уникальный паттерн.

(D)
         <проверяемые>         | <остаток>
  o  o         :   o  o        |  o
  x2 y1            x3 z1       |  y2

монета | (A) | (B) | (D)
-------+-----+-----+----
x2 > < | > < | < > | > <
x3 > < | > < | < > | < >
y1 > < | < > | > < | > <

< — меньше/легче
> — больше/тяжелее

Как то так.

Здравствуйте, NovaMind, Вы писали:
NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
меня в таких задачах смущала одна вещь — монеты не могут быть одного веса в принципе. где-то потертые, где-то грязные, в разное время отчеканенные из чуть разного металла. и мы не знаем насколько отличается по весу фальшивая. то есть вот ты взвесил весами 2 стопки по 4 и вот видишь что весы на миллиметр отклоняются. это за что считается? за равный вес или что одна тяжелее другой?

например, вес обычной монеты может колебаться +-0.1 грамма, а вес фальшифой дает -0.5 грамма, что, конечно, заметно.
но при этом при взвешивании 6 монет, где на левую часть попадет фальшивая и 5 с перевесом 0.1 легко перевесят вторую чашку где будет 5 с недовесом 0.1. и это будет так даже если пару монет туда-сюда перекинуть

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

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

Здравствуйте, NovaMind, Вы писали:


NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

Так легко же!

Здравствуйте, NovaMind, Вы писали:

NM>Я тоже хвастаться люблю!!!

А я никогда не хвастаюсь, потому что гении скромные!

Здравствуйте, NovaMind, Вы писали:


NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

NM>Image: Libra2.jpg


Быстрее взвестить еще несколько раз, а не оптимизировать число взвешиваний.
При нынешней стоимости взвешиваний это не имеет смысла.

Здравствуйте, deimos, Вы писали:

D>Быстрее взвестить еще несколько раз, а не оптимизировать число взвешиваний.
D>При нынешней стоимости взвешиваний это не имеет смысла.
Точнее, мы просто ставим 6 весов, и проводим 6 попарных взвешиваний одновременно. Потом переставляем монеты, и узнаём точный результат.

Здравствуйте, __kot2, Вы писали:

NM>>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.
__>меня в таких задачах смущала одна вещь — монеты не могут быть одного веса в принципе.
А практическая бессмысленность ограничения количества взвешиваний не смущала?
Задача же не для практического применения, а для экзамена в гугл мучания детей.

Здравствуйте, NovaMind, Вы писали:

NM>Есть 12 монет.
NM>Одна отличается по весу.
NM>За 3(три) взвешиваня найти эту монету и определить тяжелее она или легче.

По-моему ничего особо сложного.

1. Кладем по 4 монеты на каждую чашу

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

3. Если при первом взвешивании получаемы разные веса, то с более тяхелой чаши откладываем в сторонку три любые монеты (группа А). Три монеты перекладываем с легкой чаши на тяжелую (группа Б), а на их местко кладем три монеты из группы эталонных. Выполняем второе взвешивание. Если получаем равновесие, значит, фальшивая монета находится в группе монет, отложенных с более тяжелой чаши (группа А) и она тяжелее остальных монет. Находим эту монету последним взвешиванием. Если показания весов изменились на противоположные, значит, фальшивая находится в группе монет, переложенных с более легкой чаши на более тяжелую (группе Б), и она легче остальных монет. Также находим эту монету последним взвешиванием. Если же показания весов не изменились, значит фальшивая монета находится среди пары монет, оставшихся на своих местах после первого взвешивания (по одной монете на каждой чаше). Мы уже знаем, какая из этих двух монет легче, а какая тяжелее и, сравнивая любую из них с эталонной, последним взвешиванием определяем фальшивую.

Здравствуйте, NovaMind, Вы писали:

NM>>Image: Libra2.jpg
NM>Мой папа(Царствие ему небесное) рассказывал, что задачка остановила работу военного НИИ по РСМД на неделю...

Что-то они тупили, как-то долго...

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>У них интернета не было:
ЭФ>https://habr.com/ru/post/447354/

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

Здравствуйте, Vain, Вы писали:

V>Первое взвешивание:
V>4 x 4, если равно, то монета в остальных 4х. Тут просто взвешиваем 1 x 1 второй попыткой и ещё 1 x 1 третьей, где одна монета уже взвешена.
V>Разность на весах покажет, что фальшивая монета на весах. Равно покажет — в оставшейся стопке.

Так?
1. 1+2+3+4 == 5+6+7+8 => фальшивая среди 9, 10, 11 ,12
2. 9 +10 == 1+2 => фальшивая среди 11 и 12
3. 11 == 1 => фальшивая 12, но тяжелее она или легче?

Здравствуйте, __kot2, Вы писали:

__>меня в таких задачах смущала одна вещь — монеты не могут быть одного веса в принципе. где-то потертые, где-то грязные, в разное время отчеканенные из чуть разного металла. и мы не знаем насколько отличается по весу фальшивая.

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

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

Вообще-то, в истории известны примеры, когда фальшивые монеты были тяжелее настоящих. Демидовки, например...

Здравствуйте, rg45, Вы писали:

R>По-моему ничего особо сложного.

R>1. Кладем по 4 монеты на каждую чашу

По моему тоже, но ты первый, кто тут смог сформулировать решение. При этом даже люди, которые гуглили, нагуглили не то.
При этом, опять же, ты первый, кто изложил решение не только правильное, но и понятное +100500!!!

Здравствуйте, Erop, Вы писали:

E>По моему тоже, но ты первый, кто тут смог сформулировать решение. При этом даже люди, которые гуглили, нагуглили не то.

ИМХО, гугл развращает. Привычка гуглить вытесняет привычку думать. Соображалка не получает достаточной тренировки и постепенно атрофируется.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, NovaMind, Вы писали:

NM>>>Image: Libra2.jpg
NM>>Мой папа(Царствие ему небесное) рассказывал, что задачка остановила работу военного НИИ по РСМД на неделю...

E>Что-то они тупили, как-то долго...

Меня опять терзают смутные сомнения! (с) Иван IV.
Уже Семь недель висит задачка.

Вы... как-то долго...

P.S.
Это я за папу вступаюсь.

Здравствуйте, deimos, Вы писали:

D>Здравствуйте, NovaMind, Вы писали:

NM>>Я тоже хвастаться люблю!!!

D>А я никогда не хвастаюсь, потому что гении скромные!

Я тоже никогда не хвастаюсь, но люблю!

И гении имеют свои слабости...

Здравствуйте, NovaMind, Вы писали:

NM>Меня опять терзают смутные сомнения! (с) Иван IV.
NM>Уже Семь недель висит задачка.

NM>Вы... как-то долго...
Я как увидел -- сразу написал. Но я эту задачку раньше знал уже, так что я вообще мгновенно в данном случае.
Правда я всё равно не понимаю, что там можно было тупить?
Там же дерево решений мизерное.
И всегда можно просто попробовать его перебрать с очевидными отсечениями, так, что бы либо доказать, что задачу решить нельзя, либо построить решение.

Очевидно, что из 27 теоретически возможных результатов трёх взвешиваний, надо разделить 24 ситуации. То есть "подклеить" к другой ситуации, или просто заранее знать, мы можем не более трёх комбинаций результатов взвешиваний.

Очевидно, что первых ход -- это взвешивание 4 х 4, так как для 3 х 3 и 5 х 5 потом не получится за 2 взвешивания (9 разных отчётов) выбрать из 10 или 12 ситуаций.

Если 4х4, то либо получаем в ре-те равенство, и надо выбрать из 8 оставшихся вариантов (какая из 4-х монет и тяжелее или легче) Если неравенство, то тоже из 8 (какая из участвовавших во взвешивании фальшивая, так как кто легче или тяжелее уже знаем). Ок.

Например, рассмотрим случай равенства.
Ясно, что нужно так взвешивать, что бы все три исхода были информативны. Поэтому, 2 х 2 из только оставшихся взвешивать неверно, так как не можем получить равенство, а 1 х 1 не верно, так как в случае равенства не понятно, как решить задачу про две монеты и одно взвешивание. Там вроде бы всего два хода остаётся возможных -- сравнить две оставшиеся или сравнить одну из оставшихся с нефальшивой. Ну и все 4 оставшиеся если сравнить с 4 настоящими, тоже мы узнаем тяжелее настоящая или легче, но, потом из 4 за одно взвешивание с тремя исходами выбрать не получится. И ещё можно подозрительные взвешивать в духе 3х1 дополняя настоящими. Но тут тоже не получится узнать какая монета фальшивая и тяжелее ли она.
Значит надо три подозрительные сравнить с тремя настоящими. Если получим равенство, то фальшивая последняя невзвешенная, и за последний ход узнаём тяжелее она или легче.
Если три окажутся тяжелее (или легче) мы узнаем тяжелее ли фальшивая и за последнее взвешивание 1х1 выберем из этих трёх нужную.
Если же первое взвешивание показало неравенство, то у нас 8 подозрительных монет, про каждую из которых мы знаем тяжелее ли она, если она фальшивая.
Значит максимум 3 подозрительные монеты можно отложить на третье взвешивание, а из оставшихся 5 выбрать за два.

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

Но, даже если не догадаться до идеи о связи первого и второго взвешивания, и ограничить себя только вариантами, когда монета или не участвует во взвешивании, или остаётся на месте. Ок. Предположим мы так "заблудились", хотя мне не понятно, как так можно, если стремиться перебрать ВСЕ варианты (напоминаю, что мы пробуем найти решение или доказать, что его нет).
Но, положим, мы так ошиблись. То сразу возникает вопрос, а как так может получиться, что весы во втором взвешивании покажут другой результат, чем в первом?
Ясно, что позволить себе такую стратегию, при которой такой исход невозможен, мы себе не можем, так как за всего два возможных исхода мы лучше чем до 4 число подозрительных не уменьшим, и всё-таки придётся "изобрести" перекладывание монет между чашками

Вроде бы это полное рассуждение, и оно даёт ВСЕ возможные решения. О чём тут можно думать 2 недели и толпой мне решительно не ясно

NM>P.S.
NM>Это я за папу вступаюсь.

Не надо вступаться, надо попробовать решить таки НОРМАЛЬНО какую-нибудь похожую задачку. Например, для аналогичной задачи для 13 монет (26) вариантов, трёх взвешиваний (27 вариантов результатов взвешивания) можно определить фальшивую и знак её отличия от остальных?