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

[avva]

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

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

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

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

Comments

[cema.livejournal.com]

Полезное размышление для обучения студентов (и старших школьников).

[не совсем об этом, но напомнило]

[utnapishti.livejournal.com]

Вот случай, когда "умножить на -1" приводит к разочарованию:

Допустим, студенты уже привыкли к тому, что если подмножество векторного пространства определяется условием, в котором есть знак неравенства - то это, как правило, не подпространство. Обычно в каком-нибудь из первых примеров - вроде {(x,y): x <= y} - как раз умножение на -1 показывает, что нет замкнутости относительно умножения на скаляр. После этого даёшь им пример (в R^2): W={(x,y): xy => 0}. Они сразу кричат: знаем, знаем! Надо умножить на отрицательный скаляр! А потом ищут пример, и - опаньки!..

Re: [не совсем об этом, но напомнило]

[avva.livejournal.com]

:) забавный пример.

Re: [не совсем об этом, но напомнило]

[utnapishti.livejournal.com]

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

Re: [не совсем об этом, но напомнило]

[avva.livejournal.com]

ты видел кстати учебник акслера Linear Algebra Done Right? Мне понравился его подход, интересно узнать твое мнение.

Re: [не совсем об этом, но напомнило]

[utnapishti.livejournal.com]

Раньше не видел - у него на сайте есть несколько глав - первое впечатление вполне хорошее, но хотелось бы увидеть более ранние главы: собственно, про векторные пространства и про линейные трансформации.

Re: [не совсем об этом, но напомнило]

[alexey-rom.livejournal.com]

Проблема в том, что мой стандартный пример с неравенством это {(x,y): sqrt(x^2 + y^2) <= 1}. Тут уже не помогает :)

Re: [не совсем об этом, но напомнило]

[utnapishti.livejournal.com]

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

Re: [не совсем об этом, но напомнило]

[alexey-rom.livejournal.com]

Да.

[(Anonymous)]

1. Пример с пятнашками не связан, если вдуматься еще чуть-чуть, с первоначальными рассуждениями о кандидатах.
2. Чтобы приведенное рассуждение о пятнашках стало верным надо рассматривать четность положения пустого места вовсе не относительно "очевидной нумерации", а относительно нумерации змейкой. Поскольку в "очевидной нумерации" пустое место замечательно скачет с 16-го места на 12-е.

Такие дела.

[avva.livejournal.com]

1. Он просто более сложен, но суть та же, по-моему.
2. Ага, спасибо за поправку. Я вообще-то подумал о четности L_1-расстояния от пустого места до 16-го (т.е. суммы расстояний по горизонтали и по вертикали), но не хотел это долго объяснять, и показалось, что четность места дает то же самое. А не совсем.

[avva.livejournal.com]

Изменил на четность сумм координат, см. в записи. Спасибо еще раз.