Блог пользователя Planshetnik

Автор Planshetnik, 14 лет назад, По-русски
В 7-го марта, Маша сказала, что после 8-го марта все сказанное ею до 8-го марта станет ложью. Правду ли она сказала?

Объясните.
  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Нет!
14 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
У Гарднера есть хорошее рассуждение на эту тему, примерно такое:

Рассмотрим прямоугольник с двумя утверждениями:
-----------------------------------------------------
| (1) Все утверждения в этом прямоугольнике ложны.  |
| (2) Маша сказала правду.                          |
-----------------------------------------------------

Предположим, что утверждение (1) истинно. Тогда получаем, что (1) и (2) ложны. Но (1) не может быть истинным и ложным одновременно. То есть мы пришли к противоречию. Таким  образом, можно заключить, что (1) ложно. Следовательно, верно следующее: не все утверждения в этом прямоугольнике ложны. Учитывая, что (1) ложно, получаем, что (2) не может быть ложным, таким образом, Маша сказала правду.
И не сомневайтесь :)

В оригинале, правда, рассуждение было гораздо длиннее, на страницу-полторы (не помню уж, как он этого достиг; я старалась писать как можно подробнее).
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Вспоминал, вспоминал в каком детективе это рассуждение помогло Пэри Мейсону :).
    Потом сообразил, что надо заглянуть в Википедию.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      (заглянула в гугл, узнала, кто такой Пэри Мэйсон)

      У нас тоже на разных полках стояли разные Гарднеры, оба в большом количестве, но до того, который детективы, я так и не добралась. Так что у меня по умолчанию Гарднер это Мартин :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, как раз в голове крутилась эта рекурсия:
    "Тогда получаем, что (1) и (2) ложны. Но (1) не может быть истинным и ложным одновременно. То есть мы пришли к противоречию."  но не понять почему следует что оно ложно "Таким  образом, можно заключить, что (1) ложно", как называется книга у Гарднера?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      "но не понять почему следует что оно ложно" - ну да, тут неприятность именно в том, что из того, что утверждение не истинно, вообще говоря не следует, что оно ложно. Утверждение (1) - просто один из многих примеров утверждения, которое ни истинно, ни ложно.

      В вашей задаче Маша вообще покусилась на святое :) Что это еще за "станет ложью"? Она с тем же успехом могла сказать, что все тройки после 8-го марта станут пятерками. Чем бы ни было такое утверждение, оно не может являться правдой в обычном математическом смысле слова. Является ли оно ложью более тонкий вопрос (по-моему, не является), но нас вроде и не спрашивают :) Ответ - нет, то что она сказала не является правдой.

      Как называется книга точно не помню, вероятно, это были "Математические досуги". Вот, нашла конкретную статью:
      http://golovolomka.hobby.ru/books/gardner/surprize.shtml
14 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Тут слишком просто -- если она сказала правду, то это приводит к противоречию (так как она сказала правду, то все, что сказано до 8-ого стало неправдой, включая это утверждение). Если она сказала неправду, то никаких противоречий нет.

 

Вот другая клевая задачка, не на логику, а просто:

Вы находитесь в 100 этажном небоскребе. У вас есть два котенка. Вы хотите узнать, с какого максимального этажа можно сбросить котенка, чтобы он не отгреб. Известно, что для всех котят эта величина одинакова. Сколько бросков в худшем случае придется вам сделать, если вы будете действовать оптимально.

(Например, если бы у вас был один котенок, то единственная возможная стратегия была бы бросать его на каждом этаже начиная с первого -- то есть в худшем случае было бы 100 бросков. С двумя котятами, например, можно бросать первого котенка только с четных этажей пока он не отгребет, а потом бросить второго на этаж ниже того, с которого первый котенок отгреб, чтобы проверить его -- тогда в худщем случае бросков будет будет 51. Надо найти такую стратегию, когда количество бросков в худшем случае минимально).

  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    На Тимусе есть подобная задача Chernobyl’ Eagle on a Roof .

    Я решил через простенькую рекуррентную формулу + двоичный поиск.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Будем бросать первого через каждые 10 этажей начиная снизу пока он не отгребет. Тогда через максимум 10 бросков будем знать отрезок в 10 этажей который нужно проверить вторым котенком. Итого максимум 20 бросков. А можно ли ее решить с еще меньшим количеством бросков?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ответ: log(N) + 1 -> log(50) + 1 = 6 + 1 = 7 бросков!

    Сначало сбросим котенка с 50-го этажа. Если умрет, то скинем с этажа номером (текущий / 2). Если не умрет, то скинем с этажа номером (текущий + (текущий / 2)). И так далее. Короче это бин поиск :)

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это неверно, ведь есть только 2 котенка и котят подымать из мертвых нельзя.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А если после смерти первого котёнка при падении с 50 этажа второй, после падения с 25, тоже умрёт? у нас ведь только 2 котёнка!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Бросаем с 13, 26 и тд... Имеем максимум 7 бросков. Затем с 15(28...) через один - еще 6... Получается 13 бросков
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Зачем через один? Если котят нельзя скидывать с высоты 15, то это все равно ничего не говорит насчет 14 этажа.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Пусть этаж = 14. Кинем с 13 - все хорошо, с 26 - первый котенок умер. Кидаем с 15 - второй умер. А как нам теперь узнать что этаж 14-й?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Предполагал за ответ "правду" приходил к противоречию, следовательно ответ "ложь", так как "правда" приводит к противоречию, но когда пытался предположить ответ "ложь", тогда получалось что ложно и то высказывание что все ложь (что значит что высказывание не ложь). 
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Нет, если ее утверждение ложь -- это не значит, что ВСЕ утверждения до 8-ого марта правдивы. Это значит, что хотя бы одно утверждение до восьмого марта правдиво. Так что никакого противоречия нет.

       

14 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится
Если я правильно понял вашу идею, то если при падении с 26 этажа котенок умрет, то нам понадобится 14 бросков. (комментарий ушел не туда, предназначался для Artishok)

Мой ответ 14. Бросаем с 14 этажа, потом с 27, потом с 39,50,60,69,77,84,90,95,99,100.
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
>все сказанное ею до 8-го марта станет ложью

что значит станет ложью? Маша что-ли не утверждениями разговаривает, а предикатами?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Как карета у золушки превратится в тыкву, так и сказаное Машей в false : )