Вход на сайт

МЕДИАМЕТРИКА

Облако тегов

Задача в пятницу. Классика

Аватар пользователя serghey

3ад.1 Как найти фальшивую монету (13 монет, 3 взвешивания)

Даны 13 монет, одна из которых фальшивая. Фальшивая монета отличается от остальных по весу, остальные весят одинаково. Причем мы НЕ знаем, тяжелее или легче остальных фальшивая монета. Требуется за 3 взвешивания на аптекарских весах с 2 чашечками и без использования гирь определить, какая из монет фальшивая.

Предлагается решить, не прибегая к услугам сопроцессора)

Правильный ответ мы получили от   Xtriss(19:00:26 / 07-12-2012) "Эврика! 13 монет раскладываем на кучки 4, 4 и 5...", но дадим его в более схематичной форме:

13 монет, 3 группы: 1 2 3 4, 5 6 7 8, 9 10 11 12 13. При взвешивании на аптекарских весах возможны результаты: стрелка не отклонилась (==), ушла вправо (>>), ушла влево(<<). Слева в соотношениях то, что на левой чашке весов, справа то, что на правой )))

1.       Взвешиваем "кандидатов" 1+2+3+4 и 5+6+7+8.Возможны 2 варианта: 1.1. == и 2.1. >> (или <<)

1.1.    1+2+3+4==5+6+7+8 -> следовательно, фальш в 3-й группе, задача "Определить фальш среди 5 монет за 2 взвешивания":

1.1.1. Взвешиваем любые нефальшивые, например, 1+2+3 и "кандидаты" 9+10+11. Возможны 2 варианта 1.1.1.1.== и 1.1.1.2. >> (или <<):

1.1.1.1. Если 1+2+3==9+10+11, то 12 или 13 - фальш!Взвешиваем нефальшивый 1 и "кандидат" 12:если а) ==, то 13 - фальш (но "знак" неопределен)!,если б) >> (или <<), то 12 - фальш со "знаком"!

1.1.1.2. Если 1+2+3>> (или <<) 9+10+11, то опеределен "знак"!Взвешиваем "кандидат" 9 и "кандидат" 10:если а) "знак" {>> (или <<)} НЕ переменился, то 10 - фальш со "знаком"!если б) "знак" переменился и стал << (или >>), то 9 - фальш со "знаком"!если в) "знак" переменился и стал ==, то 11 - фальш со "знаком"!

2.1.  1+2+3+4 >> (или <<) 5+6+7+8 -> следовательно, в 3-й группе нет фальшивых монет .

2.1.1. Складываем на левой чашке монеты с номерами 1+5+6+7, на правой 9+10+11+8. (То есть справа налево передали 3 кандидатских монеты и заменили их на нефальшивые из резерва). Взвешиваем 1+5+6+7 и 9+10+11+8. Возможны варианты:  2.1.1.1. ==, 2.1.1.2. >> (или <<, "знак" не переменился) и 2.1.1.3. << (или >>, "знак" переменился):

2.1.1.1. 1+5+6+7 == 9+10+11+8 -> среди этих восьми монет НЕТ фальшивых, а фальшивая или 2 или  3 или 4! Взвешиваем 3 и 4, если ==, то 2 фальшивая со "знаком", иначе "знак" указывает фальшивую из пары монет 3 и 4 (со "знаком")

2.1.1.2. 1+5+6+7 >> (или <<, "знак" НЕ переменился) 9+10+11+8 -> среди этих восьми монет фальшивая или 1 или 8! Взвешиваем 1 и 2, , если ==, то 8 фальшивая со "знаком", иначе "знак" указывает на фальшивую монету 1 (со "знаком")!

2.1.1.3. 1+5+6+7 << (или >>, "знак" переменился) 9+10+11+8 -> фальшивая или 5 или  6 или 7! Взвешиваем 5 и 6, если ==, то 7 фальшивая со "знаком", иначе "знак" указывает фальшивую из пары монет 5 и 6 (со "знаком")

Во всех случаях, за исключением варианта "если а) ==, то 13 - фальш (но "знак" неопределен)!," фальшивая монета определяется со знаком, то есть, определяется тяжелее она или легче, чем остальные 12 монет.

Задача с простенько сформулированным условием оказалась совсем непростой)))

Сорри фо дилей. Всем успехов!

3ад.2 Задача-подсказка: Есть 7 монет, одна из них тяжелее остальных. Есть чашечные весы. Нужно за 2 взвешивания найти фальшивую.

Правильный ответ от   Xtriss(19:30:29 / 07-12-2012)

Да вторая легкая: 7=2+2+3.

1) Сравниваем 2 и 2. Если равны, значит одна из трёх фальшивка.

