мимоходом, математическое
Nov. 24th, 2009 04:39 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНе знаю, как это хорошо сформулировать, но есть такой общий принцип: полная противоположность тому, что надо - тоже хорошо, именно потому, что полная: значит, ее легко перевернуть и получить, что надо. Тривиальный пример: предположим, мы хотим найти удобную функцию, которая на интересующих нас данных обязательно дает положительный результат. И как назло, кандидат, который мы нашли, как раз наоборот всегда дает отрицательный результат. Ясно, что надо не расстраиваться, а просто умножить на -1 и получить то, что надо.
Я только что пытался вспомнить в уме, не подглядывая, почему пятнашки нельзя собрать, если поменять местами 14 и 15. Я помнил, что доказательство там как-то связано с четностью перестановок, но не помнил, как. Рассуждал так: какой самый простой способ связать положение доски с перестановкой, чтобы конечное положение было тождественной перестановкой? Назовем пустую клетку 16-й, пронумеруем поля доски от 1 до 16 очевидным способом, и тогда любое положение определяет перестановку: номер поля переходит в номер костяшки, к-я на самом деле стоит на этом поле.
Но: если теперь посмотреть, что происходит, когда двигается любая костяшка, то это соответствует транспозиции, т.е. четность перестановки наоборот меняется после каждого шага, а не сохраняется. Вот это "наоборот" должно было мне сразу подсказать правильное решение (но не подсказало, потому что я тормоз). Если "наоборот" меняется после каждого шага, от этого легко придти к чему-то, что сохраняется после каждого шага; например, надо добавить что-то еще, что тоже меняется после каждого шага. А это, например, четность положения пустой клетки. Вот и все. [1]
[1] Поправка благодаря анониму в комментах: не "четность положения пустой клетки", к-я двигается напр. с 4 на 8, а скажем "четность сумм координат пустой клетки", которая действительно меняется после каждого шага.
Я только что пытался вспомнить в уме, не подглядывая, почему пятнашки нельзя собрать, если поменять местами 14 и 15. Я помнил, что доказательство там как-то связано с четностью перестановок, но не помнил, как. Рассуждал так: какой самый простой способ связать положение доски с перестановкой, чтобы конечное положение было тождественной перестановкой? Назовем пустую клетку 16-й, пронумеруем поля доски от 1 до 16 очевидным способом, и тогда любое положение определяет перестановку: номер поля переходит в номер костяшки, к-я на самом деле стоит на этом поле.
Но: если теперь посмотреть, что происходит, когда двигается любая костяшка, то это соответствует транспозиции, т.е. четность перестановки наоборот меняется после каждого шага, а не сохраняется. Вот это "наоборот" должно было мне сразу подсказать правильное решение (но не подсказало, потому что я тормоз). Если "наоборот" меняется после каждого шага, от этого легко придти к чему-то, что сохраняется после каждого шага; например, надо добавить что-то еще, что тоже меняется после каждого шага. А это, например, четность положения пустой клетки. Вот и все. [1]
[1] Поправка благодаря анониму в комментах: не "четность положения пустой клетки", к-я двигается напр. с 4 на 8, а скажем "четность сумм координат пустой клетки", которая действительно меняется после каждого шага.
