С логически матрици?

[Гост]

Здравейте.
Две задачки ме мъчат напоследък.
--------Условие-на-задача-1.--------
Ако X и Y са матрици, с x(i,j) и y(i,j) ще означавам елементите съответно на X и Y в ред i и колона j, за някои цели положителни числа i и j. Матрица наричаме булева, ако всеки неин елемент е или 0, или 1. Една булева матрица ще наричаме плоска, ако в някой неин ред (без значение кой) всички елементи са 0, а всички останали са 1. Означаваме с U множеството от всички квадратни булеви матрици. Разглеждаме функцията f, f:U->U, която е определена по следния начин.
На всяка квадратна булева матрица X от ред n образът и f(X) е от същия ред. Определяме f(X) чрез описване на алгоритъма, по който се намира. Записваме матрицата Y=(X|f(X)) която е с размер n на 2n. Пресмятаме f(X) последователно по колони като почваме от най-лявата и стигаме до най-дясната. За колона с номер i на Y (n+1≤i≤2n) определяме множеството от елементи D(i) като D(i)={y(j,i-j)|1≤j≤n}. Обяснено с думи, множеството D(i) за колона номер i се състои от тези n елемента, разположени по линия, успоредна на вторичния диагонал на X, започваща от най-горния елемент на предишната колона (колоната непосредствено вляво). (За колона n+1 на Y, т.е. първа колона на f(X), D(i) е самият вторичен диагонал на X.) Ако D(i) не съдържа 0, в колона i поставяме всички елементи =0. Ако D(i) съдържа два или повече на брой 0, в колона i поставяме всички елементи =1. Ако D(i) съдържа един брой 0, в колона i поставяме в реда, съдържащ 0, числото 0, а всички други елементи =1.
Да се намерят всички цели числа n (n≥2), за които съществува булева матрица X от ред n, която не е плоска и X=f(X).
-------Край-на-условие-на-задача-1.--------
И още една задача (свързана с горната).
--------Условие-на-задача-2.--------
Нека X е дадена булева матрица от ред n. Нека Y е безкрайна булева матрица с редове, индексирани от 1 до n и колони, индексирани от 1 до +безкрайност. Първите n колони на Y (най-левите) съвпадат с X. Всяка следваща колона се образува от предишните n колони по същото правило, по което се пресмятат колоните на f(X) в задача 1. Матрицата Y, образувана така от X, ще означавам с g(X). Не е трудно да се установи, че за всяка X g(X) е периодична. Т.е. има последователност от k колони, които се повтарят периодично (за някакво цяло k, k≥1) от някакво място нататък след (евентуално) някаква апериодична част. А колко точно е k, колко дълга е апериодичната част и какви са точно стойностите - това зависи от X. Може да се направи компютърна програма, реализираща алгоритъм, който по зададена квадратна булева матрица X чрез последователно изчисление намира дължините на апериодичната част и на периода, както и намира техните стойности. (Не е проблем за мен да направя такава програма.) Интересни са следните въпроси:
1) Възможно ли е да се намерят по някакъв начин предварително без пресмятане на конкретните стойности на елементите на Y (и по-бързо!) дължините на апериодичната част и на периода на Y? Ако няма, могат ли да се намерят някакви горна и долна оценки за тези дължини, които оценки да могат да се пресметнат от X предварително? (Не разглеждаме случая, когато X е плоска, който считаме за тривиален).
2) Ако за конкретно цяло число n търсим булева матрица X от n-ти ред с възможно най-дълга апериодична част на g(X), а също и такава с възможно най дълъг период на g(X), има ли алгоритъм да ги намерим, по-бърз от изчерпващо търсене?
-------Край-на-условие-на-задача-2.--------
Коментар по задача 1. Лесно се установява, че за матрица, удовлетворяваща X=f(X), всяка колона и всяко диагонално множество D(i) съдържат точно по един бр. 0. Също, че всеки ред без най-долния (n-ти) не може да съдържа точно един брой 0. (Т.е. или само единици, или поне два броя нули.) Но следва ли от това обаче, че X непременно е плоска?