temp3 пишет:

короче решение

1) любые два нажатия на кнопку коммутируют
ясно что коммутируют любые нажатия на соседние кнопки *проверяется вручную*
а значит коммутируют вообще любые два нажатия
а отсюда значит что в процессе ни одна кнопка не будет нажата дважды
2) строится система m*n линейных уравнений над полем вычетов по модулю два
на каждую кнопку одна переменная, равная либо 0 - кнопка не нажимается, либо 1 - кнопка нажимается
каждое уравнение имеет вид - x_ij+x_(i-1)j+x_i(j-1)+x_(i+1)j+x_i(j+1)=1 где 0<i<N+1 0<j<M+1 - координаты кнопки, если кнопка краевая этих членов в уравнении просто нет

дальше система решается и получаем набор кнопок которые необходимо нажать
в зависимости от M и N система будет либо иметь либо не иметь решения

До этого думаю тут много кто догадался, только вот очень уж робское решение получается, неконструктивное, трудоемкость факториальная, а хочется хотя бы полиномиальную.

Откуда факториальное решение, я не совсем понимаю? Решить систему уравнений - это факториальная трудоемкость? ))

temp3 пишет:

srez пишет:

для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?

(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенно

о, ну значиццо n^6 решение предлагаешь фактически. а теперь давай своими итерационными методами реши задачку для m=n=1E20. *)

для итерационных методов m=n=1E20 данная система уравнений будет решена за что-то типа O(1E80), а то и значительно быстрее, ведь поле решений очень и очень хорошее
думаю даже одного шага итерации будет достаточно в данном случае

srez пишет:

temp3 пишет:

ну программку-то ты сможешь написать?

для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?

(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенно

о, ну значиццо n^6 решение предлагаешь фактически. а теперь давай своими итерационными методами реши задачку для m=n=1E20. *)

temp3 пишет:

srez пишет:

Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)

ну программку-то ты сможешь написать?

для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?

(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенно

srez пишет:

temp3 пишет:

я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемо

в таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю

Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)

ну программку-то ты сможешь написать?

для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?

temp3 пишет:

srez пишет:

Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.

я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемо

в таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю

Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)

ну программку-то ты сможешь написать?

Да и все же я не понял, собственно ответ на задачу должен отвечать на вопрос задачи. Напомню вопрос.
"если полез иначально чёрное, существует ли общий алгоритм по которому можно всё поле инверсировать?
какие ограничения на M и N?"
Как твое решение отвечает на эти вопросы я ниасилил.

пишем простейшую программку на сях, вводим для данные m и n
получаем координаты кнопок которые надо нажать
если матрица не разрешима над полем z2 - значит данное поле инверсировать нельзя

srez пишет:

temp3 пишет:

ну попробуй
я пока над этим не думал

Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.

я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемо

в таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю

Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)

temp3 пишет:

ну попробуй
я пока над этим не думал

Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.

я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемо

в таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю

ну попробуй
я пока над этим не думал

Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.

ответ:

http://www.socionica.com/viewtopic.php? … 70#p218770

Обосновать того, что ответ всегда есть?

AE0....0 = 1
EAE0...0 = 1
0EAE0..0 = 1
0...0EAE = 1
0....0EA = 1

где E - еденичные блоки размера mxm или nxn в зависимости от введёной нумерации, количество блоков соотв. наоборот n или m
A - трёхдиагональная матрица с еденицами на 3ёх центральных диагоналях

http://www.socionica.com/viewtopic.php? … 70#p218770