Логические задачки

Здесь можно пообщаться на различные темы, не связанные с Гарри Поттером.
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Lady Astrel писал(а):dmart, для того, чтобы закончить этот оффтоп, ещё раз спрашиваю: ты предлагаешь расписать всё решение? Пожалуйста, коротко, да или нет.
Нет. Конкретно этого я не предлагаю.
Но если кто-то может убедительно доказать, что процитированный ответ - единственно возможный, то я предлагаю не затыкать ему рот.
А почему, собственно, обсуждение ответа на логическую задачу в теме про логические задачи - оффтоп?
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

Тема длинная, всю не просматривал - если повтор, прошу простить.

Нумер один.
Перед вами три человека. Вы знаете, что один из них на все вопросы отвечает правдиво, другой всегда лжет, а третий может и правду сказать, и соврать - как фишка ляжет. Но вы не знаете, кто из них кто. Задача: задав ТРИ вопроса, допускающие ответы только "да" и "нет", определить, кто есть кто. Каждый вопрос задается только одному из троих, на ваше усмотрение.

Нумер два.
Вы в комнате, из нее ведут две двери, одна в ад, другая в рай. Вы не знаете, которая куда. У каждой двери стоит человек. Один из них всегда врет, второй всегда говорит правду, но вы не знаете, ни который из двух врет, ни кто у какой двери стоит. Задача: задав ОДИН вопрос, допускающий ответ только "да" или "нет", определить, какая из дверей ведет в рай.

Добавлено спустя 12 минут 14 секунд:

dmart,
dmart писал(а):Решите уравнение (x - 3)(x - 6)(x + 1)(x + 4) = 1080
Пусть некто методом научного тыка угадал корень x=8. Можем мы считать задачу решенной?
Определенно нет :).
Кстати, задачка очень легкая: замена переменной y=x-1 и усе будет. Корни x=8 и х=-6.
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
Аватара пользователя
Lady Astrel
Заслуженный Волшебник
Сообщения: 11577
Зарегистрирован: 05 авг 2004 13:00
Псевдоним: wicked witch
Пол: женский
Откуда: Москва

Сообщение Lady Astrel »

Ushwood писал(а):Нумер два.
Вы в комнате, из нее ведут две двери, одна в ад, другая в рай. Вы не знаете, которая куда. У каждой двери стоит человек. Один из них всегда врет, второй всегда говорит правду, но вы не знаете, ни который из двух врет, ни кто у какой двери стоит. Задача: задав ОДИН вопрос, допускающий ответ только "да" или "нет", определить, какая из дверей ведет в рай.
Я давала аналогичную задачу, но её ответ толком не сформулировали. :wink:
A triffle, a little, the likeness of a dream, and death comes as the end...

Лучший форумец 2007 г.
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

Так. Здесь уйму времени назад задали такую задачку:
Очень безалаберный турист потерял зажигалку, и у него осталась всего одна спичка. Он хотел зажечь обе свои походные плитки (одну--с двумя горелками, другую--простую газовую), походную лампу и прикурить сигарету. Что нужно ему в первую очередь?
На нее был дан ответ "спичку", после чего было сказано, что он правильный.
Не согласен. Поскольку в условии сказано не "что нужно ему ЗАЖЕЧЬ в первую очередь", а "что нужно ему в первую очередь", то ИМХО правильный ответ - спичечный коробок ;)
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Lady Astrel писал(а):
Ushwood писал(а):Нумер два.
Вы в комнате, из нее ведут две двери, одна в ад, другая в рай. Вы не знаете, которая куда. У каждой двери стоит человек. Один из них всегда врет, второй всегда говорит правду, но вы не знаете, ни который из двух врет, ни кто у какой двери стоит. Задача: задав ОДИН вопрос, допускающий ответ только "да" или "нет", определить, какая из дверей ведет в рай.
Я давала аналогичную задачу, но её ответ толком не сформулировали. :wink:
"Если бы я спросил тебя, ведет ли эта дверь в рай, что бы ты ответил?".
Аватара пользователя
Lady Astrel
Заслуженный Волшебник
Сообщения: 11577
Зарегистрирован: 05 авг 2004 13:00
Псевдоним: wicked witch
Пол: женский
Откуда: Москва

