Задачки с монетами

Sergei Nickolaev написал(а) к All в Dec 20 00:31:21 по местному времени:

Привет!
Вот наткнулся на пару задачек, которые мне весьма понравились:
1. Имеется 100 золотых монет одинакового веса и 100 позолоченных, тоже
одинакового, но другого веса. Монеты по внешнему виду и на ощупь
неотличимы и перемешаны. Имеются весы с двумя чашками без гирь.
Требуется с помощью ОДНОГО взвешивания предъявить две кучки монет с
одинаковым их количеством, но разного веса. Количество монет в кучках -
неважно, лишь бы было одинаковое.

2. В темной комнате на столе некто выложил 100 одинаковых монет, 88 из
них орлом вверх, 12 - решкой вверх и тщательно перемешал. Монеты сделаны
так, что на ощупь орел от решки неотличим. Требуется, не включая свет (в
темноте) проделать с этими монетами некоторые действия (заменять монеты
на принесенные с собой - не разрешается) так, чтобы на столе было две
кучки монет, в которых решкой вверх будет одинаковое количество монет.
Количества монет в кучках неважны. Количества монет решкой вверх - тоже
неважны, лишь бы они были одинаковы. 0 монет решками вверх - допустимо.

Известное мне решение второй задачки - на удивление изящно и элегантно :-)

--
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Michael Olshevski написал(а) к Sergei Nickolaev в Dec 20 04:23:55 по местному времени:

Пpивет, Sergei!

Thursday 03 December 2020 00:31, Sergei Nickolaev wrote to All:

SN> 1. Имеется 100 золотых монет одинакового веса и 100 позолоченных, тоже
SN> одинакового, но другого веса. Монеты по внешнему виду и на ощупь
SN> неотличимы и перемешаны. Имеются весы с двумя чашками без гирь.
SN> Требуется с помощью ОДНОГО взвешивания предъявить две кучки монет с
SN> одинаковым их количеством, но разного веса. Количество монет в кучках -
SN> неважно, лишь бы было одинаковое.

Хм. А если можно без взвешивания, то просто откладываешь в одну кучку сто монет, и в другую тоже сто. Вероятность того, что в каждой куче окажется ровно 50/50 -- не знаю какая, но нутром чую -- поллитра(зачёркнуто) маленькая.

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109

Sergei Nickolaev написал(а) к Michael Olshevski в Dec 20 12:01:30 по местному времени:

Привет!
03.12.2020 4:16, Michael Olshevski пишет:

> Хм. А если можно без взвешивания, то просто откладываешь в одну кучку сто монет, и в другую тоже сто. Вероятность того, что в каждой куче окажется ровно 50/50 -- не знаю какая, но нутром чую --
> поллитра(зачёркнуто) маленькая.

Задачка не инженерная, а математическая :-) Нужен гарантированный
результат, а не с большой/очень большой вероятностью

Все, что можно сделать с помощью всего одного взвешивания - набрать две
кучи с одинаковым количеством монет (количество - 1-й параметр);
взвесить; если вес оказался разный - предъявляем результат. Решение
должно еще включать действия для случая, когда выбранные две кучи -
одинакового веса. У нас 3 кучи (вариант взвешивать 100 и 100 изначально
не интересный: в случае неудачи никаких дальнейших действий, могущих
привести к успеху просто нет), из них две гарантированно одинакового
веса - можно пытаться скомбинировать их так, чтобы получилось две кучи с
одинаковым количеством и гарантированно разным весом. (Способ
комбинирования - 2-й параметр).
Правильный выбор этих двух параметров задачу решает!



--
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Michael Olshevski написал(а) к Sergei Nickolaev в Dec 20 13:51:31 по местному времени:

Пpивет, Sergei!

Thursday 03 December 2020 12:01, Sergei Nickolaev wrote to Michael Olshevski:

SN> Все, что можно сделать с помощью всего одного взвешивания - набрать две
SN> кучи с одинаковым количеством монет (количество - 1-й параметр);
SN> взвесить; если вес оказался разный - предъявляем результат. Решение
SN> должно еще включать действия для случая, когда выбранные две кучи -
SN> одинакового веса. У нас 3 кучи (вариант взвешивать 100 и 100 изначально
SN> не интересный: в случае неудачи никаких дальнейших действий, могущих
SN> привести к успеху просто нет), из них две гарантированно одинакового
SN> веса - можно пытаться скомбинировать их так, чтобы получилось две кучи с
SN> одинаковым количеством и гарантированно разным весом. (Способ
SN> комбинирования - 2-й параметр).
SN> Правильный выбор этих двух параметров задачу решает!

За 2 взвешивания. С 1 у меня получается с 2 монетами, 4, 6, 10, 14, 18 ... 198, 202, но не с 200.

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109

Sergei Nickolaev написал(а) к Michael Olshevski в Dec 20 19:43:21 по местному времени:

Привет!
03.12.2020 13:51, Michael Olshevski пишет:

> За 2 взвешивания. С 1 у меня получается с 2 монетами, 4, 6, 10, 14, 18 ... 198, 202, но не с 200.

Из приведенных здесь количеств (не знаю, что в многоточии прячется)
только для 4 требуется взвешивание. Для остальных две кучи с одинаковым
количеством, но заведомо разного веса предъявляются без взвешиваний
вовсе - делим кучу пополам и все готово: нечетное количество "золотых"
монет никак не может разложиться поровну :-)
Для 4 делаем так: кладем на весы 2 "кучки" по 1-й монете. Если вес
разный - предъявляем их, если одинаковый - предъявляем в качестве одной
"кучки" любую из монет, которые взвешивали; в качестве другой - любую из
монет, которые не взвешивали.