2) Две из трёх взвешиваем между собой.
Равны -> фальшивка третья, не равны ->фальшивка та, что тяжелее (из условия)

3) Сравнили 2 и 2. Пусть левая чаша весов легче, т.е. 2<2. Тогда понятно, что фальшивка лежит на правой чаше (из условия она тяжелее)

4) Одну их монет с правой чаши взвешиваем с эталоном. Равны -> фальшивка та, что не
взвешивали, не равны -> фальшивка то, что тяжелее (из условия) Две взвешиваем между собой, как в 2). Они, разумеется, не равны ->фальшивка та, что тяжелее (из условия)
Фонд поддержки авторов AfterShock

Комментарии

Аватар пользователя Дмитрий Кодунец

Так 12 или 13 монет-то? :)

Аватар пользователя Vneroznikov

Именно 13. Я эту задачу со школы помню.

Аватар пользователя nhfvdfq71
nhfvdfq71(5 лет 6 месяцев)(19:24:38 / 07-12-2012)

1. Берем 6 монет взвешиваем по три на весах. Если не фальшивые, то равенство.

2. Из 7  или 6 берем 4 взвешиваем по две.

3. Из 3 или 2  взвешиваем по одной.

Аватар пользователя alex_midway
alex_midway(5 лет 10 месяцев)(19:42:09 / 07-12-2012)

:-)

Условие перечитайте: 3 взвешивания.

Аватар пользователя nhfvdfq71
nhfvdfq71(5 лет 6 месяцев)(19:42:56 / 07-12-2012)

А я сколько написал?

Аватар пользователя eprst
eprst(5 лет 8 месяцев)(19:43:41 / 07-12-2012)

Написали 3, но пролетели конкретно.

Аватар пользователя nhfvdfq71
nhfvdfq71(5 лет 6 месяцев)(19:45:33 / 07-12-2012)

Ну, да ))) С такой же вероятностью можно и угадать, где фальшивка. Не знаю я ответа (((

Аватар пользователя mr_telecom
mr_telecom(5 лет 11 месяцев)(19:47:04 / 07-12-2012)

Или берем 12 монет, взвешиваем по 6 если  = то фальшивка найдена, если нет, то ->

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

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(19:49:41 / 07-12-2012)

прочитайте условие задачи еще раз

Аватар пользователя mr_telecom
mr_telecom(5 лет 11 месяцев)(20:09:36 / 07-12-2012)

Я с первого раза умею читать!

Не важно, тяжелее или нет монета.

Аватар пользователя Koshe
Koshe(5 лет 11 месяцев)(21:13:39 / 07-12-2012)

А если в кучке потяжелее, при взвешивании по три, они оказались равны? Получается осталось одно взвешивание и кучка из 6 монет...

Аватар пользователя mr_telecom
mr_telecom(5 лет 11 месяцев)(21:16:19 / 07-12-2012)

Да, косяк, мой алгоритм только в 4 хода решает задачку... (

Аватар пользователя Koshe
Koshe(5 лет 11 месяцев)(21:29:02 / 07-12-2012)

Я тоже как ни поворачивал, меньше 4 не получается)))

П.С.

вроде правильный алгоритм ниже есть. хоть и нифига не простой)))

Аватар пользователя nhfvdfq71
nhfvdfq71(5 лет 6 месяцев)(19:51:48 / 07-12-2012)

Точняк. Надо не с 6 начинать... Это б элементарно было.

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(19:57:38 / 07-12-2012)

3ад.2 Задача-подсказка: Есть 7 монет, одна из них тяжелее остальных. Есть чашечные весы. Нужно за 2 взвешивания найти фальшивую.

Аватар пользователя Anugan
Anugan(5 лет 11 месяцев)(20:08:34 / 07-12-2012)

Да эта вообще легкая задача: 1) 3 кучки: 4,4 и 5 монет. Взвешиваем 4 и 4 2) если равны взвешиваем 2 и 2 из кучки с 5 монетами. Пятая отдельно. Если не равны взвешиваем 2 и 2 с более легкой кучки 3) Если из кучки по 5 монет 2 по 2 равны, значит пятая монета фальшивая. Если из кучки с 4 монетами, взвешиваем 1 и 1 из более лёгкой кучки по 2 монеты. Элементарно

Аватар пользователя eprst
eprst(5 лет 8 месяцев)(20:20:35 / 07-12-2012)

Облом.

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:05:12 / 07-12-2012)

В задаче не сказано, что фальшиваяя монета обзательно легче, она может быть и тяжелее настоящей!

Аватар пользователя tokomak
tokomak(6 лет 5 дней)(20:32:29 / 07-12-2012)

Вторая задача решаема, по схеме: два к двум, а три лежат в сторонке... и всё из-за того, что фальшивая монета именно тяжелее (ну, или легче) - как условие задачи.

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

 

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:00:26 / 07-12-2012)

Эврика!

13 монет раскладываем на кучки 4, 4 и 5

Первое взвешивание - кладем на чаши весов 4 и 4 монет.

Линия первая - вес кучек оказался равный, значит фальшивая монета среди пяти отложенных. У нас есть 8 эталонных настоящих монет. Разбиваем кучку из 5 подозрительных на 2 и 3 монеты.

Второе взвешивание. Берем 3 эталонных монеты и взвешиваем с тремя из подозрательной кучки.

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

Допустим, во втором взвешивании 3 эталонных и 3 подозрительных монет вес не равен (значит фальшивка среди них и ещё 2 можно не взвешивать - они годные). Если три эталонные монеты весят больше, значит фальшивка более лёгкая. Раскладываем три подозрительные монеты по одиночке и взвешиваем две из них. Это третье взвешивание. Если вес равен, значит фальшивая не взвешивалась в третий раз. Если вес не равен, то фальшивая та которая легче (ма это определили из группового взвешивания трёх монет).

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

Фух, первая линия закончилась. Возвращаемся к случаю, если при первом взвешивании 4 и 4 монет одна из кучек отказалась тяжелее. Тогда мы имеем 5 эталонных монет из третьей кучки.

Пусть левая кучка легче правой. Разбиваем монетки 1+3<1+3 и 5 эталонных. С левой чаши весов снимаем 3 монетки, перекладываем с правой чаши весов 3 монетки на левую чашу, на правой чаше весов к одной оставшейся монетке прикладываем 3 эталонных. Если во втором взвешивании чаши весов урановесились, значит фальшивка среди отложенных монет, причем мы знаем, что фальшивка весит меньше. Как и в первой линии сравниваем две из отложенных между собой и определяем фальшивку.

Если во втором взвешивании знак изменился (стал больше >), значит фальшивка среди переложенных монет, причём она тяжелее подлинной, также выявляем её, взвесив две из трёх переложенных.

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

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

Это без гугла, сама. Мне полагается пирожок? :)))

Аватар пользователя Oberon
Oberon(5 лет 10 месяцев)(21:44:58 / 07-12-2012)

Пусть левая кучка легче правой. Разбиваем монетки 1+3<1+3 и 5 эталонных. С левой чаши весов снимаем 3 монетки, перекладываем с правой чаши весов 3 монетки на левую чашу, на правой чаше весов к одной оставшейся монетке прикладываем 3 эталонных. Если во втором взвешивании чаши весов урановесились, значит фальшивка среди отложенных монет, причем мы знаем, что фальшивка весит меньше. Как и в первой линии сравниваем две из отложенных между собой и определяем фальшивку.

А с чего вы взяли что фальшивка весит меньше?

а извините все верно поздравляю))

Аватар пользователя Oberon
Oberon(5 лет 10 месяцев)(22:05:45 / 07-12-2012)

все таки не понятно.

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

мы же переложили 3 монеты с правой части на левую, Значит возможны 2 варианта или фальшивка справа и ( 1 монета)  и она тяжелее, или же фальшивка стала слева и она легче.(3 монеты.)

 поясните плиз.

Аватар пользователя shaastra
shaastra(5 лет 10 месяцев)(22:29:38 / 07-12-2012)

//  или же фальшивка стала слева и она легче

фальшивка не может стать легче слева, так как ещё в первом взвешивании (по логике перебора вариантов) мы получили правую чашу весов тяжелее, т.е. справа фальшивка уже была тяжелее.

У xtriss правильное решение. Можно медаль :)

Аватар пользователя qroot
qroot(5 лет 3 месяца)(22:35:03 / 07-12-2012)

Да. Смена знака, означает, что фальшивка в трех перекладываемых монетках. А если не меняется то в двух оставшихся.

Вообще, конечно, респект xtriss за решение.

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:02:22 / 07-12-2012)

Я так поняла, ещё никто решение не нашел? Скорее ищите косяк в моем, а то уже хочется медаль нацепить :)))))))))))))))))

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(21:09:11 / 07-12-2012)

а у меня встречный вопрос, помогла ли Вам задача-подсказка?

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:17:53 / 07-12-2012)

Я начала решать задачу, когда подсказки ещё не было. Думала быстро справлюсь, а к стыду своему провозилась почти 2 часа :((

Зато мозг поупражняла!

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(21:23:21 / 07-12-2012)

Попробуйте решить вторую

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:30:29 / 07-12-2012)

Да вторая легкая.

7=2+2+3.

1) Сравниваем 2 и 2. Если равны, значит одна из трёх фальшивка.

2) Две из трёх взвешиваем между собой. Равны -> фальшивка третья, не равны -> фальшивка та что тяжелее (из условия)

1) Сравнили 2 и 2. Пусть левая чаша весов легче, т.е. 2<2. Тогда понятно, что фальшивка лежит на правой чаше (из условия она тяжелее)

2) Одну их монет с правой чаши взвешиваем с эталоном. Равны -> фальшивка та что не взвешивали, не равны -> фальшивка то что тяжелее (из условия)

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(21:35:59 / 07-12-2012)

Этот текст мы поднимем наверх!

Аватар пользователя Oberon
Oberon(5 лет 10 месяцев)(21:24:04 / 07-12-2012)

да тут понятно делим на 4 кучки по 3 монеты

Но у меня все одно 4 взвешивания получается ((

Аватар пользователя Xtriss
Xtriss(5 лет 2 месяца)(21:25:08 / 07-12-2012)

На мой взгляд, главная хитрость задачи не в том, как вычислить подделку, когда известно легче она или тяжелее настоящей, а в том, что надо догадаться перекладывать часть монет между чашечками весов. Дольше всего искала баланс, сколько снять и сколько переложить :)))

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(21:29:10 / 07-12-2012)

ДА

Аватар пользователя Читаювсё

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

Аватар пользователя Oberon
Oberon(5 лет 10 месяцев)(22:07:16 / 07-12-2012)

Можно оригинальное решение  первой задачи?

Аватар пользователя serghey
serghey(5 лет 11 месяцев)(22:59:21 / 07-12-2012)

Да, уже порА))

Аватар пользователя art1st1k
art1st1k(5 лет 10 месяцев)(23:22:17 / 07-12-2012)

1. 3+3. ---- Если не равны, то 7э и 6н. и например левая чаша тяжелее.

2. слева кладем 5э и справа 3н не меняем и добавляем 2н с левой чаши, но не путаем их (2 кучки), а одну 1н откладываем в сторонку. Если снова слева тяжелее, то делаем вывод, что те 3, которые были при первом взвешивании слева - были э. Соответственно, фальшивка легче. Если произошло так, что теперь справа тяжелее, то фальшивка тяжелее э, и она среди тех 2н, которые направо переложили. Если ж ровно, то убранная 1н - фальш.

3. теперь у нас осталось 3н или 2н. И мы знаем, тяжелее или легче фальшивка, и нам осталось взвесить 1н и 1н и по отклонению весов определить, какая из них фальшивка. А если ровно, то оставшаяся из 3х фальш.

Аналогично, если 3+3 в самом начале будет равно, только дальше уже забыл (((,

Аватар пользователя art1st1k
art1st1k(5 лет 10 месяцев)(23:18:19 / 07-12-2012)

.

Аватар пользователя Антон
Антон(5 лет 11 месяцев)(00:46:57 / 08-12-2012)

Вот у меня как раз, если три и три ровно, то не получается. Не хватает взвешивания.

Аватар пользователя Dvorkin
Dvorkin(5 лет 10 месяцев)(00:28:41 / 08-12-2012)

> 3) Сравнили 2 и 2. Пусть левая чаша весов легче, т.е. 2<2. Тогда понятно, что фальшивка лежит на правой чаше (из условия она тяжелее)

(про 7 монет, задача-подсказка)

это правильный ответ? погодите, но ведь нам неизвестно, какая именно из двух монет фальшивая. на втором взвешивании остановиться не выйдет. или я что-т не так понял. имхо, для 7ми монет необходимо от 1 до 3 взвешиваний.

или "(третье) взвешивание с эталоном не считается за взвешивание?" :)

Аватар пользователя Антон
Антон(5 лет 11 месяцев)(00:39:47 / 08-12-2012)

У меня такое решение получилось (наверно можно легче как-то, так как очень через жопу получилось):

1) Берём 8 монеток, взвешиваем по 4.

            Если равны, значит они правильные, тогда

                       2а) Берём из них 3 и сравниваем с тремя из оставшихся пяти (которые ещё не взвешивали).

                                     Если равны,

                                            3аа)      Сравниваем одну из правильных с одной из двух оставшихся.

                                                                Если равны, то фальшивая та,  которую ещё не взвешивали.

                                                                Не равны - значит фальшивая и есть, с которой сравнили.

                                    Если не равны, то мы таким образом узнаём, легче или тяжелее фальшивая

                                           3аб)      Из трёх надо найти фальшивую, зная, легче она или тяжелее. Это понятно как.

           Если не равны. Для удобства пусть будет слева - больше. Значит 5, которые не взвешивали - правильные.

                        2б) Берём 3 слева, 2 справа, взвешиваем с 5 эталонными.

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

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

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

 

Лидеры обсуждений

за 4 часаза суткиза неделю

Лидеры просмотров

за неделюза месяцза год

СМИ

Загрузка...