Взвешивание монет

[Валерий]

Имеются чашечные весы без гирь и 90 монет, среди которых 1 отличается по весу в неизвестном направлении. Необходимо найти ее за минимальное число взвешиваний.

Ответ желательно с решением.

[uv]

получилось 9:
45 х 45
22 х 22 1 отложили
11 х 11
5 х 5 1 отложили
2 х 2 1 отложили
1 х1

6 шагов не наши, последнюю монету перемеряем с отложенными, еще +3

[PARK]

Можно мах 6
Рассмотрим самый длинный и неудачный вариант взвешивания
1) Делим на три кучки по 30 монет и взвешиваем две кучки.
если они не равны, то
2) Взвешиваем одну из них с третьей кучкой из 30-и монет. Так мы не только определим кучку в которой фальшивка, но и определим тяжелее она или легче настоящей.
3) Делим на три кучки по 10 монет и взвешиваем две кучки. Сразу можно определить в какой фальшивка. (по второму взвешиванию мы знаем тяжелее фальшивка или легче)
4) Делим на две кучки по 5 монет и взвешиваем.
5) Делим на 2,2,1. Взвешиваем 2 и 2
6) Делим на 1,1. Взвешиваем и согласно взвешиванию 2 определяем фальшивку.

Можно ли определить меньшим кол-вом взвешиваний мне надо подумать?

[PARK]

получилось 9:
45 х 45
22 х 22 1 отложили
11 х 11
5 х 5 1 отложили
2 х 2 1 отложили
1 х1

6 шагов не наши, последнюю монету перемеряем с отложенными, еще +3

И что мы найдём, когда после 1-го взвешивания первая кучка из 45 монет допустим окажется легче второй и что?. В какой фальшивка?

[Валерий]

Можно ли определить меньшим кол-вом взвешиваний мне надо подумать? 

На счет подумать, это правильно. Можно меньше.

[PARK]

Можно ли определить меньшим кол-вом взвешиваний мне надо подумать? 

На счет подумать, это правильно. Можно меньше.

Можно за пять взвешиваний, согласно формуле
m_max=1/2(3ⁿ-3)
где m_max максимальное число монет для n-кол-ва взвешиваний

[егорка]

1. отнимаем 15делим на 3, получаем 3 по 25,взвешиваем 2 раза определяем вес(больше-меньше)
2. отнимаем 7 делим на 3, получаем 3 по 6, опред. 6
3.делим на 3, получаем 2
4.из 2х находим фальш.
Итого=5( в случае когда фальш оказывает в вычтеных частях, ответ не меняется)

[funk]

2. отнимаем 7 делим на 3, получаем 3 по 6, опред. 6

Как в этом действии из 4-х кучек 7+6+6+6 за одно взвешивание ты определил кучку из шести монет с фальшивкой?

[Валерий]

Можно за пять взвешиваний, согласно формуле
m_max=1/2(3ⁿ-3)
где m_max максимальное число монет для n-кол-ва взвешиваний

Было бы неплохо решение описать.

[PARK]

За 5-ть взвешиваний

1) Разделим 90 монет на 10 кучек по 9 монет, присвоим каждой кучке номера от 1 до 10 и взвесим кучки так: на одних весах 1-2-3-4 на других 5-6-7-8
если равно, то фальшивка в кучках 9 или10,
если например 1-2-3-4 тяжелее 5-6-7-8 (другой вариант аналогичен), то

2) Взвесим кучки с номерами 1-2-5 и 3-4-6
а)если они равны, то фальшивая 7 или 8 и она легче (из 1 взвеш.). Взвесим 7 с заведомо настоящей кучкой, напр.1 и найдём фальшивую 7=1, фальш 8, 7меньше1 фальш 7
б)если 1-2-5 тяжелее 3-4-6, то 1 или 2 тяжелее, либо 6 легче - этот вариант возьмём за основной, т.к. вариант (если 1-2-5 легче 3-4-6, то 3 или 4 тяжелее, либо 5 легче) аналогичен по кол-ву взвешиваний.

3) Выбирая основной вариант взвесим кучки 1 и 2
если 1>2, то фальш кучка 1
если 1<2, то фальш кучка 2
если 1=2, то фальш кучка 6
главное теперь мы знаем, какая кучка из 9 монет фальшивая и знаем легче она или тяжелее чем другие.

4) Делим эту кучку из 9 монет на три по 3 монеты и две кучки взвешиваем
сразу определяем в какой из кучек фальшивка, т.к. мы знаем тяжелее она или легче других
например тяжелее, тогда если весы уравновешены, то фальш оставшаяся кучка, если одни весы перевесили, то фальш она и есть

5) Аналогично 4) взвешиваем две монеты из фальш кучки и определяем фальшивую монету.

Может я усложнил объяснение решения, но как-то так.

[Шева]

Делим монеты на 5 кучек по 18шт.
1) min кол-во взвешиваний 2, мах - 3; определяем фальшивая монета весит больше либо меньше остальных.
кучку из 18 монет делим на 8+8+2
2) взвешиваем кучки 8 и 8, определяем кучу с фальшивой монетой ( либо 2шт-тогда еще одно взвешивание либо 8шт)
кучку из 8 монет делим на 3+3+2
3)взвешиваем кучки 3 и 3, определяем кучу с фальшивой монетой ( либо 2шт-тогда еще одно взвешивание либо 3шт)
кучку из 3 монет делим на 1+1+1
4) определяем фальшивую монету.

Итого получилось взвешиваний 5, в худшем случае 6.

[Валерий]

Может я усложнил объяснение решения, но как-то так.

Очень доходчиво объяснил. Проверил, все отлично работает. 

У меня тоже за 5 взвешиваний, но деление на 3 кучи по 30.

[Тиана]

делим монетки на три кучки по 30 монет: 30¹+30²+30³
1е взвешивание: 30 и 30, если
30¹=30², значит фальшивка среди оставшихся 30 монет
2е взвешивание: 20¹ и 20³
если 20¹ = 20³, значит фальшивка среди оставшився  10 монет из 3й кучки 10³
3е взв: 9¹ и 9³, если равно, то фальшивка та монетка, которая осталась в сторонке
если 9¹ > 9³, то фальшивка легкая среди 9 монеток из 3й кучки, и за оставшиеся два взвешивания легко найдем какая именно

2е взвешивание: 20¹ и 20³
если 20¹ > 20³, фальшивка среди 20 монет из 3й кучки и она легче настоящей, за оставшиеся три взвешивания ее найдем

1е взвешивание: 30¹>30²,
2е взвешивание: 23¹+14² и 30³+7¹, если равно, то фальшивка среди 15 монет из 2й кучки и она легче настоящей монетки
если 23¹+14² > 30³+7¹, то фальшивка среди 23 монет 1й кучки и она тяжелее настоящей
если 23¹+14² < 30³+7¹, то фальшивка тяжелая из 7 монет 1й кучки или легкасреди 14 монет 2й кучки
3й взвешивание: 7²и 7², если равно, фальшивая тяжелая и за 2 взвешивания ее легко найти
если 7²> 7², то фальшивая монетка в той кучке, которая легче и за 2 взвешивания ее найдем

[Валерий]

Делим монеты на 5 кучек по 18шт.
1) min кол-во взвешиваний 2, мах - 3; определяем фальшивая монета весит больше либо меньше остальных.
кучку из 18 монет делим на 8+8+2
2) взвешиваем кучки 8 и 8, определяем кучу с фальшивой монетой ( либо 2шт-тогда еще одно взвешивание либо 8шт)
кучку из 8 монет делим на 3+3+2
3)взвешиваем кучки 3 и 3, определяем кучу с фальшивой монетой ( либо 2шт-тогда еще одно взвешивание либо 3шт)
кучку из 3 монет делим на 1+1+1
4) определяем фальшивую монету.

Итого получилось взвешиваний 5, в худшем случае 6.

Будем считать как в худшем случае - 6.

[Валерий]

делим монетки на три кучки по 30 монет: 30¹+30²+30³
1е взвешивание: 30 и 30, если
30¹=30², значит фальшивка среди оставшихся 30 монет
2е взвешивание: 20¹ и 20³
если 20¹ = 20³, значит фальшивка среди оставшився  10 монет из 3й кучки 10³
3е взв: 9¹ и 9³, если равно, то фальшивка та монетка, которая осталась в сторонке
если 9¹ > 9³, то фальшивка легкая среди 9 монеток из 3й кучки, и за оставшиеся два взвешивания легко найдем какая именно

2е взвешивание: 20¹ и 20³
если 20¹ > 20³, фальшивка среди 20 монет из 3й кучки и она легче настоящей, за оставшиеся три взвешивания ее найдем

1е взвешивание: 30¹>30²,
2е взвешивание: 23¹+14² и 30³+7¹, если равно, то фальшивка среди 15 монет из 2й кучки и она легче настоящей монетки
если 23¹+14² > 30³+7¹, то фальшивка среди 23 монет 1й кучки и она тяжелее настоящей
если 23¹+14² < 30³+7¹, то фальшивка тяжелая из 7 монет 1й кучки или легкасреди 14 монет 2й кучки
3й взвешивание: 7²и 7², если равно, фальшивая тяжелая и за 2 взвешивания ее легко найти
если 7²> 7², то фальшивая монетка в той кучке, которая легче и за 2 взвешивания ее найдем

Отлично работает.