Вот задачка собственного изготовления
Есть 10 мешков с монетами, в одном, как водится, монеты фальшивые и весят 9 грамм вместо обычных 10-ти. Также есть весы с ограниченным верхним пределом взвешивания (т.е. весы могут определить вес в граммах от 0 до N). Найти минимальный предел, при котором можно определить фальшивую монету за два взвешивания.
There are 10 types of people in the world, those who don't understand binaries, those who do, and those who understand not only binaries.
Здравствуйте, Slamin, Вы писали:
S>Вот задачка собственного изготовления S>Есть 10 мешков с монетами, в одном, как водится, монеты фальшивые и весят 9 грамм вместо обычных 10-ти. Также есть весы с ограниченным верхним пределом взвешивания (т.е. весы могут определить вес в граммах от 0 до N). Найти минимальный предел, при котором можно определить фальшивую монету за два взвешивания.
Блесну:
Разбиваем на 2 кучки по 5 мешков.
С первого ложим одну монету, со второго 2, и т.д. По недостаче определяем номер мешка.
При наихудшем раскладе 9 + 20 + 30 + 40 + 50 = 149.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
fAX>Блесну: fAX>Разбиваем на 2 кучки по 5 мешков. fAX>С первого ложим одну монету, со второго 2, и т.д. По недостаче определяем номер мешка. fAX>При наихудшем раскладе 9 + 20 + 30 + 40 + 50 = 149.
1. Не правильно
2. В вашем варианте если оба раза весы показали 149 — не понятно в каком из двух мешков, из которых бралось по одной монете, лежат фальшивки.
There are 10 types of people in the world, those who don't understand binaries, those who do, and those who understand not only binaries.
Здравствуйте, fAX, Вы писали:
fAX>Здравствуйте, Slamin, Вы писали:
S>>Вот задачка собственного изготовления S>>Есть 10 мешков с монетами, в одном, как водится, монеты фальшивые и весят 9 грамм вместо обычных 10-ти. Также есть весы с ограниченным верхним пределом взвешивания (т.е. весы могут определить вес в граммах от 0 до N). Найти минимальный предел, при котором можно определить фальшивую монету за два взвешивания.
fAX>Блесну: fAX>Разбиваем на 2 кучки по 5 мешков. fAX>С первого ложим одну монету, со второго 2, и т.д. По недостаче определяем номер мешка. fAX>При наихудшем раскладе 9 + 20 + 30 + 40 + 50 = 149.
Так как не сказано, что весы с одной чашечкой, то, пока не поменяли условие, поспешу улучшить результат.
Разбиваем мешки на три кучки — по 3, 3 и 4 мешка.
При первым взвешивании — определяем кучку с фальшивыми монетами — сравниваем 3 монеты с первой и 3 со второй кучки.
Вторым взвешиванием определяем фальшивый мешок.
В худшем случае потребуется
9 + 20 + 30 + 40 = 99 грамм !!!
(не 100!, так как кучка с фальшивыми монетами нам будет известна)
Привет, mrhru!
S>>>Вот задачка собственного изготовления S>>>Есть 10 мешков с монетами, в одном, как водится, монеты фальшивые и весят 9 грамм вместо обычных 10-ти. Также есть весы с ограниченным верхним пределом взвешивания (т.е. весы могут определить вес в граммах от 0 до N). Найти минимальный предел, при котором можно определить фальшивую монету за два взвешивания.
M>Так как не сказано, что весы с одной чашечкой, то, пока не поменяли условие, поспешу улучшить результат.
Спешить никогда не надо!
M>Разбиваем мешки на три кучки — по 3, 3 и 4 мешка. M>При первым взвешивании — определяем кучку с фальшивыми монетами — сравниваем 3 монеты с первой и 3 со второй кучки. M>Вторым взвешиванием определяем фальшивый мешок. M>В худшем случае потребуется M> 9 + 20 + 30 + 40 = 99 грамм !!! M>(не 100!, так как кучка с фальшивыми монетами нам будет известна)
Первым взвешиванием действительно выгодно сразу оставить 3 или 4 мешка, среди которых есть мешок с фальшивыми монетами.
В худшем случае останется 4 мешка.
В этом случае, взвешиваем 0, 1, 2 и 3 монеты из этих мешков. Получим максимум 60 грамм!
Если вес 60 грамм — фальшивые монеты в первом мешке, если 59 — во втором, 58 — в третьем, 57 — в четвертом!
...
M>>Так как не сказано, что весы с одной чашечкой, то, пока не поменяли условие, поспешу улучшить результат.
A>Спешить никогда не надо!
Надо-надо!
...
A>Первым взвешиванием действительно выгодно сразу оставить 3 или 4 мешка, среди которых есть мешок с фальшивыми монетами. A>В худшем случае останется 4 мешка. A>В этом случае, взвешиваем 0, 1, 2 и 3 монеты из этих мешков. Получим максимум 60 грамм! A>Если вес 60 грамм — фальшивые монеты в первом мешке, если 59 — во втором, 58 — в третьем, 57 — в четвертом!
Улучшаем еще вдвое:
В худшем случае, с каждой стороны весов кладем по 1+2 монетки и на ту чашку, которая легче добавляем 1 или 2 грамма гирек.
Опровержения в виде: "тогда это будет 3 взвешивания, а не два" — не принимаются.
Раз уж мы согласились с тем, что весы двухчашечные, то даже простое измерение веса с помощью гирек должно распадаться на несколько измерений — пока весы не уравновесятся.
Итого: 10 + 20 = 30 грамм!
Кто меньше?
Евгений
Re: шение: если по-честному, то 80 гр, иначе 11 гр или даже
Здравствуйте, Slamin, Вы писали:
S>Есть 10 мешков с монетами, в одном, как водится, монеты фальшивые и весят 9 грамм вместо обычных 10-ти. Также есть весы с ограниченным верхним пределом взвешивания (т.е. весы могут определить вес в граммах от 0 до N). Найти минимальный предел, при котором можно определить фальшивую монету за два взвешивания.
Договоримся сразу, что никаких гирь подкладывать во время взвешивания нельзя (их у нас нет)! Такого — — нам не надо!
1. Весы с одной чашей, никаких приспособлений использовать нельзя — 80 грамм!
Кладем на весы по одной монетке из 4-х мешков и по две из двух — максимум 80 грамм.
Итак, максимум 4 мешка с подозрительными монетами. Кладем 0, 1, 2 и 3 монетки из них (максимум 60 грамм) и определяем фальшивые.
2. Весы с одной чашей, можно использовать приспособления — 11 грамм!
Кладем на весы 4 монеты из разных мешков, "подвешиваем под чашу" каким-либо способом 3 монеты из других мешков. Показания весов — 9, 10 или 11 грамм определяют максимум 4 мешка, где могут быть фальшивые монеты. Из 4-х мешков кладем на весы 1 монету из одного мещка, 2 монеты из другого, подвешиваем снизу 1 монету из третьего мешка и 1 монету из тех, что точно не фальшивые! Показания весов: 8, 9, 10 или 11 грамм определяют одну из 4-х кучек, где фальшивая монета!
3. Весы с двумя чашами показывают перевес одной или другой чаши — от -1 до 2 грамм!
Кладем на одну чашу весов 4 монеты из разных мешков и на другую тоже — от -1 до 1 грамма! Осталось максимум 4 мешка. Кладем на первую чашу 1 монету из 4-х оставшихся мешков и 2 монеты из тех, что точно не фальшивые. На другую кладем 1 монету из оставшихся уже 3-х мешков и 2 монеты из оставшихся 2-х. Показания весов -1, 0, 1 или 2 грамма определяют тот мешок, где фальшивая монета!
Здесь могла бы быть Ваша реклама!
Re[2]: шение: если по-честному, то 80 гр, иначе 11 гр или да
С конца:
A>3. Весы с двумя чашами показывают перевес одной или другой чаши — от -1 до 2 грамм!
A>Кладем на одну чашу весов 4 монеты из разных мешков и на другую тоже — от -1 до 1 грамма! Осталось максимум 4 мешка. Кладем на первую чашу 1 монету из 4-х оставшихся мешков и 2 монеты из тех, что точно не фальшивые. На другую кладем 1 монету из оставшихся уже 3-х мешков и 2 монеты из оставшихся 2-х. Показания весов -1, 0, 1 или 2 грамма определяют тот мешок, где фальшивая монета!
Этот вариант, с учетом ограничения "никаких гирь подкладывать во время взвешивания нельзя" — не подходит! Иначе как отличить перевес в 1 или 2 грамма?
А если и можем отличить, то мой вариант — лучше — потому как на весы надо ложить не 4 а 3 монеты! И таким образом, максимальный вес на чашках — не 40 а 30 грамм.
A>1. Весы с одной чашей, никаких приспособлений использовать нельзя — 80 грамм!
A>Кладем на весы по одной монетке из 4-х мешков и по две из двух — максимум 80 грамм. A>Итак, максимум 4 мешка с подозрительными монетами. Кладем 0, 1, 2 и 3 монетки из них (максимум 60 грамм) и определяем фальшивые.
A>2. Весы с одной чашей, можно использовать приспособления — 11 грамм!
A>Кладем на весы 4 монеты из разных мешков, "подвешиваем под чашу" каким-либо способом 3 монеты из других мешков. Показания весов — 9, 10 или 11 грамм определяют максимум 4 мешка, где могут быть фальшивые монеты. Из 4-х мешков кладем на весы 1 монету из одного мещка, 2 монеты из другого, подвешиваем снизу 1 монету из третьего мешка и 1 монету из тех, что точно не фальшивые! Показания весов: 8, 9, 10 или 11 грамм определяют одну из 4-х кучек, где фальшивая монета!
Жульничество, ну да ладно.
Кладем на весы 3 монеты из разных мешков, "подвешиваем под чашу" каким-либо способом 3 монеты из других мешков.
Показания весов — -1, 0 или 1 грамм определяют максимум 4 мешка, где могут быть фальшивые монеты.
Остальное почти совпадает:
Из 4-х мешков — один откладываем в сторону(!), кладем на весы 1 монету из одного мещка, 2 монеты из другого, подвешиваем снизу 3 монеты из тех, что точно не фальшивые[/i]! Показания весов: -2, -1, 0 определяют одну из 3-х кучек, где фальшивая монета или это отложенный мешок!
Преимущества: перевес максимум в 2 грамма и на чашках не более 3 монет.
В общем, надо определиться — что есть такое весы и что мы можем с ними вытворять.
Евгений
Re[2]: шение: если по-честному, то 80 гр, иначе 11 гр или да
Здравствуйте, Apapa, Вы писали:
A>Договоримся сразу, что никаких гирь подкладывать во время взвешивания нельзя (их у нас нет)! Такого — — нам не надо!
A>1. Весы с одной чашей, никаких приспособлений использовать нельзя — 80 грамм!
A>Кладем на весы по одной монетке из 4-х мешков и по две из двух — максимум 80 грамм. A>Итак, максимум 4 мешка с подозрительными монетами. Кладем 0, 1, 2 и 3 монетки из них (максимум 60 грамм) и определяем фальшивые.
Именно это я и имел ввиду.
There are 10 types of people in the world, those who don't understand binaries, those who do, and those who understand not only binaries.
Apapa.gif)
— нам не надо!
