Задачи, головоломки, загадки

Adam Sniper

Администратор
Команда форума
Жёсткая задачка!

Из той серии что "перемножте в уме два н-значных числа", т.е. как решать примерно понятно, но удержание в уме всех этих ветвящихся условий вызывает боль и страдания. Типа пока одну ветку решаешь, вторую уже забываешь:)

А вот, к примеру, "недетский пазл" от kapkap-а выглядит более весёлым что-ли, типа смекнул принцип, а там уже всё понятно. Видимо другие структуры мозга задействуются. Ну, по крайней мере, у меня так это работает.
Потому айкью - это больше смекалка, чем «индекс интеллекта», как его ошибочно называют
 
Такая задача:

Дано 5 золотых и 5 серебряных монет. Веса золотой и сереллбряной монет никак не связаны.
Известно что 1 золотая монета фальшивая, и она легче на 1г., также 1 серебряная монета фальшивая, и она тяжелее на 1г.

Найти обе фальшивые монеты за 3 взвешивания (на чашечных весах).
IMG_20190501_113115_127.jpg
(на рисунке в варианте №5 знак равно не дорисован). Далее- по рисунку.

делаем 3 кучки из 10 монет, произвольным образом: кучка А = 2 зол+2 сер, такая же кучка Б и кучка В= 1 зол+1 сер
Взвешивание 1: на одну чашку кучку А, на другую - Б. Резалт: либо чашки равны, либо нет.

Сначала рассмотрим что чашки равны. Это варианты №1 и №5.
Взвешивание 2. берем любую кучку. на одну чашку серебряную монету , на другую серебряную монету из этой же кучки. Резалта также 2: либо чашки равны,либо нет.
* если чашки неравны, то это 100% вариант №5, в более тяжелой - фальшивая серебряная монета.
Тогда взвешивание 3 - оставшиеся золотые монеты из этой же кучки. В более легкой - фальшивая золотая.
* если чашки равны, то это означает лишь, что все 4 монеты этой кучки - нефальшивые; но различить : это вариант №1 или кучка А из №5 невозможно: фальшивые монеты находятся либо одновременно в кучке Б, либо одновременнов кучке В. Тут на самом деле труба - почему?
Взвешивание 3 - на одну чашку серебряную монету 3 из этой кучки Б, на другую - 4 из этой же кучки.
Если чашки равны- все тип-топ, это вариант №1, и фальшивые обе монеты в кучке В.
А вот если чашки неравны, то за это взвешивание определяем что в тяжелой -фальшивая серебряная монета,а вот определить какая из двух золотых монет в этой кучке Б фальшивая - не знаю как без 4 взвешивания!

Возвращаемся к взвешиванию1: чашки неравны. Варианты №2,3,4.
Взвешивание 2. берем тяжелую кучку; на одну чашку серебряную монету, на другую серебряную монету. Резалта также 2: либо чашки равны,либо нет.
* если чашки равны, то это 100% вариант №3: фальшивая серебряная монета в кучке В.
Тогда взвешивание 3 - на одну чашку золотую монету из легкой кучки, на другую - другую из той же легкой кучки. Которая легче - та фальшивая.
* если чашки неравны, то в тяжелой - фальшивая серебряная монета. Также это означает варианты либо №2, либо №4.
Поэтому взвешивание 3 - на одну чашку золотую монету из легкой кучки, на другую - другую из той же легкой кучки.
Если чашки равны, фальшивая золотая в кучке В; если неравны, то фальшивая в легкой чашке.
 
Жёсткая задачка!

Из той серии что "перемножте в уме два н-значных числа", т.е. как решать примерно понятно, но удержание в уме всех этих ветвящихся условий вызывает боль и страдания. Типа пока одну ветку решаешь, вторую уже забываешь:)
есть еще такая зубодробительная загадка Эйнштейна..
во там да, в втором вопросе с зеброй реальности разьезжаются прям на шпагат..)
 
Посмотреть вложение 97671
(на рисунке в варианте №5 знак равно не дорисован). Далее- по рисунку.

делаем 3 кучки из 10 монет, произвольным образом: кучка А = 2 зол+2 сер, такая же кучка Б и кучка В= 1 зол+1 сер
Взвешивание 1: на одну чашку кучку А, на другую - Б. Резалт: либо чашки равны, либо нет.