Сообщение Lady Astrel »

dmart, а ход рассуждений? :wink:
A triffle, a little, the likeness of a dream, and death comes as the end...

Лучший форумец 2007 г.
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Ushwood писал(а):
dmart писал(а):Решите уравнение (x - 3)(x - 6)(x + 1)(x + 4) = 1080
Пусть некто методом научного тыка угадал корень x=8. Можем мы считать задачу решенной?
Определенно нет :).
Кстати, задачка очень легкая: замена переменной y=x-1 и усе будет. Корни x=8 и х=-6.
Верно. Красивая задачка. Легкая, но только если увидеть замаскированную симметрию.
Последний раз редактировалось dmart 19 май 2008 18:12, всего редактировалось 7 раз.
Аватара пользователя
Lady Astrel
Заслуженный Волшебник
Сообщения: 11577
Зарегистрирован: 05 авг 2004 13:00
Псевдоним: wicked witch
Пол: женский
Откуда: Москва

Сообщение Lady Astrel »

dmart писал(а):Вынудить лжеца солгать дважды, и тем самым, сказать в итоге правду.
А вот по-подробней бы...
A triffle, a little, the likeness of a dream, and death comes as the end...

Лучший форумец 2007 г.
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Lady Astrel, восстановить всю цепочку рассуждений, приведшую к такому варианту ответа, уже вряд ли удастся.

Добавлено спустя 1 час 8 минут 47 секунд:
Ushwood писал(а):Нумер один.
Перед вами три человека. Вы знаете, что один из них на все вопросы отвечает правдиво, другой всегда лжет, а третий может и правду сказать, и соврать - как фишка ляжет. Но вы не знаете, кто из них кто. Задача: задав ТРИ вопроса, допускающие ответы только "да" и "нет", определить, кто есть кто. Каждый вопрос задается только одному из троих, на ваше усмотрение.
В нумере два мы научились узнавать правду от лжеца. Здесь первым делом надо локализовать обманщика (так для краткости назовем того, кто может и правду сказать, и соврать, так что толку от него не добьешься). На это придется потратить 2 вопроса.
Задаем первому вопрос, уже знакомый из решения нумера два: "Если бы я спросил, обманщик ли второй, что бы ты ответил?". Если ответ "да", то обращаемся с тем же вопросом к третьему. Как минимум один из двоих должен ответить правильно, поэтому, если и третий говорит "да", то обманщик действительно второй. Если допрашиваемые путаются в показаниях, обманщик один из них, а именно тот, кто сказал "да".
Если первый ответил "нет", то он сам попадает под подозрение. Тогда спрашиваем второго: "Если бы я спросил, обманщик ли первый, что бы ты ответил?". Ответ "да" подтвержает подозрение, что обманщик первый, ответ "нет" - означает, что обманщик третий.
Теперь мы знаем, кто из троих обманщик, у нас остался один вопрос и два человека, один из которых честный, а другой - лжец. Задача благополучно свелась к уже решенному нумеру два.
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

dmart,
dmart писал(а):Задаем первому вопрос, уже знакомый из решения нумера два: "Если бы я спросил, обманщик ли второй, что бы ты ответил?". Если ответ "да", то
Вопрос некорректен. В определенной ситуации первый может изначально не знать, что он бы ответил на вопрос "обманщик ли второй?", потому предложенный тобой вопрос допускает ответ "не знаю", следовательно, он запрещен условием задачи.
Первая задача решается совершенно не так, как вторая ;).
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Ushwood, а задача вообще решается, если сами допрашиваемые не знают, кто из них лжец, а кто обманщик?
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

dmart, сами допрашиваемые это знают, разумеется.
Но обманщик не знает, что он сам ответит на следующий вопрос - правду или ложь ;).
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Ushwood писал(а):dmart, сами допрашиваемые это знают, разумеется.
Но обманщик не знает, что он сам ответит на следующий вопрос - правду или ложь ;).
Ответом "не знаю" он сам себя выдаст. Поэтому ответит "да" или "нет" из каких-то своих соображений.
Кстати, спрашивают его не что он ответит на следующий вопрос, а что бы он ответил на предыдущий.
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

