Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, также упорядоченные по весу. Известно, что все монеты различны по весу. В нашем распоряжении - двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую по весы 101-е место? Укажите это число и докажите, что меньшим числом взвешиваний обойтись нельзя.

уточнение: 101- это сто первая или сто одна?
"занимающую по весы 101-е место?"- имелось ввиду "весу"?

суббота, вечер....)

Да, сто первое место по весу.

101 золотая монета - это сто первая или сто одна?

берем крайние легкие и тяжелые, разбиваем пополам (50 сер и 51зол) и сравниваем, а дальше по алгоритму сравнения - около 8-10 итераций. вроде так.

и хватит на сегодня, 40 минут убил

жаль макросы писать не умею ) пришлось блок схемы рисовать)

Не понял. Берем, что ли среднюю монету (сер) и сравниваем с золотыми? Или как? Подробнее нельзя?

На первый взгляд это будет сумма алгебраической прогрессии от 1 до 100 с разностью 1 и равна 5050

Еще можно рассуждать так:
Нам нужно найти самую тяжелую монету. Тогда разобьем монеты на 50 пар и одну монету без пары. Сравним 2 монеты в каждой паре. Выберем самые тяжелые из каждой пары. Выйдет 50 монет + 1. Потом получим 25 монет. Всего 26. Разобьем на 13 пар и получим 13. Потом 6 пар + 1. Далее 3 + 1. потом 2. И в конце получим наитяжелейшую. Всего 99 взвешиваний.

Золотые монеты уже упорядочены по весу. Серебряные тоже. Нужно найти монету (среди золотых и серебряных), которая займет 101-е место среди общей кучи.

Все понял. Их всего 201 монет.

Тогда задача еще проще.

А - серебряные веса.
В - золотые веса.

Первое взвешивание: сравниваем min(A) и min(B). Это будет начало цепочки. Пусть будет min(A)=min(min(A),min(B)).
Второе взвешивание: min(A-min(A)) и min(B). Пусть теперь это будет min(B).
Третье: min(A-min(A)) и min(B-min(B)).

Остановимся на 101 монете по весу.

Таким образом делаем всего 50 взвешиваний.

проще ))

и так мы знаем что монеты упорядочены по весу, знаем что №1 это самая легкая № 100 (101 -золотая) тяжелые из своих рядов, сравниваем два ряда по середине, 50 серебро и 51 золото, если 51"З">50"C", то нужная монета находится где-то среди монет 52-101 золотой и 1-50 сеpебpяной. Если наоборот - то монета наоборот, дальше по такому же принципу

8 действий = [log2(201)] + 1
Если правильно условие понял

P.S. обычная школьная олимпиадная задачка для 7-8 класса.

Я дам вам контр пример к вашему ошибочному методу.

Контр пример:
x[n]= веса серебряных монет с номером n.
y[n]= веса золотых монет с номером n.

x[1]=1 грамм ,x[50]=1.5, x[100]=2 грамм.

y[1]=3 грамм, y[51]=4.

Следуя вашему методу нужная монета находится где-то среди монет 52-101 золотой и 1-50 сеpебpяной. Но 101 по весу монета наша - это первая золотая.

все монеты разложим в поpядке возpастания pазмеpа: золотые отдельно, сеpебpяные отдельно. Пyсть пеpвая по счетy в каждом pядy монета самая большая (и тяжелая). Сpеднюю по весy монетy можно найти, последовательно взвешивая сpединные монеты каждой из оставшихся линеек.
1. Взвешиваем 51-ю золотyю монетy и 50-ю сеpебpянyю. Если пеpвая тяжелее, то искомая монета находится где-то сpеди 52-101 золотой и 1-50 сеpебpяной. Если легче, то искомая монета находится где-то сpеди 1-51 золотой и 51-100 сеpебpяной. То есть, 51+50 монет. Остальные можно отложить.
2. Взвешиваем опять сpединные монеты. Так как число ваpиантов pастет в геометpической пpогpессии, бyдy pассматpивать только итоги ;) Из 51+50 монет выбиpаем сpавниваем 25 и 26 монеты. Остается 26+25 монет.
3. Взвешиваем 13 и 13 монеты. Остается 13+13 или 13+12. Далее бyдy pассматpивать только слyчай 13+13, 13+12 аналогично.
4. Взвешиваем 7 и 7. Остается 7+7.
5. Взвешиваем 4 и 3. Остается 4+3.
6. Здесь могy поподpобнее, так как монет осталось мало ;) Пyсть остались золотые монеты 1234 и сеpебpяные ABC (все в поpядке возpастания). Взвешиваем 2 и B. Если 2>B, то сpедняя монета какая-то из 34AB, если нет, то из 12C. Рассмотpи пеpвый слyчай.
7. Взвешиваем 3 и A. Если 3
взвешиваем 3 и B. Какая больше, та и искомая.
если 3>A, то:
взвешиваем 4 и A. Какая больше, та и искомая.


(это не я такая умная, просто на самом деле у этой задачи условия - определите за 8 взвешиваний ....)

Да что вы говорите...

Вы мой контр пример видели? Он показывает неверность вашего рассуждения, и без того не обоснованного.

я ваши игреки тем более не пойму, мое рассуждение основано на гугле, я философ а не математик

Вы попробуйте просто прочитать. Там все черным по белому написано. Если вы 8 классов окончили, то поймете.

Там показано, что если взять 51 золотую больше по весу 50 серебряной, то НЕ следует то что вы написали. То есть ошибка с самого начала ваших с гуглом рассуждений.

Каждый математик есть философ и наоборот.

мнепох на саммом деле

Наоборот: если 51-я золотая монета тяжелее, то искомая - среди 1-51-й золотой и 51-100-й серебряной.

кулл!

круто..я вообще ничего не понял