Которая 101-я?

[fortpost]

Tim0512 - ура!!!

[☭-Изделие 20Д]

1. 50 с 50, те которые меньше до 50 отбрасываем
2. 25 с 25 (из оставшихся). Итого 75 монет
3. 13 с 13. Итого 88 монет
4. 6 с 6. Итого: 94
5. 3 с 3. Итого 97
6. 2 с 2. Итого 99
7. 1 с 1. Итого 100
8. для 101

Я ж говорил - надо к Замату в "Неможет быть"

Здесь случаем ошибки не закралось Именно только про 2 монеты, а не 2 кучки монет
Пока еще подумать не успел  , но если взвешивать только по две(т.е. по одной на чашку) то походу долговато будет - за 50 +1контрольное

Не, не ошибка. Именно только по две монеты можно взвешивать.
[/b]

[☭-Изделие 20Д]

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

Выходит как-то так: - Крошим сотню на 25 четверок.
В каждой четверке взвешиваем
1-2
2-3
3-4
1-4
На базе 4-х взвешиваний худо-бедно выстраиваем четверку по порядку
Всё что было дл этого и будет ниже полностью опирается на условие "...монет, упорядоченных по массе..."

Далее получив 25 упорядоченных внутри четверок, разбиваем на очередные четверки уже их и сравниваем между собой по одной - любой монете 1-й,2-й,3-ей или 4-ой.
В итоге поимеем упорядоченную сотню монет - последнюю 101-ю взвешиваем с любой из сотни - тяжелее, значит это и есть искомая 101-я, легче - значит 101-я - четвертая в 25-й четверке.
ИТОГО: - на всё про всё у меня вышло 101 взвешивание.
КТО СОБИРАЕТСЯ ДОКАЗАТЬ, ЧТО 101-Ю МОНЕТУ МОЖНО ОПРЕДЕЛИТЬ ЗА 7-8 или даже 16 ВЗВЕШИВАНИЙ - чтож (есстественно соблюдая условия поставленные в задаче)
ФЛАГ В РУКИ БАРАБАН НА ШЕЮ И СТРАУСИНОЕ ПЕРО В ЗАДНИЦУ- ВПЕРЕД
могу ещё предложить - паровоз навстречу

[fortpost]

КТО СОБИРАЕТСЯ ДОКАЗАТЬ, ЧТО 101-Ю МОНЕТУ МОЖНО ОПРЕДЕЛИТЬ ЗА 7-8 или даже 16 ВЗВЕШИВАНИЙ - чтож (есстественно соблюдая условия поставленные в задаче)
ФЛАГ В РУКИ БАРАБАН НА ШЕЮ И СТРАУСИНОЕ ПЕРО В ЗАДНИЦУ- ВПЕРЕД
могу ещё предложить - паровоз навстречу

Вдохновившись сим оптимистическим напутствием, приводится попытка доказательства.
Показать скрытый текст

Рассмотрим более общую ситуацию: имеется g золотых монет, упорядоченных по возрастанию массы, s серебряных монет, также упорядоченных по возрастанию массы и мы ищем k-ю по тяжести монету в общем упорядочении всех имеющихся монет. Докажем, что за одно взвешивание мы можем перейти к ситуации с параметрами g', s', k/2, если k чётное, и g', s', [k/2] + 1, если k — нечётное. Для этого сравним [k/2]-е монеты в золотом и серебряном рядах. Без ограничения общности полагаем, что золотая монета тяжелее. Но тогда легче [k/2]-й серебряной монеты может быть лишь ([k/2] – 1) + ([k/2] – 1) ≤ k – 2 монет, значит, серебряные монеты от первой до [k/2]-й можно отбросить. Искомая монета будет теперь иметь номер k/2 при чётном k и [k/2] + 1 — при нечётном, что и требовалось доказать.
Возможен случай, когда в одном из рядов меньше [k/2] монет. Тогда аналогичным рассуждением убеждаемся, что из другого ряда можно выбросить [k/2] монет.
Перед началом взвешиваний имеем: g = 101, s = 100, k = 101. После 1-го взвешивания: k = 51, после 2-го взвешивания: k = 26, после 3-го взвешивания: k = 13, после 4-го взвешивания:
k = 7, после 5-го взвешивания: k = 4, после 6-го взвешивания: k = 2, после 7-го взвешивания: k = 1.
Итак, перед 8-м взвешиванием нам нужно найти самую лёгкую монету. Это легко сделать, сравнив по весу самые лёгкие монеты из двух рядов. Таким образом, 8 взвешиваний достаточно.
Докажем, что меньшим числом взвешиваний обойтись нельзя. Для этого будем смотреть, как меняется в результате взвешивания число подозрительных монет, которые могут оказаться 101-ми по счёту. Вначале подозрительных монет 201, поскольку любая может оказаться 101-й. В результате взвешивания отпадает какое-то множество монет, причём каждая монета может быть исключена из числа подозрительных лишь при одном из результатов взвешивания, либо ни при каком из результатов взвешивания на этом шаге, так как иначе её можно было бы исключить из числа подозрительных монет до этого шага. Но это означает, что при каждом результате взвешивания число подозрительных монет сократится не более чем на половину. Поскольку 2⁷ = 128 < 201, необходимо по крайней мере 8 взвешиваний.

