2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Классика - взвешиваем монетки
Сообщение12.06.2016, 22:25 
Если кому эта задачка покажется излишне простой, то просто скажите что знаете решение, не обязательно его озвучивать - вдруг найдутся те кому будет интересно порешать. Я со своей стороны хочу узнать степень ее легкости, чтобы знать на какой уровень предлагать. Условие просто донельзя - есть 38 внешне неотличимых монет, рычажные весы, одна монета фальшивая - отличается от других по весу. Надо за 4 взвешивания найти фальшивую монету.

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение12.06.2016, 23:14 
Аватара пользователя
Это олимпиадная задача для 7-8 классов. (видел в задачнике в этом разделе)

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение12.06.2016, 23:20 
А вы знаете как ее решить?

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:08 
UPD: ставка выросла до 40 монет.

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:28 
Аватара пользователя
В случае с 38-ми монетами отложить 14 в сторону. На весы поставить по 12. Если сравняются то оставшиеся 14 можно за 3 измерения. Если нет то среди тех (24-х), что на весах тоже можно найти за 3 взвешивания.

(Оффтоп)

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

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:29 
А в случае с 40? Давайте уж по повышенным ставкам, как 7-классники - решать сразу про 40.

-- 13.06.2016, 01:36 --

TelmanStud в сообщении #1131123 писал(а):
А Вы про 40 уверены?

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

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

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

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 02:15 
Думаю, знатоки расскажут что-то про троичную симметричную систему счисления и прочие умные слова. А я просто кустарно вариантики прикидывал, да рекурсию применял (она то меня и подвела, 38 я первоначально получил откладывая 12 монет - поэтому и 40 должны быть верными :-) )

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 03:37 
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$

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 09:52 
_Ivana в сообщении #1131099 писал(а):
Если кому эта задачка покажется излишне простой, то просто скажите что знаете решение, не обязательно его озвучивать - вдруг найдутся те кому будет интересно порешать. Я со своей стороны хочу узнать степень ее легкости, чтобы знать на какой уровень предлагать.
Зная решение, трудно оценить степень легкости. Но степень известности очень высока.
Потому лучше взять что-то менее избитое типа:
Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

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

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 15:45 
Цитата:
Имеется 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б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные, если нет - то более
легкая- фальшивая.

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 16:16 
Аватара пользователя
chh в сообщении #1131270 писал(а):
3б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные

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

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 16:20 
whitefox в сообщении #1131286 писал(а):
chh в сообщении #1131270 писал(а):
3б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные

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

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

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение17.06.2016, 05:00 
TelmanStud в сообщении #1131132 писал(а):
Интересно откуда такая формула
после написания программы, решающей данную задачку в общем случае для любого заданного числа взвешиваний и количества монет, я тоже могу сказать, что при оптимальном алгоритме у нас каждое взвешивание оставляет треть от первоначального диапазон поиска, но одно взвешивание оставляет две трети - получаем за определенное число взвешиваний сужение диапазона поиска в два делить на три в степени число взвешиваний, и когда поиск сужается до одной монеты, задача решена.

 
 
 
 Re: Классика - взвешиваем монетки
Сообщение27.07.2016, 11:51 
VAL в сообщении #1131175 писал(а):
_Ivana в сообщении #1131099 писал(а):
Если кому эта задачка покажется излишне простой, то просто скажите что знаете решение, не обязательно его озвучивать - вдруг найдутся те кому будет интересно порешать. Я со своей стороны хочу узнать степень ее легкости, чтобы знать на какой уровень предлагать.
Зная решение, трудно оценить степень легкости. Но степень известности очень высока.
Потому лучше взять что-то менее избитое типа:
Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

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


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

 
 
 [ Сообщений: 54 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group