2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Классика - взвешиваем монетки
Сообщение12.06.2016, 22:25 


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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение12.06.2016, 23:14 
Аватара пользователя


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

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


05/09/12
2587
А вы знаете как ее решить?

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:08 


05/09/12
2587
UPD: ставка выросла до 40 монет.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:28 
Аватара пользователя


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 01:29 


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

-- 13.06.2016, 01:36 --

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

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

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 02:06 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 02:15 


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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 03:37 


08/05/08
593
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 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 15:45 


12/04/16

305
Цитата:
Имеется 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 
Заслуженный участник
Аватара пользователя


19/12/10
1546
chh в сообщении #1131270 писал(а):
3б)г) Взвешиваем две серебряных монетки с левой чаши. Если наблюдается равенство, то они обе нормальные

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение13.06.2016, 16:20 


12/04/16

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

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

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение17.06.2016, 05:00 


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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение27.07.2016, 11:51 


12/04/16

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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу 1, 2, 3, 4  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group