Сначала рассмотрим что чашки равны. Это варианты №1 и №5.
Взвешивание 2. берем любую кучку. на одну чашку серебряную монету , на другую серебряную монету из этой же кучки. Резалта также 2: либо чашки равны,либо нет.
* если чашки неравны, то это 100% вариант №5, в более тяжелой - фальшивая серебряная монета.
Тогда взвешивание 3 - оставшиеся золотые монеты из этой же кучки. В более легкой - фальшивая золотая.
* если чашки равны, то это означает лишь, что все 4 монеты этой кучки - нефальшивые; но различить : это вариант №1 или кучка А из №5 невозможно: фальшивые монеты находятся либо одновременно в кучке Б, либо одновременнов кучке В. Тут на самом деле труба - почему?
Взвешивание 3 - на одну чашку серебряную монету 3 из этой кучки Б, на другую - 4 из этой же кучки.
Если чашки равны- все тип-топ, это вариант №1, и фальшивые обе монеты в кучке В.
А вот если чашки неравны, то за это взвешивание определяем что в тяжелой -фальшивая серебряная монета,а вот определить какая из двух золотых монет в этой кучке Б фальшивая - не знаю как без 4 взвешивания!

Возвращаемся к взвешиванию1: чашки неравны. Варианты №2,3,4.
Взвешивание 2. берем тяжелую кучку; на одну чашку серебряную монету, на другую серебряную монету. Резалта также 2: либо чашки равны,либо нет.
* если чашки равны, то это 100% вариант №3: фальшивая серебряная монета в кучке В.
Тогда взвешивание 3 - на одну чашку золотую монету из легкой кучки, на другую - другую из той же легкой кучки. Которая легче - та фальшивая.
* если чашки неравны, то в тяжелой - фальшивая серебряная монета. Также это означает варианты либо №2, либо №4.
Поэтому взвешивание 3 - на одну чашку золотую монету из легкой кучки, на другую - другую из той же легкой кучки.
Если чашки равны, фальшивая золотая в кучке В; если неравны, то фальшивая в легкой чашке.
Думаете в верном направлении, но надо аккуратнее.
В случае №3 тоже не всё ясно. Непонятно как за 1 взвешивание можно одновременно найти и золотую и серебряную монеты (т.е. не просто кучку, а саму монету).

Могу дать намёк как такие задачи вообще решать из соображений комбинаторики.
Каждое взвешивание потенциально может иметь 3 результата: больше, меньше, равно. Значит возможные варианты того где фальшивые монеты делятся на 3 группы. После 3 взвешиваний мы должны всегда приходить к 1 варианту. Значит перед последним взвешиванием их должно быть не больше 3, за 2 взвешивания до конца их должно быть не больше 9, и изначально - не больше 27.

У нас 1 из 5 фальшивая для золотых и серебряных. Таким образом у нас изначально 5^2 = 25 вариантов.
Т.е. вроде бы решается. Но запас небольшой.

Предлагаю проверить Ваши варианты того что как взвешивается, и убедиться что после любого взвешивания при любом результате остаётся не слишком много вариантов.
 
Думаете в верном направлении, но надо аккуратнее.
В случае №3 тоже не всё ясно. Непонятно как за 1 взвешивание можно одновременно найти и золотую и серебряную монеты (т.е. не просто кучку, а саму монету).

Могу дать намёк как такие задачи вообще решать из соображений комбинаторики.
Каждое взвешивание потенциально может иметь 3 результата: больше, меньше, равно. Значит возможные варианты того где фальшивые монеты делятся на 3 группы. После 3 взвешиваний мы должны всегда приходить к 1 варианту. Значит перед последним взвешиванием их должно быть не больше 3, за 2 взвешивания до конца их должно быть не больше 9, и изначально - не больше 27.

У нас 1 из 5 фальшивая для золотых и серебряных. Таким образом у нас изначально 5^2 = 25 вариантов.
Т.е. вроде бы решается. Но запас небольшой.