dmart,
dmart писал(а):Ответом "не знаю" он сам себя выдаст.
Ты удаляешься от сути.
Во-первых, перед обманщиком вовсе не стоит задача "себя не выдать". Во-вторых, вопрос не в том, что и в каких условиях он ответит, а в том, что ответ "не знаю" на этот вопрос принципиально возможен, а следовательно - этот вопрос запрещен условием задачи.
Поэтому советую искать другое решение, принципиально не включающее в себя такого рода "условные" вопросы.
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

Ну что, ответ с решением давать? :) Времени прошло изрядно. Или народ желает думать дальше?

Чтоб было веселее думать, вот еще задачка.
Имеется квадрат 10х10 клеток. Его нужно замостить плитками 1х4.

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

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

Поскольку прошло много времени, полагаю, что уже можно давать решение первой из предложенных мной задач. Ниже приведена именно та логическая цепочка, в результате которой ответ нашел я сам :).

Итак, у нас три человека, назовем их А, Б и В. Каждый из них может быть (р)ыцарем, (л)жецом, и для третьего я применяю термин (х)амелеон (либо хаотик, либо хитрец - кому как больше нравится :)). Возможных раскладов, очевидно, 6, вот они:
А Б В
р л х
р х л
л р х
л х р
х р л
х л р

1. Поскольку каждый вопрос, допускающий ответ "да" или "нет", позволяет различить два варианта, то три вопроса принципиально позволяют различить 8 вариантов. Следовательно, задача принципиально разрешима, и даже на первый взгляд условие избыточно.
2. Однако второй взгляд показывает, что первый взгляд неверен. Ведь если вопрос будет задан хаотику, он может ответить и "да", и "нет", т.е. соответствующий вариант как бы "расщепляется" на два, и реально у нас вариантов не 6, а 8.
3. Отсюда важный вывод: кроме как на первом вопросе, мы не должны допускать расщепления вариантов, иначе задача станет нерешаемой. Следовательно, уже второй вопрос мы должны задавать гарантированно не-хаотику. Т.е. первым вопросом мы должны точно найти не-хаотика. Если мы это сделаем, то дальнейшее уже будет делом техники: вторым вопросом мы узнаем у этого не-хаотика, рыцарь он или лжец (например, задав тривиальный вопрос типа "верно ли, что 2х2=4?"), а третьим - узнаем, кто двое остальных.
Итак, вся загвоздка в первом вопросе.
4. Если мы задаем первый вопрос А - ясно, что мы никак не можем определить этим вопросом, хаотик ли сам А. Значит, нам надо подобрать такой вопрос, ответ "да" на который означал бы, что Б не хаотик, а ответ "нет" - что В не хаотик. Или наоборот.
Ясно, что, подбирая вопрос, мы можем уже не волноваться, что ответит А, если он сам хаотик - т.к. что бы он ни ответил в этом случае, все равно и Б, и В не хаотики.
5. Ищем вопрос с ответом "да" при раскладах р-л-х и л-р-х и "нет" при раскладах р-х-л и л-х-р. Или, что то же самое, ищем логическое утверждение, истинное в случаях р-л-х и л-х-р и ложное в случаях р-х-л и л-р-х.
6. Такое утверждение находится теперь очень легко: "Б лжет чаще (т.е. в большем проценте случаев), чем В".

Итак, ответ на задачку.
Первый вопрос: верно ли, что Б лжет чаще, чем В?
Второй вопрос: верно ли, что 2х2=4?
Третий вопрос: верно ли, что А хаотик?
Первый вопрос задается А, второй и третий задаются Б, если ответ на первый вопрос "да", и В, если ответ на первый вопрос "нет".
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Ushwood писал(а):Итак, ответ на задачку.
Первый вопрос: верно ли, что Б лжет чаще, чем В?
Попрошу разжевать. 1) Предположим, нам не повезло, и первый вопрос мы задали хаотику. Какую полезную информацию даст нам ответ на этот вопрос? 2) Что запрещает хаотику ответить на этот вопрос "не знаю"?
Остаюсь при своем мнении, что вычислить хаотика одним вопросом невозможно.

