Сообщение Re[5]: Еще одна задача про рыцарей от 11.06.2015 12:00
Изменено 11.06.2015 12:01 _DAle_
Здравствуйте, _DAle_, Вы писали:
В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому.
То есть:
1 2 3 4 5 — 1 виток
1 3 5 2 4 — 2 витка
1 5 4 3 2 — 4 витка
Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.
В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому.
То есть:
1 2 3 4 5 — 1 виток
1 3 5 2 4 — 2 витка
1 5 4 3 2 — 4 витка
Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.
Re[5]: Еще одна задача про рыцарей
Здравствуйте, _DAle_, Вы писали:
В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому.
То есть:
1 2 3 4 5 — 1 виток
1 3 5 2 4 — 3 витка
1 5 4 3 2 — 4 витка
Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.
В общем, я понял, за что можно зацепиться..
Рассмотрим количество витков, которые необходимо сделать по рассадке рыцарей, если от 1 двигаться ко 2, от второго к 3, ..., от последнего к первому.
То есть:
1 2 3 4 5 — 1 виток
1 3 5 2 4 — 3 витка
1 5 4 3 2 — 4 витка
Дело в том, что при действующих условия обмен между двумя соседними (даже 1 с последним) не меняет количество витков. Таким образом у нас все перестановки разбиваются на N-1 классов, остается доказать, что имея один вариант с k витками из него можно получить все перестановки из существующего класса.