Предлагаю проверить Ваши варианты того что как взвешивается, и убедиться что после любого взвешивания при любом результате остаётся не слишком много вариантов.
угу! доказательство, что задача - решаема, поняла)
С вариантом №3. Он выщепляется именно потому, что когда мы взвешиваем более тяжелую кучку, то оно может быть только при 2 случаях: в ней есть тяжелая фальшивая серебряная монета (варианты №2и №4) - либо в легкой есть фальшивая золотая (№3). Взвешивание 2 как раз и дает инфу об этом. То есть если обе серебряные монеты в тяжелой кучке во 2 взвешивании равны, то однозначно сер фальшивая в кучке В, и нужно 3 взвешивание для определения фальшивой золотой.

Но, решение задачи в целом неполное, согласна.
 
угу! доказательство, что задача - решаема, поняла)
С вариантом №3. Он выщепляется именно потому, что когда мы взвешиваем более тяжелую кучку, то оно может быть только при 2 случаях: в ней есть тяжелая фальшивая серебряная монета (варианты №2и №4) - либо в легкой есть фальшивая золотая (№3). Взвешивание 2 как раз и дает инфу об этом. То есть если обе серебряные монеты в тяжелой кучке во 2 взвешивании равны, то однозначно сер фальшивая в кучке В, и нужно 3 взвешивание для определения фальшивой золотой.

Но, решение задачи в целом неполное, согласна.
Дело не только в том что задача (вроде бы) решаема, таким образом легко проверить что в каждом из вариантов следующее взвешивание правильное, т.е. при любом раскладе можно прийти к 1 варианту.

Например, я могу показать что в случае если в первом взвешивании чашки равны, то Ваше второе взвешивание (по одной серебряной монете на каждой чашке) точно неверно. Т.е. возможен вариант где 3 взвешиваний хватит
 
Дело не только в том что задача (вроде бы) решаема, таким образом легко проверить что в каждом из вариантов следующее взвешивание правильное, т.е. при любом раскладе можно прийти к 1 варианту.

Например, я могу показать что в случае если в первом взвешивании чашки равны, то Ваше второе взвешивание (по одной серебряной монете на каждой чашке) точно неверно. Т.е. возможен вариант где 3 взвешиваний хватит
Я действительно до этого все усложнила.

1 взвешивание. Начинаем с серебряных монет (можно и с золотых, не суть). Кладем на чашки по 2 сер монеты в каждую.
* если чашки равны фальшивая сер - отложенная 5-я.
Тогда 2 взвешивание- также по 2 золотых в чашку.
Если они равны, то фальшивая зол - отложенная 5-я. Управляемся за 2 взвешивания.
Если они неравны, то 3 взвешивание: обе зол монеты из легкой чашки распределяем по 1 в чашку и взвешиваем. Фальшивая- где легкая.

* если чашки неравны, то фальшивая сер, очевидно, одна из 2 в тяжелой чашке; остальные 3 норм.
2 взвешивание. Кладем эти сомнительные 2 сер монеты по 1 в чашку и добавляем к ним по 1 любой золотой.
Если чашки равны, то ясно, что в одной из них - фальшивая сер, в другой - фальш зол.
Убираем золотые монеты, запомнив, в какой чашке какая была и делаем 3 взвешивание. В той, которая тяжелее - фальш сер. Фальш зол - из противоположной чашки.
Если чашки неравны, то фальш сер в той, которая тяжелее; обе взвешенные золотые - норм, их убираем.
Делаем 3 взвешивание: сравниваем любые 2 из оставшихся 3 зол. Если чашки равны - фальш, которая осталась последней. Если неравны - фальш, которая в легкой чашке.

Красивая задача.
 
Я действительно до этого все усложнила.

1 взвешивание. Начинаем с серебряных монет (можно и с золотых, не суть). Кладем на чашки по 2 сер монеты в каждую.
* если чашки равны фальшивая сер - отложенная 5-я.
Тогда 2 взвешивание- также по 2 золотых в чашку.
Если они равны, то фальшивая зол - отложенная 5-я. Управляемся за 2 взвешивания.
Если они неравны, то 3 взвешивание: обе зол монеты из легкой чашки распределяем по 1 в чашку и взвешиваем. Фальшивая- где легкая.