[BIVES]

На базе 4-х взвешиваний худо-бедно выстраиваем четверку по порядку

Во первых так

1-2
2-3
3-4
1-4

вы не выстроите четверку по порядку (может быть ситуация 1-ая>2-ой, 2-ая>3-ей, 3-ья<4-ой, 1-ая>4-ой и мы не знаем какая больше весит 2-ая или 4-ая).
А во вторых в задаче требуется просто,

найдите монету, занимающую по массе 101-е место.

а не упорядочить все первые 101 монеты по возрастанию массы.

[☭-Изделие 20Д]

Показать скрытый текст

КТО СОБИРАЕТСЯ ДОКАЗАТЬ, ЧТО 101-Ю МОНЕТУ МОЖНО ОПРЕДЕЛИТЬ ЗА 7-8 или даже 16 ВЗВЕШИВАНИЙ - чтож (есстественно соблюдая условия поставленные в задаче)
ФЛАГ В РУКИ БАРАБАН НА ШЕЮ И СТРАУСИНОЕ ПЕРО В ЗАДНИЦУ- ВПЕРЕД
могу ещё предложить - паровоз навстречу

Вдохновившись сим оптимистическим напутствием, приводится попытка доказательства.
[spoiler]Рассмотрим более общую ситуацию: имеется g золотых монет, упорядоченных по возрастанию массы, s серебряных монет, также упорядоченных по возрастанию массы и мы ищем k-ю по тяжести монету в общем упорядочении всех имеющихся монет. Докажем, что за одно взвешивание мы можем перейти к ситуации с параметрами g', s', k/2, если k чётное, и g', s', [k/2] + 1, если k — нечётное. Для этого сравним [k/2]-е монеты в золотом и серебряном рядах. Без ограничения общности полагаем, что золотая монета тяжелее. Но тогда легче [k/2]-й серебряной монеты может быть лишь ([k/2] – 1) + ([k/2] – 1) ≤ k – 2 монет, значит, серебряные монеты от первой до [k/2]-й можно отбросить. Искомая монета будет теперь иметь номер k/2 при чётном k и [k/2] + 1 — при нечётном, что и требовалось доказать.
Возможен случай, когда в одном из рядов меньше [k/2] монет. Тогда аналогичным рассуждением убеждаемся, что из другого ряда можно выбросить [k/2] монет.
Перед началом взвешиваний имеем: g = 101, s = 100, k = 101. После 1-го взвешивания: k = 51, после 2-го взвешивания: k = 26, после 3-го взвешивания: k = 13, после 4-го взвешивания:
k = 7, после 5-го взвешивания: k = 4, после 6-го взвешивания: k = 2, после 7-го взвешивания: k = 1.
Итак, перед 8-м взвешиванием нам нужно найти самую лёгкую монету. Это легко сделать, сравнив по весу самые лёгкие монеты из двух рядов. Таким образом, 8 взвешиваний достаточно.
Докажем, что меньшим числом взвешиваний обойтись нельзя. Для этого будем смотреть, как меняется в результате взвешивания число подозрительных монет, которые могут оказаться 101-ми по счёту. Вначале подозрительных монет 201, поскольку любая может оказаться 101-й. В результате взвешивания отпадает какое-то множество монет, причём каждая монета может быть исключена из числа подозрительных лишь при одном из результатов взвешивания, либо ни при каком из результатов взвешивания на этом шаге, так как иначе её можно было бы исключить из числа подозрительных монет до этого шага. Но это означает, что при каждом результате взвешивания число подозрительных монет сократится не более чем на половину. Поскольку 2⁷ = 128 < 201, необходимо по крайней мере 8 взвешиваний.

