Классика - взвешиваем монетки

[_Ivana]

Если кому эта задачка покажется излишне простой, то просто скажите что знаете решение, не обязательно его озвучивать - вдруг найдутся те кому будет интересно порешать. Я со своей стороны хочу узнать степень ее легкости, чтобы знать на какой уровень предлагать. Условие просто донельзя - есть 38 внешне неотличимых монет, рычажные весы, одна монета фальшивая - отличается от других по весу. Надо за 4 взвешивания найти фальшивую монету.

[fiztech]

Это олимпиадная задача для 7-8 классов. (видел в задачнике в этом разделе)

[_Ivana]

А вы знаете как ее решить?

[_Ivana]

UPD: ставка выросла до 40 монет.

[TelmanStud]

В случае с 38-ми монетами отложить 14 в сторону. На весы поставить по 12. Если сравняются то оставшиеся 14 можно за 3 измерения. Если нет то среди тех (24-х), что на весах тоже можно найти за 3 взвешивания.

(Оффтоп)

А Вы про 40 уверены?

[_Ivana]

А в случае с 40? Давайте уж по повышенным ставкам, как 7-классники - решать сразу про 40.

-- 13.06.2016, 01:36 --

TelmanStud в сообщении #1131123 писал(а):

А Вы про 40 уверены?

Я конечно всегда оставляю шанс что ошибся, но в данном случае по моему мнению он невелик.

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

[TelmanStud]

Не удержался)).. Интересно откуда такая формула, что за $N$ взвешиваний можно определить фальшивку (но без ответа больше она остальных или меньше) из $(3^N-1)/2$ монеток.

[_Ivana]

Думаю, знатоки расскажут что-то про троичную симметричную систему счисления и прочие умные слова. А я просто кустарно вариантики прикидывал, да рекурсию применял (она то меня и подвела, 38 я первоначально получил откладывая 12 монет - поэтому и 40 должны быть верными )

[ET]

TelmanStud в сообщении #1131132 писал(а):

Не удержался)).. Интересно откуда такая формула, что за $N$ взвешиваний можно определить фальшивку (но без ответа больше она остальных или меньше) из $(3^N-1)/2$ монеток.

Всего листов у дерева алгоритма $3^N$ При этом для любой монетки, кроме одной, алгоритм еще и скажет - легче она или нет, так что $(3^N+1)/2$
Но при точном $(3^N+1)/2$ задачу можно решить только в случае, если есть еще одна монетка, про которую известно, что она не фальшивая. Если же такой монеты нет,то $(3^N+1)/2-1=(3^N-1)/2$

[VAL]

_Ivana в сообщении #1131099 писал(а):

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

Зная решение, трудно оценить степень легкости. Но степень известности очень высока.
Потому лучше взять что-то менее избитое типа:
Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

Если нужно, могу предложить еще массу вариаций.

[chh]

Цитата:

Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

Для наглядности обозначу все нормальные монеты цифрой 1, а фальшивые - 0.
Золотых монет имеется 1+1+0+0, серебряных - 1+1+1+0.
Разделим серебряные монеты на две одинаковые кучки. Получится всего две комбинации: 1,1 и 1,0.
1. Кладем на левую чашу весов три золотые монетки, а на правую -две серебряных и одну золотую.
Возможны следующие комбинации:
( через запятую - золотая монетка)
а) 110 = 11,0
б) 100 < 11,1
в) 110 > 10,0
г) 100 < 10,1

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

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

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

[whitefox]

chh в сообщении #1131270 писал(а):

3б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные

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

[chh]

whitefox в сообщении #1131286 писал(а):

chh в сообщении #1131270 писал(а):

3б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные

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

Верно подметили ошибку! Буду думать.)

[_Ivana]

TelmanStud в сообщении #1131132 писал(а):

Интересно откуда такая формула

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

[chh]

VAL в сообщении #1131175 писал(а):

_Ivana в сообщении #1131099 писал(а):

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

Зная решение, трудно оценить степень легкости. Но степень известности очень высока.
Потому лучше взять что-то менее избитое типа:
Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

Если нужно, могу предложить еще массу вариаций.

Не получается за три взвешивания!