* если чашки неравны, то фальшивая сер, очевидно, одна из 2 в тяжелой чашке; остальные 3 норм.
2 взвешивание. Кладем эти сомнительные 2 сер монеты по 1 в чашку и добавляем к ним по 1 любой золотой.
Если чашки равны, то ясно, что в одной из них - фальшивая сер, в другой - фальш зол.
Убираем золотые монеты, запомнив, в какой чашке какая была и делаем 3 взвешивание. В той, которая тяжелее - фальш сер. Фальш зол - из противоположной чашки.
Если чашки неравны, то фальш сер в той, которая тяжелее; обе взвешенные золотые - норм, их убираем.
Делаем 3 взвешивание: сравниваем любые 2 из оставшихся 3 зол. Если чашки равны - фальш, которая осталась последней. Если неравны - фальш, которая в легкой чашке.

Красивая задача.
Почти :D:D:D

Если чашки неравны, то фальш сер в той, которая тяжелее; обе взвешенные золотые - норм, их убираем.
Необязательно! Может быть что золотая на лёгкой чашке тоже фальшивая
 
Т.е. возможен вариант где 3 взвешиваний хватит
У меня все время получается, что в одной из вероятностей все равно возникает необходимость в 4 взвешивании...
Единственный способ, как это обойти, я вижу в том, чтобы загнать в одно взвешивание по сути 2: то есть сначала положить на чашки по 2 монеты на каждую, а потом убрать по монете и тоже посмотреть на результат.. И счесть этот мухлёж типа за 1 взвешивание..
Иных способов я просто не вижу.
 
Так, так, так... Ну давайте посмотрим.

1) G1 G2,S1 S2 <-> G3 G4, S3 S4

а) Если какая-то чашка перевесит, то считай нам повезло. Допустим, без ограничения общности, перевесила правая, тогда остались варианты: 1) G1 S3, 2) G1 S4, 3) G2 S3, 4) G2 S4, 5) G1 S5, 6) G2 S5 7) G5 S3, :cool: G5 S4, т.е. G3, G4, S1, S2 - подлинные.
На второе взвешивание кладем G1 <-> G2, на третье S3 <-> S4 и там все очевидно.

б) Если на первом взвешивании оказалось равенство, то мы остались с вариантами:

1) G1 S1, 2) G1 S2, 3) G2 S1, 4) G2 S2, 5) G3 S3, 6) G3 S4, 7) G4 S3, :cool: G4 S4. Ну и само собой не забываем 9) G5 S5.

Теперь критическое второе взвешивание:
G1 G3 S1 <-> G2 G4 S2 (!!)
a) "=": осталось 1) G1 S1, 2) G2 S2, 3) G5 S5 - последнее взвешивание тривиально.
б) "<": осталось 1) G1 S2, 2) G3 S3, 3) G3 S4 - последнее взвешивание S3 <-> S4
в) ">": осталось 1) G2 S1, 2) G4 S3, 3) G4 S4 - последнее взвешивание тоже S3 <-> S4

Вуаля. :)
 
У меня все время получается, что в одной из вероятностей все равно возникает необходимость в 4 взвешивании...
Единственный способ, как это обойти, я вижу в том, чтобы загнать в одно взвешивание по сути 2: то есть сначала положить на чашки по 2 монеты на каждую, а потом убрать по монете и тоже посмотреть на результат.. И счесть этот мухлёж типа за 1 взвешивание..
Иных способов я просто не вижу.
Попробуйте проанализировать с точки зрения кол-ва вариантов. Я, например, только так смог это решить.

Например, возьмём Ваш подход:

1-е взвешивание: по 2 зол и 2 сер с каждой стороны. Давайте посчитаем кол-во вариантов:

(а) если получилось равно, то мы знаем что фальшивые монеты в одной кучке. Если они в кучке А то это 4 варианта (2 варианта для зол умножить на 2 варианта для сер), Б также 4 варианта, В - 1 вариант.
Итого: 9 вариантов.

(б) если одна из чашек тяжелее, то в каждом случае должно быть (25 - 9)/2 = 8 вариантов. (эти варианты симметричны, всего изначально их было 5^2 = 25).

