18 нояб. 2009 г.

Транзитивность

Добрый день.

В недавней заметке о разборчивой невесте мы рассматривали группу кандидатов, между которыми есть транзитивное отношение. Записывали мы это так: если А лучше Б, а Б лучше В, то А заведомо лучше В для произвольных A, Б и В. При выполнении этого условия для любой тройки кандидатов можно говорить, что отношение «лучше» является транзитивным.

Например, отношение «тяжелее» тоже является транзитивным: если А тяжелее Б, который тяжелее В, то А тяжелее В. С числами тоже всё легко: если a>b и b>c, то a>c. Легко показать, что свойства параллельности прямых или делимости чисел являются транзитивными.

А отношение дружбы уже может не быть транзитивным: иногда бывает так, что одному и тому же человеку рады в двух воинствующих компаниях. Отношение «коллега» тоже не обязано быть транзитивным: если А и Б работают в одной организации, а Б и В тоже работают в одной организации, то это не значит, что А и В коллеги, так как Б может успевать работать в двух разных местах. Отношение любви вообще не является транзитивным: если А любит Б, а Б любит В, то, скорее всего, А испытывает к В неприязнь.

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

Но сначала давайте поймём, как вообще можно считать вероятность того, что одна кость выиграет другую. Предлагаю доверить это дело компьютеру (кстати, это неплохая задачка для освоения его возможностей): запускаем любой табличный процессор и записываем в него строчку и столбец из 6 чисел - значения на гранях первого и второго кубиков, соответственно. В образовавшееся поле 6 на 6 клеток поставим статусы «победил»/«проиграл» (я ставил 1 и 0, чтобы было проще считать). Для этого я записал формулу в верхнюю левую ячейку таблицы, которая для каждой из 36 ячеек сравнивает самое левое число (с грани одного кубика) с самым верхним (с грани второго кубика) - моя формула видна в верхнем правом углу изображений. А потом просто «растянул» эту ячейку на оставшиеся 35 клеток, чтобы получить результаты для всех возможных состояний.

Что мы получили? Сейчас поймём! Один кубик может выпасть шестью разными способами. Второй - тоже шестью способами. Поскольку кубики друг на друга не влияют, то есть 36 разных равновероятных вариантов состояний пары кубиков после броска. Вот мы и рассмотрели все эти 36 вариантов. Остаётся просуммировать единички в таблице, чтобы увидеть, что кубик, значения граней которого расположены вертикально, побеждает в 21 случае из 36. Это значит, что с вероятностью примерно 58% кость (2 3 4 15 16 17) окажется сильнее кости (1 8 10 11 13 14).

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

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

Другими словами, побеждает тот, кто размещает числа на кубиках, а не тот, кто выбирает любой из трёх кубиков, как многим кажется. Напишите, пожалуйста, с какими случаями иллюзии транзитивности вы сталкивались. Бывают не только математические задачки, но и вполне жизненные ситуации - интересны и те, и другие.

Хорошей вам недели!

