Главное > Общение
Задачки по терверу
mutsera Lord Dregas Volar:
Возьмём набор для игры в "пятнашки", вынем все фишки, перемешаем и случайным образом поставим обратно. С какой вероятностью получится расстановка, которую можно решить, передвигая фишки по правилам?
kuuff:
0.5
Если взять всё множество возможных перестановок, записать группу допустимых преобразований (т.е. переходов от перестановки к перестановке), то эта группа разбивает множество перестановок на две равные части. Ну, я так сходу не проделаю все эти выкладки, но я как-то давно писал эту игру в компьютерном исполнении, мне хотелось научится определять "правильность" перестановки заранее, сразу после случайной генерации, плюс мне были интересны применения теории групп. И я помню, что множество перестановок в конечном итоге разбилось на две равные части, что собственно было формальным доказательством того, что некоторые расклады неразрешимы.
Я думаю, что если порыскать в гугле, можно найти доказательство существования неправильных позиций, и скорее всего там этот результат равномощности двух подмножеств перестановок вылезает как побочный эффект. Так же как он вылез у меня.
А, кстати, это же очевидно. Если принять как факт то, что перестановка 1,2,3...13,15,14 неразрешима, и что все другие неразрешимые перестановки сводимы к этой, то можно рассмотреть все перестановки которые можно получить из 1,2,3...,15,14, нарисовать их в виде графа, где вершинами будут перестановки, а рёбра будут соединять те перестановки, между которыми можно перейти одним движением. А теперь возьмём и во всех вершинах графа поменяем местами 15 и 14. Очевидно и несложно доказать, что получившийся граф будет равен графу, который мы могли бы построить, если бы мы исходно взяли перестановку 1,2....,13,14,15 и строили бы граф из неё движениями. А если графы равны, значит количество вершин в них равно. И суммарно вершины двух графов покрывают всё множество возможных перестановок.
Немного сумбурное изложение, но если оно слишком сумбурно, я могу это изложить более формально и связно.
Навигация
Перейти к полной версии