Это значит что Ваше первое взвешивание вполне может быть правильным, в любом из случаев остаётся не больше 9 вариантов.

Походу проблема со вторым взвешиванием. Если у Вас получается что иногда хватает 2 взвешиваний, то это УЖЕ признак что так задача не решится. Это значит что по крайней мере для одного из случаев остаётся лишь 1 вариант, и если в других не больше 3, то в сумме у нас всего лишь 7 вариантов.
 
Попробуйте проанализировать с точки зрения кол-ва вариантов. Я, например, только так смог это решить.

Например, возьмём Ваш подход:

1-е взвешивание: по 2 зол и 2 сер с каждой стороны. Давайте посчитаем кол-во вариантов:

(а) если получилось равно, то мы знаем что фальшивые монеты в одной кучке. Если они в кучке А то это 4 варианта (2 варианта для зол умножить на 2 варианта для сер), Б также 4 варианта, В - 1 вариант.
Итого: 9 вариантов.

(б) если одна из чашек тяжелее, то в каждом случае должно быть (25 - 9)/2 = 8 вариантов. (эти варианты симметричны, всего изначально их было 5^2 = 25).

Это значит что Ваше первое взвешивание вполне может быть правильным, в любом из случаев остаётся не больше 9 вариантов.

Походу проблема со вторым взвешиванием. Если у Вас получается что иногда хватает 2 взвешиваний, то это УЖЕ признак что так задача не решится. Это значит что по крайней мере для одного из случаев остаётся лишь 1 вариант, и если в других не больше 3, то в сумме у нас всего лишь 7 вариантов.
я помучаю задачку еще, но пока не улавливаю, как можно применить подсчет кол-ва вариантов к нахождению решения.
Если не получится по-иному, освежу начала комбинаторики)
Так, так, так... Ну давайте посмотрим.

1) G1 G2,S1 S2 <-> G3 G4, S3 S4

а) Если какая-то чашка перевесит, то считай нам повезло. Допустим, без ограничения общности, перевесила правая, тогда остались варианты: 1) G1 S3, 2) G1 S4, 3) G2 S3, 4) G2 S4, 5) G1 S5, 6) G2 S5 7) G5 S3, :cool: G5 S4, т.е. G3, G4, S1, S2 - подлинные.
На второе взвешивание кладем G1 <-> G2, на третье S3 <-> S4 и там все очевидно.

б) Если на первом взвешивании оказалось равенство, то мы остались с вариантами:

1) G1 S1, 2) G1 S2, 3) G2 S1, 4) G2 S2, 5) G3 S3, 6) G3 S4, 7) G4 S3, :cool: G4 S4. Ну и само собой не забываем 9) G5 S5.

Теперь критическое второе взвешивание:
G1 G3 S1 <-> G2 G4 S2 (!!)
a) "=": осталось 1) G1 S1, 2) G2 S2, 3) G5 S5 - последнее взвешивание тривиально.
б) "<": осталось 1) G1 S2, 2) G3 S3, 3) G3 S4 - последнее взвешивание S3 <-> S4
в) ">": осталось 1) G2 S1, 2) G4 S3, 3) G4 S4 - последнее взвешивание тоже S3 <-> S4

Вуаля. :)
ни-ни. весь цимес в мучениях)))
 
Так, так, так... Ну давайте посмотрим.

1) G1 G2,S1 S2 <-> G3 G4, S3 S4

а) Если какая-то чашка перевесит, то считай нам повезло. Допустим, без ограничения общности, перевесила правая, тогда остались варианты: 1) G1 S3, 2) G1 S4, 3) G2 S3, 4) G2 S4, 5) G1 S5, 6) G2 S5 7) G5 S3, :cool: G5 S4, т.е. G3, G4, S1, S2 - подлинные.
На второе взвешивание кладем G1 <-> G2, на третье S3 <-> S4 и там все очевидно.

б) Если на первом взвешивании оказалось равенство, то мы остались с вариантами:

1) G1 S1, 2) G1 S2, 3) G2 S1, 4) G2 S2, 5) G3 S3, 6) G3 S4, 7) G4 S3, :cool: G4 S4. Ну и само собой не забываем 9) G5 S5.

