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

[ql^2/8]

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


* * *
Почивните дни май ще са по-прохладни. Хубав уикенд!

[Bibi]

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

[ql^2/8]

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

Хахаха, знаех си, че съм забравил нещо!

Благодаря ти за въпроса!
Разполагаме с везна, без тежести!

[Bibi]

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

[protonic]

Разбира се, че не - нали в това е сложността

[Bibi]

Хмм. Явно нещо пропускам да съобразя? Ако теглата на монетите от един вид са на равни разстояния помежду си, сложността пак не ми изглежда малка.
Търсим онази монета, от която има 100 по-леки и 100 по-тежки, нали така?

[ql^2/8]

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

Не, няма такова правило.
Само монетата с по-голям номинал е по-тежка от монета с по-малък номинал
от същия материал.

[protonic]

Хайде жокер - първо теглене - две монети - 51 юана срещу 50 рубли

[Bibi]

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

[ql^2/8]

Да кажем, че жокерът беше доста силен!
Интересно е да видим решението?

[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-мото теглене.

[ql^2/8]

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

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

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

[Bibi]

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

[ql^2/8]

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

Все пак ако в един момент останем с четен брой монети,
понятието "средна по тежест" вече се раздвоява...

[Bibi]

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

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