20 комментариев:

  1. Инертность мышления и сила привычки - вообще злые вещи.
    Вот, наверняка, все из вас слышали фразу «добро всегда побеждает зло».
    А многие ли из вас замечали двоякость этой фразы?
    Ведь и у слова «добро» и у слова «зло» совпадают именительный и винительный падежи. А значит, учитывая свободный порядок в русском языке, подлежащим (а следовательно и побеждающим) может оказаться как «добро» и «зло».

    Тем, кто запутался, пример: «дым всегда порождает пламя».

    ОтветитьУдалить
  2. Анонимный18.11.2009, 17:23

    Как ни странно, отношение "звук А выше звука B" нетранзитивно - на этом основана иллюзия Шепарда. Последовательность звуков расположена по кругу так, что каждый кажется выше соседнего по часовой стрелке и нельзя выделить среди них самый высокий. Послушать можно, например, здесь: http://www.youtube.com/watch?v=Br4qrnoEJhY и в других видеоклипах по запросу Shepard tone.

    ОтветитьУдалить
  3. Не понял - ни первого ни второго комментария.

    ОтветитьУдалить
  4. Первый комментарий к транзитивности отношения не имеет. Просто мысли вслух.

    ОтветитьУдалить
    Ответы
    1. Имеет, если рассматривать интранзитивный (непереходный) характер выражения. Разотождествление, непричастность человека ко всему, что происходит в мире.

      Пример: Мне не спится. Мне не здоровится. Можно много работать, но мало сделать. Работать - непереходный глагол, делать - переходный. Общая тенденция русского менталитета - стремление к интранзитивизации, что и отражает язык.

      Удалить
  5. Комментарий немного в сторону...
    Уж раз есть заметка об одной распространенной ошибке (про "-тся/-ться"), которую, однако, грамотные люди все же чаще не допускают, нежели допускают, у меня есть идея сходной заметки про другую распространенную ошибку, которую допускают почти все, в том числе, к примеру, Виктор Цой и, тоже к примеру, Вы, Илья, в этой самой заметке.

    Речь идет о неправильном употреблении "не" и "ни" в выражениях типа "где бы ты ни был".

    Сначала - ссылка на правила с сайта gramota.ru.
    Чтобы представить себе размах ситуации, приведу несколько примеров из Гугла:
    "кто бы ни" - 4,450,000 результатов
    "кто бы не" - 8,520,000 результатов
    "где бы ни" - 3,890,000
    "где бы не" - 7,500,000
    "какой бы ни" - 2,870,000
    "какой бы не" - 4,750,000

    Часть этих результатов, вне сомнения, вызвана случаями правильного употребления "кто/где/какой бы не..." (сравните: "Не было страны, где бы он не был" и "Где бы он ни был, он находил время написать родным"). Но общая тенденция говорит, что неправильное употребление "не" и "ни" людям глаза уже не разу ни режет :) Или мы наблюдаем процесс эволюции языка?

    ОтветитьУдалить
  6. Анонимный19.11.2009, 6:41

    Большое спасибо за Ваш блог. Он как никакой другой часто заставляет чувствовать себя дураком

    ОтветитьУдалить
  7. Анонимный19.11.2009, 6:48

    Илья, вот Вы пишете

    > Не так сложно найти набор из трёх кубиков, для которых отношение «сильнее» не является транзитивным (как мы убедились выше, легко реализовать перебор на компьютере)

    А ведь это не так-то просто! Надо перебрать 18! вариантов, т.е. ~6*10^15. Это очень много! Не у всех есть доступ к суперкомпьютеру :-)

    ОтветитьУдалить
  8. Анонимный19.11.2009, 7:12

    >А ведь это не так-то просто! Надо перебрать 18! вариантов, т.е. ~6*10^15. Это очень много! Не у всех есть доступ к суперкомпьютеру :-)

    Зачем же перебирать все варианты, если в среднем каждая двухсотая случайно раскрашенная тройка костей нетранзитивна?

    ОтветитьУдалить
  9. LisandreL, спасибо за пример интересной фразы!

    Уважаемый аноним, благодарю за напоминание об иллюзии Шепарда. Мы о ней недавно вспоминали, но здесь она как раз к месту. Надо только отдавать себе отчёт, что отношение "выше" для нот транзитивно, а вот ощущения при восприятии аккордов могут человека обмануть, создав иллюзию постоянно повышающихся звуков.

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

    Уважаемый аноним, благодарю за тёплые слова.

    Отмечу только, что оценка 18! слишком завышена. Дело в том, что при анализе кубиков нам не важен порядок чисел на каждом из них, поэтому вычисленное количество состояний каждой кости можно смело делить на 6! (количество перестановок). Более того, про один из кубиков можно заранее решить, что на нём всегда будет число 18, например (так мы сокращаем перебор ещё в 18 раз). А на "втором" кубике пусть всегда будет большее из 12-ти оставшихся чисел (нам не важно, на какой из двух оставшихся оно попадёт). Это позволяет заметно сократить перебор одинаковых раскрасок.

    Если учесть данные замечания, то окажется, что что расположить 18 чисел по трём костям можно следующим количеством способов:

    17*16*15*14*13*11*10*9*8*7/(5! * 5!)=2858856 - это чуть меньше трёх миллионов. Такой перебор уже не должен пугать :)

    ОтветитьУдалить
  10. ---, едва ли тут можно говорить об эволюции языка, так как тут «е» и «и» несут разный смысл…
    Хотя, вспоминая упразднение «i», которое свело два слова «мир» в одно, думается, что всё может быть.

    ОтветитьУдалить
  11. > …по поводу очень распространённой ошибки. И спосибо, что указали на неё…
    Это шутка или очепятка?

    ОтветитьУдалить
  12. LisandreL, эх, это опечатка :( Увы, я её даже исправить не могу, так как нет возможности редактировать комментарии.

    ОтветитьУдалить
  13. По-моему ваш пример с подсчетом в экселе неудачен, как в нем перебирать числа, что-бы найти нетранзитивные элементы? По поводу транзитивности к задаче понял из комментария к предыдущей заметке, а как доказать, что она существует, или найти какой-либо вариант без использования компьютера(что вы рекомендовали делать в старых статьях) не додумался.

    ОтветитьУдалить
  14. al31f, благодарю за интересное мнение.

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

    Перебор же можно делать в чём угодно (даже на 1С). И в Excel тоже есть достаточно мощный для подобных задач язык, поэтому проблемы с этим нет.

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

    А найти нетранзитивную тройку кубиков не очень трудно своей головой. Человек - не компьютер, поэтому ведёт осмысленный перебор, быстро исключая заведомо неудачные расстановки (на которые компьютер потратил бы много итераций). Попробуйте! И Вы сами тоже найдёте нетранзитивную тройку :)

    ОтветитьУдалить
  15. "...побеждает тот, кто размещает числа на кубиках, а не тот, кто выбирает любой из трёх кубиков..."

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

    PS Илья, извините за предыдущий комментарий - как-то я совсем по диагонали второпях прочитал заметку, и просто повторил в комментарии то, что и так было в заметке..-)

    ОтветитьУдалить
  16. al31f,
    подсчёт в экселе, предложенный Ильёй, на мой вкус, очч хорош, так как нагляден. Он может дать зацепочку для понимания природы этой нетранзитивности.
    Собственно, откуда берётся интуитивное предположение о транзитивности? Если мы бросаем кубики не попарно, а все три сразу, то для каждого испытания отношение между кубиками транзитивно: если A выиграл у B, а B выиграл у C, то A выиграл и у C.
    Табличка исходов даёт нам понимание, как пытаться сконструировать нетранзитивную тройку. Кубик может выигрывать как за счёт превосходства "по строкам", так и за счёт превосходства "по столбцам". В первом случае у кубика должны быть большие числа (чтобы одно число выигрывало максимальное количество вариантов), в другом случае - должно быть большее количество вариантов, которые выигрывают в среднем больше половины испытаний.
    Таким образом, мы имеем 2 "координаты" - выигрыш за счёт "маленького количества больших превосходств" и выигрыш за счёт "большого количества небольших превосходств".
    А где 2 координаты - там и "закольцевать" можно.

    ОтветитьУдалить
  17. abyrvalgХотя да, был неправ, когда говорил что неудачен. В таблице нагляднее всего виден принцип по которому один кубик побеждает другого. Просто это для меня было понятно, поэтому мне было интереснее, как определить что нетранзитивность существует. )

    ОтветитьУдалить
  18. Анонимный03.12.2009, 18:24

    В книге "Справочник экономиста-афериста" можно найти много примеров интересных нетранзитивностей в области экономики. И много других вероятностных парадоксов.

    ОтветитьУдалить
  19. Анонимный30.03.2013, 15:36

    Что вы тут умничаете..

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний