Опять про фальшивые монеты
Alexander Smolensky
Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи pычажных
весов за 3 взвешивания нужно опpеделить подделку.
Alexander.
Taras Heychenko
> Пpивет, All.
> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи pычажных
> весов за 3 взвешивания нужно опpеделить подделку.
IMHO эту задачу можно решить только если знаешь, тяжелее или легче фальшивая
монета. Иначе за четыре.
> Alexander.
--
Tasic.
Делал ли кто-нибудь вязку кисок по асинхре?
Alex Sadovsky
21 Jan 99 в 10:24 Alexander Smolensky писал(а,о) All:
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS> pычажных весов за 3 взвешивания нужно опpеделить подделку.
Hумеруем монеты от 1 до 12. Пусть взвешиваемые на левой чашке монеты будут
обозначаться Л (X, Y, ..., Z), а на правой - П (X1, Y1, ..., Z1). Введу понятие
"знак взвешивания" - если Л > П, это минус, если Л < П, это плюс.
*ВЗВЕСИТЬ*: Л (1, 2, 3, 4) ? П (5, 6, 7, 8).
1.1. [1234] = [5678].
_ВЗВЕСИТЬ_: Л (9) ? П (10)
1.1.1. [9] = [10].
/ВЗВЕСИТЬ/: Л (9) ? Л (11)
[9] = [11] - фальшивая монета N 12,
не равна - фальшивая монета N 11.
1.1.2. [9] не равна по массе [10].
/ВЗВЕСИТЬ/: Л (9) ? Л (11)
[9] = [11] - фальшивая монета N 10,
не равна - фальшивая монета N 9.
1.2. [1234] не равны по массе [5678] (запомнить, что больше весит, Л или П!)
_ВЗВЕСИТЬ_: Л (1, 2, 5) ? П (3, 4, 6)
1.2.1. [125] = [346].
/ВЗВЕСИТЬ/: Л (7) ? П (1)
[7] = [1] - фальшивая монета N 8,
не равна - фальшивая монета N 7.
1.2.2. [125] не равны [346] (запомнить знак взвешивания!)
Если по сравнению с первым взвешиванием знак во втором взвешивании
поменялся, то фальшивая монета 3, 4 или 5.
/ВЗВЕСИТЬ/: Л (3) ? П (4)
[3] = [4] - фальшивая монета N 5,
не равна:
- если в первом и третьем взвешиваниях знаки были одинаковые,
то фальшивая монета N 3,
- иначе фальшивая монета N 4.
Если же знак первого и второго взвешиваний не менялся, то фальшивая
монета 1, 2 или 6.
/ВЗВЕСИТЬ/: Л (1) ? П (2)
[1] = [2] - фальшивая монета N 6,
не равна:
- если в первом и третьем взвешиваниях знаки были одинаковые,
то фальшивая монета N 1,
- иначе фальшивая монета N 2.
Благодарю за чудную беседу! Александр Sado...@usa.net.
Alexander Kobrin
21 Jan 99 10:24, Alexander Smolensky wrote to All:
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS> pычажных весов за 3 взвешивания нужно опpеделить подделку.
ну это просто.
берем четыре монеты и кладем на одну чашку весов и еще 4 - на другую,
если весы уравновешены, то фальшивая среди четырех оставшихся...
дальше продолжать? :-) в книжке "язык турбо с" эта задача хорошо расписана, но
очень длинно. набивать лениво... ;)
Ciao!
Alexander
Andrew Usachov
21 Jan 99 10:24, Alexander Smolensky wrote to All:
AS> éÍÅÅÔÓÑ 12 ÍÏÎÅÔ ÉÚ ÎÉÈ ÏÄÎÁ ÆÁÌØÛÉ×ÁÑ (ÄpÕÇÏÇÏ ×ÅÓÁ). ðpÉ ÐÏÍÏÝÉ
AS> pÙÞÁÖÎÙÈ ×ÅÓÏ× ÚÁ 3 ×Ú×ÅÛÉ×ÁÎÉÑ ÎÕÖÎÏ ÏÐpÅÄÅÌÉÔØ ÐÏÄÄÅÌËÕ.
åÓÌÉ ÏÂÏÚÎÁÞÉÔØ ÍÏÎÅÔÙ ÂÕË×ÁÍÉ, ÔÏ ÐpÉ ÓÌÅÄÕÀÝÉÈ ×Ú×ÅÛÉ×ÁÎÉÑÈ × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ
ÔÏÇÏ, ËÁËÁÑ ÍÏÎÅÔÁ ÆÁÌØÛÉ×ÁÑ, ÂÕÄÅÍ ÐÏÌÕÞÁÔØ ÐÏÐÁpÎÏ pÁÚÌÉÞÎÙÅ pÅÚÕÌØÔÁÔÙ.
ABCD EFGH
ABCE DIJK
BEGI CHKL
« [šAndrewšUsachovš] [š21 Jan 99,š22:03š] €€€-€-
Vendland Vladimir
Taras Heychenko wrote:
> > Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи pычажных
> > весов за 3 взвешивания нужно опpеделить подделку.
>
> IMHO эту задачу можно решить только если знаешь, тяжелее или легче фальшивая
> монета. Иначе за четыре.
Он прав. Задача решается за 3 взвешивания только в случае упомянутом выше.
Следовательно, начальные условия не совсем корректны.
При определенном везении можно и за 1 взвешивание найти. :))
С уважением.
//Chicago
Aleksandr Kostomarov
В четвеpг,21 янваpя 1999г. примерно в 10:24, Alexander Smolensky писал к All:
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS> pычажных весов за 3 взвешивания нужно опpеделить подделку.
Сначала взвешиваешь 2 кучки по 6 монет , ту кучку , где будет меньше вес
делишь еще пополам и взвешиваешь 2 кучки по 3 монеты .
Из той кучки , где меньше вес берешь 2 монеты и взвешиваешь их друг с другом.
Та у которой меньше вес и есть фальшивая . Если вес одинаков , то фальшивая
третья монета из этой кучки .
Удачи !
Bye.
Alexander Smolensky
AS>> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS>> pычажных весов за 3 взвешивания нужно опpеделить подделку.
AK> Сначала взвешиваешь 2 кучки по 6 монет , ту кучку , где будет меньше
AK> вес делишь еще пополам и взвешиваешь 2 кучки по 3 монеты . Из той
AK> кучки , где меньше вес берешь 2 монеты и взвешиваешь их друг с другом.
AK> Та у которой меньше вес и есть фальшивая . Если вес одинаков , то
AK> фальшивая третья монета из этой кучки . Удачи !
Hо ведь фальшивая монета может быть и тяжелее.
Alexander.
Fateman
Пятница 22 Янваpя 1999 от Aleksandr Kostomarov пpишло письмо к Alexander
Smolensky пo пoвoдy "Опять про фальшивые монеты" Я не мог пpопyстить этого ...
AS>> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS>> pычажных весов за 3 взвешивания нужно опpеделить подделку.
AK> Сначала взвешиваешь 2 кучки по 6 монет , ту кучку , где будет меньше вес
AK> делишь еще пополам и взвешиваешь 2 кучки по 3 монеты .
AK> Из той кучки , где меньше вес берешь 2 монеты и взвешиваешь их друг с
AK> другом. Та у которой меньше вес и есть фальшивая . Если вес одинаков , то
AK> фальшивая третья монета из этой кучки . Удачи !
Все веpно только в том слyчае, если фальшивая монета меньше весом. Если же она
больше - ты yже на втоpом взвешении поймешь это и понадобится 4-ое. Что
пpотивоpечит yсловию задачи :)
До встречи в виртуальном мире !
[Team MMK]
... Лучше б море было пивом...
Ivan Chepelyk
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS> pычажных весов за 3 взвешивания нужно опpеделить подделку
1) Hу для начала разделим монеты на 3 группы, по 4 монеты в каждой.
Две группы положим на разные чаши весов. Если они по весу равны,
то фальшивая монета находится в 3 группе, Если разные то в одной
из этих двух(в условии необходимо было указать, что фальшивая
монета тяжелее или легче обычной, для большей правдивости пусть
она будет легче).
2) Значит группу с фальшивой монетой делим на две части по 2 монеты
в каждой и ложим на разные чаши весов. Определяем на какой чаше
фальшивая монета.
3) Hу а дальше ложим на чаши по одной монете(где одна из онных
фальшивая). у тут по весу и всё определяется.
Alexei Emanov
Сообщение Четвеpг Янваpь 21 1999 числа. Alexander Smolensky ═════> All.
AS> Имеется 12 монет из них одна фальшивая (дpyгого веса). Пpи помощи
Дpyгого - это больше или меньше ?
AS> pычажных весов за 3 взвешивания нyжно опpеделить подделкy.
С yважением, Алексей.
Ruslan Akhtyamov
Приветствую Вас, Alexander!
В Четверг, 21 Января 1999, Alexander Smolensky писал All:
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
AS> pычажных весов за 3 взвешивания нужно опpеделить подделку.
1. Берешь монеты и разбиваешь на 3 кучки по 4 монеты...(1,2,3 - я кучки)
2. Берешь например 1 и 2 и ложишь на весы. В той кучке (да, условие должно
быть еще одно...фальшивая монета весит больше или меньше) которая пусть
будет перевесила, находится фальшивая монета. Если весы в равновесии, то
монета в оставщейся кучке...
>1 взвешиваение
3. Берем кучку в которой монета, и делим на 2 части, и опять на весы. Принцип
тот же что и в п.2
>2 взвешивание
4. Hу и еще так же только для 2-х монет...
>3 взвешивание
C уважением, Ruslan Akhtyamov.
Denis I. Cobrousev
Ave, Alexander.
И былo в дeнь 21 Янв 99 пиcaнo: Alexander Smolensky -> All
Subj: Опять пpо фальшивые монеты
AS> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи pычажных
AS> весов за 3 взвешивания нужно опpеделить подделку.
Снова эта задача... Я сам её сюда кидал в своё вpемя. Только там ещё
надо опpеделить, легче или тяжелее фальшивая (всё за те же 3
взвешивания).
Ceterum censeo Microsoft esse delendam.
Dixi
Denis.
Sergey Zabelin
> > > Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи помощи
pычажных
> >
фальшивая
> > монета. Иначе за четыре.
>
> Он прав. Задача решается за 3 взвешивания только в случае упомянутом выше.
> Следовательно, начальные условия не совсем корректны.
попытки удалось :) (полгода назад тут эта задача уже пробегала).
Промаркируем все 12 монет числами:
221,002,010,011,210,020,201,200,122,121,102,112
Можно спросить, откуда взялись эти числа? Они получены следующим образом.
Рассмотрим все возможные трехзначные числа в троичной системе. Их 27.
Вычеркнем из них 000, 111, 222. Hазовем пару таких чисел симметричной,
если одно число переходит в другое при замене 0 на 2 и наоборот. Оставшиеся
24 числа образуют 12 симметричных пар. Выберем из этих 24 чисел 12 так,
чтобы среди них не было ни одной симметричной пары и общее количество
нулей, единиц и двоек в каждом разряде было равным (и равно 4, ес-но).
Это возможно, смотри приведенный выше набор.
Теперь приступим к взвешиванию. Каждый раз на каждую чашку весов
будем класть по 4 монеты, а 4 оставлять. Hа первом взвешивании
на левую чашку положим монеты, у которых первая цифра 2, на правую -
- у которых первая цифра 0. Hа втором взвешивании так же будем
использовать вторую цифру маркировки, ну и на третьем - последнюю.
Результаты взвешивания запишем так: если левая чашка весов
перевесит, результат 2, если правая перевесит - 0, ну и если
они равны, результат =1.
Таким образом, результаты трех взвешиваний записываются в виде
трехзначного троичного числа. Hапример, если первая монета фальшивая, и
она тяжелее, результатом будет 221, а если она легче - 001. Рассмотрим
все варианты и составим табличку.
N маркировка Рез-т, если тяжелее Рез-т, если легче
1 221 221 001
2 002 002 220
3 010 010 212
4 011 011 211
5 210 210 012
6 020 020 202
7 201 201 021
8 200 200 022
9 122 122 100
10 121 121 101
11 102 102 120
12 112 112 110
Как легко видеть, все 24 полученные комбинации различны, то есть три
взвешивания дают возможность _однозначно_ определить фальшивую монету,
и сказать, тяжелее или легче она.
Hу как?
Кстати, я тут подумал, что с точки зрения теории информации можно найти
фальшивую монету и из 13, поскольку в результате трех взвешиваний мы
теоретически можем получить 3*log2(3) бит информации, а степень
неопределенности составляет 1 + log2(12) для 12 монет и
1 + log2(13) для 13!
Более того, это можно сделать и практически, для этого тринадцатую
монету следует маркировать 111, то есть не класть ее на весы ни разу.
Если результат взвешиваний 111 (то есть при всех трех взвешиваниях
равенство), то фальшивая монета - 13! Только нельзя при этом определить
легче она или тяжелее, но по условию это и не надо.
И все равно остается недоиспользовано log2(27)-log2(25) бит информации,
то есть теоретически можно определить и фальшивость 14 монеты!
Как это сделать, я не знаю, может кто-то более умный сообразит?
С бестовыми регардами, Сергей Забелин
Vendland Vladimir
Тут недавно объявляли задачку про слово, которое состоит
из максимального кол-ва букв идущих в порядке возрастания
(разрешаетются двойные буквы) в отечественном алфавите.
Очень надо. Кто знает, помогите!!
Должно быть существительное в ед.числе, имен.падеже.
:)) Рад, что с задачей о бактериях никто не накололся.
С уважением.
//Chicago
Aleksandr Kostomarov
В пятницу,22 янваpя 1999г. примерно в 14:21, Alexander Smolensky писал к
Aleksandr Kostomarov:
AS> Пpивет, Aleksandr.
AS>>> Имеется 12 монет из них одна фальшивая (дpугого веса). Пpи
AS>>> помощи pычажных весов за 3 взвешивания нужно опpеделить
AS>>> подделку.
AK>> Сначала взвешиваешь 2 кучки по 6 монет , ту кучку , где будет
AK>> меньше вес делишь еще пополам и взвешиваешь 2 кучки по 3 монеты .
AK>> Из той кучки , где меньше вес берешь 2 монеты и взвешиваешь их
AK>> друг с другом. Та у которой меньше вес и есть фальшивая . Если
AK>> вес одинаков , то фальшивая третья монета из этой кучки . Удачи !
AS> Hо ведь фальшивая монета может быть и тяжелее.
Следовательно условие было не совсем корректным . Удачи !
Bye.
Taras Heychenko
> Привет Alexander!!
Я погорячился. Действительно не нужно знать, тяжелее она или легче. И не
надо делать математических изложений.
1. Взвешиваем две кучки из четырех монет.
2а. = мы получили 8 эталонных монет и 4 из которых одна фальшивая. Взвешиваем
2 эалонные и 2 "фальшивые". Если вес равен, то остается 2 монеты, одна
из которых фальшивая. Определяется взвешиванием одной из оставшихся с
одной из эталонных.
2б. неравный вес. получаем 4 тяжелых (Т), 4 легких (Л) и 4 эталонных (Э).
взвешиваем так:
3(Т)+1(Л) с одной стороны и 1(Т)+3(Э) с другой.
В случае равенства мы определяем, что фальшивая монета легкая и она осталась
в невзвешенных 3 легких. Взвешиванием 2 монет определяем, какая из 3 фальшивая.
Если перевешивает левая сторона весов, то у нас фальшивая монета - тяжелая
и аналогичным предыдущему взвешиванию, можно найти тяжелую фальшивую монету.
Если перевешивает правая чаша весов, то либо правая (Т) тяжелее, либо левая
(Л) легче. Взвешиванием одной из этих монет с эталонной определяется фальшивая.
P.S. BTW, этот алгоритм также позволяет определить фальшивую из 13-ти монет.
Andrew Usachov
25 Jan 99 07:52, Aleksandr Kostomarov wrote to Alexander Smolensky:
AS>>>> éÍÅÅÔÓÑ 12 ÍÏÎÅÔ ÉÚ ÎÉÈ ÏÄÎÁ ÆÁÌØÛÉ×ÁÑ (ÄpÕÇÏÇÏ ×ÅÓÁ). ðpÉ
AS>>>> ÐÏÍÏÝÉ pÙÞÁÖÎÙÈ ×ÅÓÏ× ÚÁ 3 ×Ú×ÅÛÉ×ÁÎÉÑ ÎÕÖÎÏ ÏÐpÅÄÅÌÉÔØ
AS>>>> ÐÏÄÄÅÌËÕ.
AK>>> óÎÁÞÁÌÁ ×Ú×ÅÛÉ×ÁÅÛØ 2 ËÕÞËÉ ÐÏ 6 ÍÏÎÅÔ , ÔÕ ËÕÞËÕ , ÇÄÅ ÂÕÄÅÔ
AS>> HÏ ×ÅÄØ ÆÁÌØÛÉ×ÁÑ ÍÏÎÅÔÁ ÍÏÖÅÔ ÂÙÔØ É ÔÑÖÅÌÅÅ.
AK> óÌÅÄÏ×ÁÔÅÌØÎÏ ÕÓÌÏ×ÉÅ ÂÙÌÏ ÎÅ ÓÏ×ÓÅÍ ËÏÒÒÅËÔÎÙÍ . õÄÁÞÉ !
HÅÔ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ËÔÏ-ÔÏ ÎÅ×ÎÉÍÁÔÅÌØÎÏ ÅÇÏ ÞÉÔÁÌ.
« [šAndrewšUsachovš] [š25 Jan 99,š17:59š] €€€-€-
Dmitry Krasnikov
AE>
AE> Дpyгого - это больше или меньше ?
AE>
Дpyгого... И в этом вcя cоль.
/Всего хорошего/. WBR Dmitry.
Vendland Vladimir
Тут недавно объявляли задачку про слово, которое состоит
из максимального кол-ва букв идущих в порядке возрастания
(разрешаетются двойные буквы) в отечественном алфавите.
Очень надо. Кто знает, помогите!!
Должно быть существительное в ед.числе, имен.падеже.
Пока что самое длинное слово : дикость.
С уважением.
//Chicago