Теперь критическое второе взвешивание:
G1 G3 S1 <-> G2 G4 S2 (!!)
a) "=": осталось 1) G1 S1, 2) G2 S2, 3) G5 S5 - последнее взвешивание тривиально.
б) "<": осталось 1) G1 S2, 2) G3 S3, 3) G3 S4 - последнее взвешивание S3 <-> S4
в) ">": осталось 1) G2 S1, 2) G4 S3, 3) G4 S4 - последнее взвешивание тоже S3 <-> S4

Вуаля. :)
Всё верно!
Моё решение аналогично
 
Попробуйте проанализировать с точки зрения кол-ва вариантов.
перебрала все имхо возможные методы: по 4 монеты в чашку (1 мое решение), по 3, по 2 одинаковых (2 мое решение), по 2 разных, по 1. Все время остается 1 из вероятностей, где нужно 4 взвешивание. Самая простая- это если к 3му взвешиванию известны 2 монеты сер, из которых точно 1 фальшивая, и такие же 2золотых. Но - за одно 3-е взвешивание оно необязательно определимо.
То есть для меня -тупик.
Еще немного подумаю, и пойду смотреть правильный ответ)
 
перебрала все имхо возможные методы: по 4 монеты в чашку (1 мое решение), по 3, по 2 одинаковых (2 мое решение), по 2 разных, по 1. Все время остается 1 из вероятностей, где нужно 4 взвешивание. Самая простая- это если к 3му взвешиванию известны 2 монеты сер, из которых точно 1 фальшивая, и такие же 2золотых. Но - за одно 3-е взвешивание оно необязательно определимо.
То есть для меня -тупик.
Еще немного подумаю, и пойду смотреть правильный ответ)
Если у Вас к 3-му взвешиванию остаются под подозрением 2 сер и 2 зол, то это 4 варианта. Естественно что за 1 взвешивание это не решается.

О чём это говорит? О том что Ваше 2-е взвешивание было спланировано так что по крайней мере для 1 из результатов взвешивания остаются 4 варианта. А значит либо (1) для разных результатов взвешивания возможные варианты делятся неравномерно (например, 9 распадается на 2 + 2 + 5), либо (2) изначально перед 2-м взвешиванием у Вас было более 9 неотброшенных вариантов.

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

О чём это говорит? О том что Ваше 2-е взвешивание было спланировано так что по крайней мере для 1 из результатов взвешивания остаются 4 варианта. А значит либо (1) для разных результатов взвешивания возможные варианты делятся неравномерно (например, 9 распадается на 2 + 2 + 5), либо (2) изначально перед 2-м взвешиванием у Вас было более 9 неотброшенных вариантов.

В случае (1) постарайтесь взвесить монеты по-другому, чтобы расклад был более равномерным. В случае (2) - та же проблема, но она уже возникла после 1-го взвешивания, уже там начальные 25 вариантов распределились слишком неравномерно.
я поняла, что мой подход изначально тупиковый, нужно искать другой. :)
 
перебрала все имхо возможные методы: по 4 монеты в чашку (1 мое решение), по 3, по 2 одинаковых (2 мое решение), по 2 разных,
Не сдавайся. А чем плохо твое первое решение по 4 монеты на чашку (в качестве первого взвешивания)?
 
Не сдавайся. А чем плохо твое первое решение по 4 монеты на чашку (в качестве первого взвешивания)?
там все уперлось в необходимость 4го взвешивания при одном из раскладов. И если идти по моей методике - то это всюду возникает, хотя бы раз. Метода не та)
 
там все уперлось в необходимость 4го взвешивания при одном из раскладов. И если идти по моей методике - то это всюду возникает, хотя бы раз. Метода не та)
Смотри, по твоей картинке:

IMG_20190501_113115_127.jpg

После первого взвешивания, в случае равенства, остается 9 возможных пар, которые я обозначил черными черточками.
Значит в случае неравенства оставшиеся (25-9) = 16 пар распределятся поровну между "<" и ">". То есть по 8. (поровну - потому что симметрия). Значит для "<", "=", ">" имеем: 8, 9, 8. То есть, первое взвешивание - ОК.
Нужно лишь найти какое должно быть второе взвешивание (что и есть самое сложное в этой задаче).