Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

мимоходом, математическое

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

Я только что пытался вспомнить в уме, не подглядывая, почему пятнашки нельзя собрать, если поменять местами 14 и 15. Я помнил, что доказательство там как-то связано с четностью перестановок, но не помнил, как. Рассуждал так: какой самый простой способ связать положение доски с перестановкой, чтобы конечное положение было тождественной перестановкой? Назовем пустую клетку 16-й, пронумеруем поля доски от 1 до 16 очевидным способом, и тогда любое положение определяет перестановку: номер поля переходит в номер костяшки, к-я на самом деле стоит на этом поле.

Но: если теперь посмотреть, что происходит, когда двигается любая костяшка, то это соответствует транспозиции, т.е. четность перестановки наоборот меняется после каждого шага, а не сохраняется. Вот это "наоборот" должно было мне сразу подсказать правильное решение (но не подсказало, потому что я тормоз). Если "наоборот" меняется после каждого шага, от этого легко придти к чему-то, что сохраняется после каждого шага; например, надо добавить что-то еще, что тоже меняется после каждого шага. А это, например, четность положения пустой клетки. Вот и все. [1]

[1] Поправка благодаря анониму в комментах: не "четность положения пустой клетки", к-я двигается напр. с 4 на 8, а скажем "четность сумм координат пустой клетки", которая действительно меняется после каждого шага.
Subscribe

  • еще о текущих событиях

    Понравилось из записи Сестры Мило: "Муж рассказал, как знакомый сотрудника столкнулся с тем, что у него закончились какие-то детали, которые раньше…

  • о шпаргалках

    Анна Фрид в фейсбуке: "Я очень коварная женщина. Каждый раз, когда я могу сама выбирать, чем можно пользоваться на экзамене, а чем нельзя, я…

  • из газы

    My Child Asks, ‘Can Israel Destroy Our Building if the Power Is Out?’ Нью-Йорк Таймс опубликовали статью профессора литературы из Газы, где он…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments

  • еще о текущих событиях

    Понравилось из записи Сестры Мило: "Муж рассказал, как знакомый сотрудника столкнулся с тем, что у него закончились какие-то детали, которые раньше…

  • о шпаргалках

    Анна Фрид в фейсбуке: "Я очень коварная женщина. Каждый раз, когда я могу сама выбирать, чем можно пользоваться на экзамене, а чем нельзя, я…

  • из газы

    My Child Asks, ‘Can Israel Destroy Our Building if the Power Is Out?’ Нью-Йорк Таймс опубликовали статью профессора литературы из Газы, где он…