Добавлено спустя 8 минут 1 секунду:
Ushwood писал(а):dmart,
dmart писал(а):Ответом "не знаю" он сам себя выдаст.
Ты удаляешься от сути.
Во-первых, перед обманщиком вовсе не стоит задача "себя не выдать".
Перед обманщиком стоит задача максимально затруднить нам решение.
Ushwood писал(а):Во-вторых, вопрос не в том, что и в каких условиях он ответит, а в том, что ответ "не знаю" на этот вопрос принципиально возможен, а следовательно - этот вопрос запрещен условием задачи.
Лжец и обманщик принципиально могут ответить "не знаю" на любой вопрос.
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

dmart писал(а):Остаюсь при своем мнении, что вычислить хаотика одним вопросом невозможно.
Ты безусловно прав, вычислить хаотика одним вопросом невозможно. А вот вычислить НЕхаотика одним вопросом возможно, что и делается :).
1) Предположим, нам не повезло, и первый вопрос мы задали хаотику. Какую полезную информацию даст нам ответ на этот вопрос?
Что второй вопрос мы можем задавать как Б, так и В, с нулевым шансом нарваться на хаотика.

Смотри. Предположим, А ответил "да". Это возможно в следующих случаях: р-л-х, л-р-х, х-р-л, х-л-р. В ЛЮБОМ из этих четырех случаях, задав следующий вопрос Б, мы гарантируем отсутствие "расщепления". А собсно кто хаотик, А или В - мы выясним третьим вопросом, заданным опять-таки Б.
При первом ответе "нет" - аналогично.
Перед обманщиком стоит задача максимально затруднить нам решение.
Процитируй строку в условии задачи, где это сказано.
dmart писал(а):Лжец и обманщик принципиально могут ответить "не знаю" на любой вопрос.
Неправильно. На те вопросы, ответы на которые они знают, они ответят только ложью (для лжеца) либо ложью/правдой (для хаотика). Ответ "не знаю" принципиально возможен только на тот вопрос, на который они ДЕЙСТВИТЕЛЬНО не знают ответа, и вопрос "что ответил бы хаотик на такой-то вопрос?" относится как раз к таким.
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
dmart
Староста
Сообщения: 1554
Зарегистрирован: 27 авг 2004 11:38
Пол: мужской
Откуда: Дежавютон

Сообщение dmart »

Ushwood писал(а):Смотри. Предположим, А ответил "да". Это возможно в следующих случаях: р-л-х, л-р-х, х-р-л, х-л-р. В ЛЮБОМ из этих четырех случаях, задав следующий вопрос Б, мы гарантируем отсутствие "расщепления". А собсно кто хаотик, А или В - мы выясним третьим вопросом, заданным опять-таки Б.
При первом ответе "нет" - аналогично.
Красиво. Трудно поверить, что, задав один вопрос человеку, который, возможно, обманщик, можно получить хотя бы бит полезной информации, но получается, что это так.
Насчет задачи, как замостить квадрат 10x10 плитками 1x4 - могу доказать, что это невозможно.
Распишем квадрат цифрами:
1234123412
2341234123
3412341234
4123412341
1234123412
2341234123
3412341234
4123412341
1234123412
2341234123
Каждая плитка, как бы ее ни уложили, закрывает 4 разных цифры. Но двоек здесь 26, а четверок - 24. Так что замостить никак не получится.
Аватара пользователя
Ushwood
Заслуженный Волшебник
Сообщения: 1673
Зарегистрирован: 03 апр 2005 15:57
Псевдоним: Парадоксов друг
Пол: мужской
Откуда: Москва

Сообщение Ushwood »

dmart, с квадратом - решил правильно :).

Следующая задачка. В том же квадрате 10х10 разместить два набора кораблей для игры в "морской бой" в соответствии с классическими правилами игры.
P.S. Мнение автора может не совпадать с его точкой зрения.

Мои переводы:
Гарри Поттер и Принц-Полукровка (см. сайт)
Гарри Поттер и Реликвии Смерти (обращайтесь)
Аватара пользователя
Melkii`
Лавгуд
Сообщения: 5080
Зарегистрирован: 16 май 2005 18:40
Пол: мужской
Откуда: Montréal

Сообщение Melkii` »

АБВГДЕЖЗИК
11XXXX6XXXX
21234567890
3X23456789X
4123456789X
5X23456789X
61234567890
7X23456789X
8X23456789X
9123456789X
0XXX45XXX90

Для того, чтобы наиболее громоздкие корабли занимали меньше места, попорбуем прижать их к бортам - на максимально близком расстоянии окажутся 2 четырехпалубника, 4 трехпалубника, 1 двухпалубник и 2 однопалубника (как вариант - 2 двухпалубника, но на одном двухпалубнике мы выиграем 4 клетки, тогда как на двух однопалубниках - 6).
Далее, у нас останется квадрат 8*8, то есть, 64 клетки.
Мы знаем, что размещенный по правилам двухпалубник занимает 12 клеток, однопалубник - 9.
Отсюда, чтобы разместиьт все оставшиеся корабли, нам понадобится 12*4+6*9=104 клетки, тогда как у нас только 64.
Следовательно, разместить в таком квадрате два набора для морского боя невозможно.
Последний раз редактировалось Melkii` 06 июн 2008 18:47, всего редактировалось 5 раз.
Так долго строить храм и сжечь за миг
Лишь может тот, кто этот храм воздвиг
Аватара пользователя
Lady Astrel
Заслуженный Волшебник
Сообщения: 11577
Зарегистрирован: 05 авг 2004 13:00
Псевдоним: wicked witch
Пол: женский
Откуда: Москва

Сообщение Lady Astrel »

Melkii`, если я правильно поняла твои расчёты, у тебя 3 четырёхпалубника.

Добавлено спустя 17 минут 24 секунды:
Melkii` писал(а):однопалубник - 9.
А два однопалубника - 15. Ты это учитывал?
A triffle, a little, the likeness of a dream, and death comes as the end...

Лучший форумец 2007 г.
Аватара пользователя
Melkii`
Лавгуд
Сообщения: 5080
Зарегистрирован: 16 май 2005 18:40
Пол: мужской
Откуда: Montréal

Сообщение Melkii` »

Изменил, теперь количество четырехпалубников вернулось в норму.
А два однопалубника - 15. Ты это учитывал?
Ммм, нет. Сейчас подумаем(=.

Добавлено спустя 15 минут 36 секунд:

Хм. У нас остается квадратик 6х6.
Аналогично расставляем корабли:

XX4XX7X
34567X
X4XX78
34567X
X4X67X

Остается два поля в центре, в которые и можно уместить один кораблик.
А у нас еще осталось три однопалубных.
Последний раз редактировалось Melkii` 06 июн 2008 22:23, всего редактировалось 1 раз.
Так долго строить храм и сжечь за миг
Лишь может тот, кто этот храм воздвиг
Аватара пользователя
Lady Astrel
Заслуженный Волшебник
Сообщения: 11577
Зарегистрирован: 05 авг 2004 13:00
Псевдоним: wicked witch
Пол: женский
Откуда: Москва

Сообщение Lady Astrel »

Melkii` писал(а):три однопалубных.
На твоей схеме размещены сейчас 7 однопалубников...
A triffle, a little, the likeness of a dream, and death comes as the end...

Лучший форумец 2007 г.
Аватара пользователя
Melkii`
Лавгуд
Сообщения: 5080
Зарегистрирован: 16 май 2005 18:40
Пол: мужской
Откуда: Montréal

Сообщение Melkii` »

Где 7? 5 же.
А3, А5, В5, В7, Д7.
2 на верхней схеме и 3 на нижней.
Так долго строить храм и сжечь за миг
Лишь может тот, кто этот храм воздвиг

Вернуться в «Общение на свободные темы»