Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

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

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

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

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

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