>
> Мои наилучшие пожелания,
> Michael.
>


--
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Michael Olshevski написал(а) к Sergei Nickolaev в Dec 20 22:07:18 по местному времени:

Пpивет, Sergei!

Thursday 03 December 2020 19:43, Sergei Nickolaev wrote to Michael Olshevski:
>> За 2 взвешивания. С 1 у меня получается с 2 монетами, 4, 6, 10, 14, 18
>> ... 198, 202, но не с 200.
SN> Из приведенных здесь количеств (не знаю, что в многоточии прячется)
SN> только для 4 требуется взвешивание. Для остальных две кучи с одинаковым
SN> количеством, но заведомо разного веса предъявляются без взвешиваний
SN> вовсе - делим кучу пополам и все готово: нечетное количество "золотых"
SN> монет никак не может разложиться поровну :-)

Да, загнался.

SN> Для 4 делаем так: кладем на весы 2 "кучки" по 1-й монете. Если вес
SN> разный - предъявляем их, если одинаковый - предъявляем в качестве одной
SN> "кучки" любую из монет, которые взвешивали; в качестве другой - любую из
SN> монет, которые не взвешивали.

Угу. Только я и здесь загнался: вешал по одной и в случае равенства предъявлял как кучку 1 обе монеты с весов, кучку 2 -- любую монету с весов плюс любую из оставшихся.

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109

Sergei Nickolaev написал(а) к Michael Olshevski в Dec 20 23:23:04 по местному времени:

Привет!
03.12.2020 22:07, Michael Olshevski пишет:

> Угу. Только я и здесь загнался: вешал по одной и в случае равенства предъявлял как кучку 1 обе монеты с весов, кучку 2 -- любую монету с весов плюс любую из оставшихся.

Похоже, что я где-то не совсем четко сформулировал :-( В предъявляемых
кучах допустимо любое количество монет, лишь бы оно было равное, хоть по
одной монете (по 0 не годится, любые кучки из 0 монет весят одинаково,
неважно 0 там золотых монет или 0 позолоченных :-) ). Но, при этом,
кучки не должны пересекаться, то есть ни одна монета не должна быть
включена сразу в обе предъявляемые кучки.

Еще подсказка: если для суммарного числа монет вида 4n+2 (удвоенные
нечетные) ключевым моментом является четность/нечетность
(делимость/неделимость на 2), то для 200 монет сходную роль играет
делимость/неделимость на 3. Разумеется речь не идет о воспроизведении
метода по аналогии "влоб".


--
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Michael Olshevski написал(а) к Sergei Nickolaev в Dec 20 00:44:31 по местному времени:

Пpивет, Sergei!

Thursday 03 December 2020 23:23, Sergei Nickolaev wrote to Michael Olshevski:

SN> Еще подсказка: если для суммарного числа монет вида 4n+2 (удвоенные
SN> нечетные) ключевым моментом является четность/нечетность
SN> (делимость/неделимость на 2), то для 200 монет сходную роль играет
SN> делимость/неделимость на 3. Разумеется речь не идет о воспроизведении
SN> метода по аналогии "влоб".

Блин. Про 3 кучи я знал. Делим на 3 кучи по 66 плюс 2 монеты. Взвешиваем 2 кучи, если одинаковые, то взвешиваем одну из них с третьей, если опять одинаковые -- 2 монеты разного веса. Но 2 взвеса...

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109

Sergei Nickolaev написал(а) к Michael Olshevski в Dec 20 00:53:50 по местному времени:

Привет!
04.12.2020 0:16, Michael Olshevski пишет:

> Блин. Про 3 кучи я знал. Делим на 3 кучи по 66 плюс 2 монеты. Взвешиваем 2 кучи, если одинаковые, то взвешиваем одну из них с третьей, если опять одинаковые -- 2 монеты разного веса. Но 2 взвеса...

Это уже очень горячо: решение совсем рядом!
Берем 2 кучи по 67 монет. Если вес разный - ура. Если одинаковый то
предъявляем две вот такие кучи: 1 - с чашки весов; 2 - 66 монет, которые
не взвешивали, плюс одна ЛЮБАЯ монета из второй чашки весов. Осталось
показать, что предъявляемые кучи непременно разного веса. Хоть чуть-чуть
интриги оставлю :-)


--
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Michael Olshevski написал(а) к Sergei Nickolaev в Dec 20 02:39:32 по местному времени:

Пpивет, Sergei!

Friday 04 December 2020 00:53, Sergei Nickolaev wrote to Michael Olshevski:

SN> Берем 2 кучи по 67 монет. Если вес разный - ура. Если одинаковый то
SN> предъявляем две вот такие кучи: 1 - с чашки весов; 2 - 66 монет, которые
SN> не взвешивали, плюс одна ЛЮБАЯ монета из второй чашки весов. Осталось
SN> показать, что предъявляемые кучи непременно разного веса.

Понятно. В точке перелома разница между монетами в куче-66 будет 2. 34/33+34/33 дают 3кучу 32/34, какую монету ни клади -- не выравняешь.

SN> Хоть чуть-чуть интриги оставлю :-)

Не, меня этим не заинтригуешь нисколько. Собственно, меня вообще, наверное, ничем уже не заинтригуешь -- если за 60 лет не получилось. Я, грешным делом, из твоих слов понял, что готового решения для первой задачи нет.
=== Начало Windows Clipboard ===
Известное мне решение второй задачки - на удивление изящно и элегантно :-)
==== Конец Windows Clipboard ====
А ты его, оказывается, знал... Увы, это не моё.

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109