[/spoiler]
 
Только вот такие утверждения 
Итак, перед 8-м взвешиванием нам нужно найти самую лёгкую монету. Это легко сделать, сравнив по весу самые лёгкие монеты из двух рядов.
понятно былоб если к примеру - сымые светлые/темные/какие-то ещё, но самые легкие до того должны быть определены.

[замат]

 Если некоторые особо легкие золотые монеты могут быть легче некоторых серебрянных,то придётся тупо все перевесить,разложить все монеты по ранжиру и посчитать которая 101.Иначе никакой уверенности не будет ,что эта и есть та самая 101.Если бы из всех монет именно от 101 первой зависела ваша жизнь, то именно так бы любой и сделал , и никакой гений комбинаторики тут бы не помог.

[☭-Изделие 20Д]

Вдохновившись сим оптимистическим напутствием, приводится попытка доказательства.
Показать скрытый текст

Рассмотрим более общую ситуацию: имеется g золотых монет, упорядоченных по возрастанию массы, s серебряных монет, также упорядоченных по возрастанию массы и мы ищем k-ю по тяжести монету в общем упорядочении всех имеющихся монет. Докажем, что за одно взвешивание мы можем перейти к ситуации с параметрами g', s', k/2, если k чётное, и g', s', [k/2] + 1, если k — нечётное. Для этого сравним [k/2]-е монеты в золотом и серебряном рядах. Без ограничения общности полагаем, что золотая монета тяжелее. Но тогда легче [k/2]-й серебряной монеты может быть лишь ([k/2] – 1) + ([k/2] – 1) ≤ k – 2 монет, значит, серебряные монеты от первой до [k/2]-й можно отбросить. Искомая монета будет теперь иметь номер k/2 при чётном k и [k/2] + 1 — при нечётном, что и требовалось доказать.
Возможен случай, когда в одном из рядов меньше [k/2] монет. Тогда аналогичным рассуждением убеждаемся, что из другого ряда можно выбросить [k/2] монет.
Перед началом взвешиваний имеем: g = 101, s = 100, k = 101. После 1-го взвешивания: k = 51, после 2-го взвешивания: k = 26, после 3-го взвешивания: k = 13, после 4-го взвешивания:
k = 7, после 5-го взвешивания: k = 4, после 6-го взвешивания: k = 2, после 7-го взвешивания: k = 1.
Итак, перед 8-м взвешиванием нам нужно найти самую лёгкую монету. Это легко сделать, сравнив по весу самые лёгкие монеты из двух рядов. Таким образом, 8 взвешиваний достаточно.
Докажем, что меньшим числом взвешиваний обойтись нельзя. Для этого будем смотреть, как меняется в результате взвешивания число подозрительных монет, которые могут оказаться 101-ми по счёту. Вначале подозрительных монет 201, поскольку любая может оказаться 101-й. В результате взвешивания отпадает какое-то множество монет, причём каждая монета может быть исключена из числа подозрительных лишь при одном из результатов взвешивания, либо ни при каком из результатов взвешивания на этом шаге, так как иначе её можно было бы исключить из числа подозрительных монет до этого шага. Но это означает, что при каждом результате взвешивания число подозрительных монет сократится не более чем на половину. Поскольку 2⁷ = 128 < 201, необходимо по крайней мере 8 взвешиваний.

[/quote]УУУ как далеки Вы от народа.
Я так Ваше доеазательство - переводя на обывательский язык и утрируя понял как-то так:
Так как для получения ответа на поставленный вопрос - Какая монета является - 101-ой - первые сотни монет нас не интересуют - поэтому мы просто избавляемся от них(берет и высыпает себе в карман), а вот уже между 101-х всего за одно взвешивание определяем какая является именно - 101-ой
Если я и передернул то совсем чуть-чуть. Можете доказать обратное, но уже не теоретически, а практически!!!
Вот у меня на столе сейчас 101-золотая и 101серебрянная монеты т.е. G1-G101 и S1-S101 в Вашей квалификации - взвешивайте  - Скажите мне какие две самые легкие я должен взять т.е. назовите из идентификационные номера g/sXX ?? Я буду сообщать результаты взвешивания  И за 8 взвешиваний укажите на 101 

[fortpost]

А может так яснее будет?
Показать скрытый текст

Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию, и соединим соседние монеты отрезками, как показано на рисунке (в первой строчке монеты золотые, во второй — серебряные).

Каждый отрезок соединяет две монеты. Придадим ему направление от тяжелой монеты к легкой, так чтобы каждый отрезок превратился в стрелочку. Эти стрелочки обладают тем свойством, что если какая-то направлена вниз, то и все слева от нее тоже направлены вниз, а если какая-то направлена вверх, то и все справа от нее тоже направлены вверх. Каждая монета в этой схеме обладает тем свойством, что число монет слева от нее в верхнем ряду плюс число монет справа от нее в нижнем ряду равно 100. Таким образом, 101-я «средняя» монета М характеризуется тем, что слева от нее все стрелки направлены вниз, а справа — вверх.
Найти это место можно с помощью 8 взвешиваний. Вначале перед нами 200 отрезков, на которых еще не расставлены стрелки. Испытываем какой-нибудь отрезок и ставим на нем стрелку. (Если она направлена вниз, то дальше достаточно проверять отрезки справа от нее, а если вверх — то слева: по другую сторону стрелки расставляются автоматически.) Будем проверять каждый раз средний отрезок из непроверенного куска, а если средних два — то один из них. В результате первого испытания останется не больше 100 непроведенных стрелок, в результате 2-го — не более 50, в результате 3-го — не более 25, в результате 4-го — не более 12, в результате 5-го — не более 6, в результате 6-го — не более 3, в результате 7-го — не более 1. 8-е испытание устанавливает направление последней неизвестной стрелки.
Меньшим числом взвешиваний обойтись нельзя. Действительно, перед всеми взвешиваниями все монеты (201) были кандидатами на 101-е место. В результате одного взвешивания множество монет, которые были кандидатами перед этим взвешиванием, делится на два подмножества: те монеты, которые сохранили возможность занять 101-е место, и остальные. Результаты взвешиваний заранее не известны. Поэтому может случиться, что в результате первого взвешивания останется не менее чем 101 кандидат, в результате второго — 51, в результате 3-го — 26, в результате 4-го — 13, в результате 5-го — 7, в результате 6-го — 4, в результате 7-го — 2. Итак, нельзя гарантировать, что число кандидатов после 7 взвешиваний будет меньше 2, что означает, что 7 взвешиваний недостаточно.

[☭-Изделие 20Д]

А может так яснее будет?
Показать скрытый текст

Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию, и соединим соседние монеты отрезками, как показано на рисунке (в первой строчке монеты золотые, во второй — серебряные).

Каждый отрезок соединяет две монеты. Придадим ему направление от тяжелой монеты к легкой, так чтобы каждый отрезок превратился в стрелочку. Эти стрелочки обладают тем свойством, что если какая-то направлена вниз, то и все слева от нее тоже направлены вниз, а если какая-то направлена вверх, то и все справа от нее тоже направлены вверх. Каждая монета в этой схеме обладает тем свойством, что число монет слева от нее в верхнем ряду плюс число монет справа от нее в нижнем ряду равно 100. Таким образом, 101-я «средняя» монета М характеризуется тем, что слева от нее все стрелки направлены вниз, а справа — вверх.
Найти это место можно с помощью 8 взвешиваний. Вначале перед нами 200 отрезков, на которых еще не расставлены стрелки. Испытываем какой-нибудь отрезок и ставим на нем стрелку. (Если она направлена вниз, то дальше достаточно проверять отрезки справа от нее, а если вверх — то слева: по другую сторону стрелки расставляются автоматически.) Будем проверять каждый раз средний отрезок из непроверенного куска, а если средних два — то один из них. В результате первого испытания останется не больше 100 непроведенных стрелок, в результате 2-го — не более 50, в результате 3-го — не более 25, в результате 4-го — не более 12, в результате 5-го — не более 6, в результате 6-го — не более 3, в результате 7-го — не более 1. 8-е испытание устанавливает направление последней неизвестной стрелки.
Меньшим числом взвешиваний обойтись нельзя. Действительно, перед всеми взвешиваниями все монеты (201) были кандидатами на 101-е место. В результате одного взвешивания множество монет, которые были кандидатами перед этим взвешиванием, делится на два подмножества: те монеты, которые сохранили возможность занять 101-е место, и остальные. Результаты взвешиваний заранее не известны. Поэтому может случиться, что в результате первого взвешивания останется не менее чем 101 кандидат, в результате второго — 51, в результате 3-го — 26, в результате 4-го — 13, в результате 5-го — 7, в результате 6-го — 4, в результате 7-го — 2. Итак, нельзя гарантировать, что число кандидатов после 7 взвешиваний будет меньше 2, что означает, что 7 взвешиваний недостаточно.

