Задача за претегляне

Преглед за печат

22-08-14, 11:56
ql^2/8

Задача за претегляне

Не знам дали има по-обширна тема в логическите задачи
от тези за претегляне, при това най-вече на монети. Може би
могат да се конкурират само с тези за говорещите лъжа-истина...
Е, тук ви предлагам още една.
* * *
Задача:
Разполагаме със 101 златни монети, с номинал от 1 до 101 американски юани,
а също и 100 сребърни монети с номинал от 1 до 100 канадски рубли.
Всички монети са с различно тегло, като тези с по-висок номинал са по-тежки
от тези с по-нисък. С колко най-малко претегляния можем да определим
средната по тегло от всичките 201 монети? Обменният курс не е известен.
:)

* * *
Почивните дни май ще са по-прохладни. Хубав уикенд!
22-08-14, 12:20
Bibi

Отговор: Задача за претегляне

С везна ли разполагаме?
22-08-14, 14:33
ql^2/8

Отговор: Задача за претегляне

Цитат:

Първоначално публикувано от Bibi

С везна ли разполагаме?

Хахаха, знаех си, че съм забравил нещо!
:)
Благодаря ти за въпроса!
Разполагаме с везна, без тежести!
22-08-14, 21:14
Bibi

Отговор: Задача за претегляне

Пак имам въпрос, защото без отговорът не мога да си приложа идеята.
Във всяка шепа дали важи правилото, че монетата с номинал 1 плюс тази, с 2 се равняват по тегло на монетата 3?
Ако е така, бих могла с около 8 претегляния да се оправя.
Подозирам, че това постижение може да се подобри.
22-08-14, 21:21
protonic

Отговор: Задача за претегляне

Разбира се, че не - нали в това е сложността :)
22-08-14, 22:01
Bibi

Отговор: Задача за претегляне

Хмм. Явно нещо пропускам да съобразя? Ако теглата на монетите от един вид са на равни разстояния помежду си, сложността пак не ми изглежда малка.
Търсим онази монета, от която има 100 по-леки и 100 по-тежки, нали така?
22-08-14, 23:22
ql^2/8

Отговор: Задача за претегляне

Цитат:

Първоначално публикувано от Bibi

Пак имам въпрос, защото без отговорът не мога да си приложа идеята.
Във всяка шепа дали важи правилото, че монетата с номинал 1 плюс тази, с 2 се равняват по тегло на монетата 3?
Ако е така, бих могла с около 8 претегляния да се оправя.
Подозирам, че това постижение може да се подобри.

Не, няма такова правило.
Само монетата с по-голям номинал е по-тежка от монета с по-малък номинал
от същия материал.
23-08-14, 11:51
protonic

Отговор: Задача за претегляне

Хайде жокер - първо теглене - две монети - 51 юана срещу 50 рубли
25-08-14, 11:33
Bibi

Отговор: Задача за претегляне

След което можем да махнем вдясно всички, които са по-тежки от по-тежката от тях и са от нейната серия. И аналогично да махнем вляво всички по-леки или равни на другата.
Махаме ги, понеже търсената положително не е сред тях. Те са 100 на брой: 50+50 или 51+49. Остават 101 кандидата за много подобна задача.
Продължаваме с двоично деление. Ще трябват общо 7 претегляния.
Ако това е идеята, мога да я разпиша по-прецизно.
25-08-14, 18:27
ql^2/8

Отговор: Задача за претегляне

Да кажем, че жокерът беше доста силен!
Интересно е да видим решението?
25-08-14, 19:15
Bibi

Отговор: Задача за претегляне

Малко се затруднявам да измисля хубав начин да го разкажа. Положително с някаква графика или нещо подобно би могло да се докара доста по-ясно, отколкото с думи.

Ако 51-вия юан е по-тежък от 50-тата рубла.
За всеки следващ юан от 52 до 101 знаем, че има поне 101 монети, които са по-леки от него. Това са първите 51 юана (по условие) и първите 50 рубли (според първото мерене). А ние търсим монета, от която има само 100 по-леки. Значи тези 50 отпадат от подозрение.
Също за всяка рубла от 1 до 50 може да се види, че има поне 101 монети, които са по-тежки от нея. Това са 50-те най-тежки рубли и 51 най-тежки юани.
Така само след едно мерене стесняваме мястото на търсената монета: от 1 до 51 юан или от 51 до 100 рубла.
На второто теглене можем да сравним 26-тия юан със 75-тата рубла.
Ако е по-тежък, ще можем да изключим 27-51 юан и 51-75 рубла.
Ако е по-лек, ще бъдат изключени 76-100 рубли и 1-26 юани.
След всяко следващо мерене все повече стесняваме зоната, докато не ни остане само една монета. Което би трябвало да се случи след 7-мото теглене.
26-08-14, 09:59
ql^2/8

Отговор: Задача за претегляне

Струва ми се, че проверяваш дали внимавам?

Цитат:

Първоначално публикувано от Bibi

. . .
Така само след едно мерене стесняваме мястото на търсената монета: от 1 до 51 юан или от 51 до 100 рубла.
На второто теглене можем да сравним 26-тия юан със 75-тата рубла.
. . .
Ако е по-лек, ще бъдат изключени 76-100 рубли и 1-26 юани.
. . .

Да се преброим - останаха рубли от 51 до 75 (25 броя), юани от 27 до 51 (25 броя).
Въпрос - от тези 50 коя ще е средната?
26-08-14, 13:32
Bibi

Отговор: Задача за претегляне

Този проблем го имам още на първата стъпка.
Но не знам доколко е проблем. Може да се окаже, че не е.
Важното е да се сравняват монети, със сума 101. И да се стеснява зоната, докато уловим рибката.
А може и да дрънкам глупости.
26-08-14, 15:12
ql^2/8

Отговор: Задача за претегляне

Цитат:

Първоначално публикувано от Bibi

Този проблем го имам още на първата стъпка.
Но не знам доколко е проблем. Може да се окаже, че не е.
Важното е да се сравняват монети, със сума 101. И да се стеснява зоната, докато уловим рибката.
А може и да дрънкам глупости.

Все пак ако в един момент останем с четен брой монети,
понятието "средна по тежест" вече се раздвоява...
26-08-14, 17:48
Bibi

Отговор: Задача за претегляне

Ние през цялото време търсим монета, от която има точно 100 по-леки и 100 по-тежки.
Когато стесняваме "кръга заподозрени", не редуцираме това условие - т.е. продължаваме да отхвърляме само такива, за които намираме поне 101 от едната им страна.
Това дали върши работа?

Примерно когато сравнявам 26-тия юан със 75-тата рубла. Вскички юани от 27 нагоре ги изключвам, понеже от тях има поне 101 по-леки (26+75). А не търся просто 51 по-леки.