Если кто играл в братьев пилотов, то помнят там холодильник был с 16-ю ручками — 4 ряда по 4 ручки в ряду. Ручки имели два положения — вертикальное и горизонтальное.
Надо было открыть холодильник, поворачивая ручки. Открывался он, если все ручки принимали вертикальное положение (или горизонтальное, не помню).
Но сделать это было не так просто, так как при повороте ручки, одновременно поворачивались все ручки в том же ряду и столбце.
Помню, когда потыкался пару минут в ручки, понял, что это пустая трата времени и решил найти алгоритм. После нескольких раздумий на бумаге алгоритм нарисовался.
Собственно предлагаю задачу (если такая уже была, извиняйте) — найти алгоритм взлома холодильника.
Так же можно обобщить алгоритм на случай NхN ручек.
Для наглядности еще программку прилагаю — там вместо ручек — квадратики. Белый означает закрыто, черный — открыто. Надо добиться, что все квадратики были черными.
PS. Писал, писал, потом решил поискать на форуме, оказалось было, но в КУ. Тогда предлагаю другую задачу — показать решение в общем виде аналитически. Например, если при повороте ручки поворачиваются все в той же диагонали.
Здравствуйте, ДимДимыч, Вы писали:
ДД>Здравствуйте, Spiceman, Вы писали:
S>>PS. Писал, писал, потом решил поискать на форуме, оказалось было, но в КУ.
ДД>Здесь же
Назвали сейфом, потому и не нашел.
Но аналитического решения там не было приведено. Было только упоминание
А аналитически можно:
1. доказать/опровергнуть, что задача имеет решение для исходного состояния ручек,
2. получить решение для любого правила (например, если поворачиваются ручки в том же столбце/строке или, если поворачиваются ручки в той же диагонали) и для любого размера матрицы.
Здравствуйте, Spiceman, Вы писали:
S>Здравствуйте.
S>Если кто играл в братьев пилотов, то помнят там холодильник был с 16-ю ручками — 4 ряда по 4 ручки в ряду. Ручки имели два положения — вертикальное и горизонтальное. S>Надо было открыть холодильник, поворачивая ручки. Открывался он, если все ручки принимали вертикальное положение (или горизонтальное, не помню). S>Но сделать это было не так просто, так как при повороте ручки, одновременно поворачивались все ручки в том же ряду и столбце.
S>Помню, когда потыкался пару минут в ручки, понял, что это пустая трата времени и решил найти алгоритм. После нескольких раздумий на бумаге алгоритм нарисовался.
S>Собственно предлагаю задачу (если такая уже была, извиняйте) — найти алгоритм взлома холодильника.
S>Так же можно обобщить алгоритм на случай NхN ручек.
S>Для наглядности еще программку прилагаю — там вместо ручек — квадратики. Белый означает закрыто, черный — открыто. Надо добиться, что все квадратики были черными.
S>PS. Писал, писал, потом решил поискать на форуме, оказалось было, но в КУ. Тогда предлагаю другую задачу — показать решение в общем виде аналитически. Например, если при повороте ручки поворачиваются все в той же диагонали.
Заведем другую матрицу 4х4 и для каждой клетки будем хранить там 1, если число единичек в строке и столбце этой клетки в исходной матрице нечетно, иначе храним 0.
Например, если исходная матрица
0000
0100
0010
0000
то вторая матрица
0110
1101
1011
0110
Заметим, что вторая матрица состоит из всех нулей тогда и только тогда, когда исходная матрица состоит из всех нулей. Кроме того, самое интересное, что изменение элементов в исходной матрице по описанному в условии правилу эквивалентно изменению просто одной клетки во второй матрице. А значит, для того, чтобы получить нулевую первую матрицу, нам надо обратить единичные клетки второй матрицы.
Другими словами, построенная таким образом вторая матрица просто показывает, какие рычаги надо покрутить. И все!
На практике, при игре, например, надо просто найти первую попавшуюся клетку, у которой число неправильно стоящих рычагов в одной с ней строке и столбце нечетно, и повернуть этот рычаг. Повторять пока не сойдется.
Здравствуйте, vadimcher, Вы писали:
V>Заведем другую матрицу 4х4 и для каждой клетки будем хранить там 1, если число единичек в строке и столбце этой клетки в исходной матрице нечетно, иначе храним 0.
Мне в свое время чтобы до этого дойти пришлось несколько листов бумаги исписать.
V>Другими словами, построенная таким образом вторая матрица просто показывает, какие рычаги надо покрутить. И все!
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, Spiceman, Вы писали:
S>>Дайте мне аналитическое решение в общем виде
V_>В общем виде только решать систему линейных уравнений по модулю два, по-моему.
Вобщем да. Просто тут никто еще не написал, как выглядит эта система.
PS. Я так понял, что эту задачу тут уже все перерешали. Ну и ладно.
Здравствуйте, Spiceman, Вы писали:
S>Здравствуйте.
S>Если кто играл в братьев пилотов, то помнят там холодильник был с 16-ю ручками — 4 ряда по 4 ручки в ряду. Ручки имели два положения — вертикальное и горизонтальное. S>Надо было открыть холодильник, поворачивая ручки. Открывался он, если все ручки принимали вертикальное положение (или горизонтальное, не помню). S>Но сделать это было не так просто, так как при повороте ручки, одновременно поворачивались все ручки в том же ряду и столбце.
S>Помню, когда потыкался пару минут в ручки, понял, что это пустая трата времени и решил найти алгоритм. После нескольких раздумий на бумаге алгоритм нарисовался.
S>Собственно предлагаю задачу (если такая уже была, извиняйте) — найти алгоритм взлома холодильника.
S>Так же можно обобщить алгоритм на случай NхN ручек.
S>Для наглядности еще программку прилагаю — там вместо ручек — квадратики. Белый означает закрыто, черный — открыто. Надо добиться, что все квадратики были черными.
S>PS. Писал, писал, потом решил поискать на форуме, оказалось было, но в КУ. Тогда предлагаю другую задачу — показать решение в общем виде аналитически. Например, если при повороте ручки поворачиваются все в той же диагонали.
В ICQ есть модифицированная версия игры. В нее можно поиграть, например, здесь. Задача -- заткнуть всех соседей. (В принципе, их можно заткнуть, нажав sound off. )
Понятно, что максимальное число кликов, которые требуются -- 8.
Пример. Если исходная комбинация
Обязательно бахнем! И не раз. Весь мир в труху! Но потом. (ДМБ)
)