Вам бы в депутаты идти рассказывать как хорошо будет жить лет через ннадцать, но пока этого никто не увидит нельзя сейчас сказать - хорошо ли оно будет.

[пестерь]

А может так яснее будет?
Показать скрытый текст

Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию, и соединим соседние монеты отрезками, как показано на рисунке (в первой строчке монеты золотые, во второй — серебряные).

Каждый отрезок соединяет две монеты. Придадим ему направление от тяжелой монеты к легкой, так чтобы каждый отрезок превратился в стрелочку. Эти стрелочки обладают тем свойством, что если какая-то направлена вниз, то и все слева от нее тоже направлены вниз, а если какая-то направлена вверх, то и все справа от нее тоже направлены вверх. Каждая монета в этой схеме обладает тем свойством, что число монет слева от нее в верхнем ряду плюс число монет справа от нее в нижнем ряду равно 100. Таким образом, 101-я «средняя» монета М характеризуется тем, что слева от нее все стрелки направлены вниз, а справа — вверх.
Найти это место можно с помощью 8 взвешиваний. Вначале перед нами 200 отрезков, на которых еще не расставлены стрелки. Испытываем какой-нибудь отрезок и ставим на нем стрелку. (Если она направлена вниз, то дальше достаточно проверять отрезки справа от нее, а если вверх — то слева: по другую сторону стрелки расставляются автоматически.) Будем проверять каждый раз средний отрезок из непроверенного куска, а если средних два — то один из них. В результате первого испытания останется не больше 100 непроведенных стрелок, в результате 2-го — не более 50, в результате 3-го — не более 25, в результате 4-го — не более 12, в результате 5-го — не более 6, в результате 6-го — не более 3, в результате 7-го — не более 1. 8-е испытание устанавливает направление последней неизвестной стрелки.
Меньшим числом взвешиваний обойтись нельзя. Действительно, перед всеми взвешиваниями все монеты (201) были кандидатами на 101-е место. В результате одного взвешивания множество монет, которые были кандидатами перед этим взвешиванием, делится на два подмножества: те монеты, которые сохранили возможность занять 101-е место, и остальные. Результаты взвешиваний заранее не известны. Поэтому может случиться, что в результате первого взвешивания останется не менее чем 101 кандидат, в результате второго — 51, в результате 3-го — 26, в результате 4-го — 13, в результате 5-го — 7, в результате 6-го — 4, в результате 7-го — 2. Итак, нельзя гарантировать, что число кандидатов после 7 взвешиваний будет меньше 2, что означает, что 7 взвешиваний недостаточно.

Вам бы в депутаты идти рассказывать как хорошо будет жить лет через ннадцать, но пока этого никто не увидит нельзя сейчас сказать - хорошо ли оно будет.

1. s50-g50

[☭-Изделие 20Д]

1. s50<g50

[замат]

Что значит- "Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию"?

Я так понял , что именно это и требуется определить,какая из монет какое место занимает по ранжиру в весовой категории и затем найти 101.

А тут оказывается уже монеты рассортированы согласно весу.

 Можно ли  точно описать условие задачи,что имеем и что ищем?

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

Вполне может случится ситуация,когда все золотые монеты будут легче самой легкой серебрянной. Почему собственно нет? Золото намного дороже серебра.

[☭-Изделие 20Д]

Что значит- "Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию"?

Я так понял , что именно это и требуется определить,какая из монет какое место занимает по ранжиру в весовой категории и затем найти 101.

А тут оказывается уже монеты рассортированы согласно весу.

 Можно ли  точно описать условие задачи,что имеем и что ищем?

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

Вполне может случится ситуация,когда все золотые монеты будут легче самой легкой серебрянной. Почему собственно нет? Золото намного дороже серебра.

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