Подсчет количества цифр в записи числа

[maxal]

Alik писал(а):

Необходимо найти максимальное число различных $x_{p+1}$ так чтобы однажды найденные $x_1, x_2, \dots, x_p$ были одинаковыми. В случае нулевых столбцов лишь одна из перестановок даст требуемый $x_i$.

Долго думал над этими фразами, но так до конца и не понял.
Попробую перевести первую фразу как я ее понял:
нужно найти такие числа $x_1,\dots,x_p\in\mathbb{R}$ и множество чисел $X\subset\mathbb{R}$, чтобы для любого $y\in X$ набор числа $x_1,\dots,x_p$ и $x_{p+1}=y$ удовлетворяли хотя бы одному уравнению из системы, заданной матрицей $M$. При этом необходимо, чтобы $X$ содержало как можно больше чисел. Так?
А вторая фраза так и осталась загадкой.

[Alik]

Уже сбился со счету какой будет дубль, наверное не последний
Дано:
Модифицированная матрица $M$ полного троичного разложения размером $3^p\times (p+1)$, где последний столбец $p+1$ состоит из $-1$. Cоставим исходную систему уравнений вида $MX=B$ и oпределим строки $M$, где первая ненулевая цифра будет $-1$. Столбец свободных членов $B$ содержит $-1$ ровно в этих же строках, на остальных местах стоят нули, вектор неизвестных $X=x_1, x_2, \dots, x_{p+1}$. Для любого $p\in\mathbb{N}$ рассмотрим подсистемы уравнений с двумя неизвестными $x_i, x_{p+1}$ составленные из исходной, к примеру

$$ \left[\begin{array}{cccc} -1&0&0&-1\\ 1&0&0&-1\\ \end{array} \right] \times \left[\begin{array}{cccc} x_1\\ x_{p+1}\\ \end{array} \right] = \left[\begin{array}{cccc} -1\\ 0\\ \end{array} \right] $$

Очевидно, что таких подсистем можно составить $p$ штук, а их решением будет пара $x_i=1/2, x_{p+1}=1/2$. Теперь зафиксируем индекс $i$, допустим $i=1$ и рассмотрим подсистемы уравнений с тремя неизвестными $x_1,x_i, x_{p+1}$, при условии что $x_1=1/2$.
Повторяя подобную процедуру найти общую формулу для $x_1, x_2, \dots, x_p$ и максимальное количество различных $x_{p+1}$.

[Alik]

Цитата:

Впрочем, независимо от поля могу дать такую нижнюю оценку на число разрешимых систем
$L(p)$ для $p=1,2,\dots,5$:

2, 11, 531, 134218778, 2417851639229258617849376

А как может общее число составленных (разрешимых) уравнений быть больше количества строк в матрице, ведь $3^5=243$?

Цитата:

...а если требовать, чтобы были различны, - то это совсем другое (сводится просто к подсчету различных $x_{p+1}$)

maxal, если сделать лирическое отступление и подсчитать количество нетривиальных (ненулевых) решений и различных $x_{p+1}$ сколько их действительно будет?

[maxal]

Alik писал(а):

Цитата:

Впрочем, независимо от поля могу дать такую нижнюю оценку на число разрешимых систем
$L(p)$ для $p=1,2,\dots,5$:

2, 11, 531, 134218778, 2417851639229258617849376

А как может общее число составленных (разрешимых) уравнений быть больше количества строк в матрице, ведь $3^5=243$?

Ну так мы же подсчитываем не отдельные уравнения, а их системы, количество которых может быть вплоть до $2^{3^5}$.
А вообще я про вашу задачу помню, просто времени сейчас нет. Но как только - так сразу

[Alik]

maxal, а ваша формула она для систем уравнений, где $x_1, x_2, \dots, x_{p+1}$ могут быть и положительными и отрицательными или только положительными?

[Alik]

maxal, хоть этот топик медленно уходит за горизонт, я все еще надеюсь на вашу помощь...

[maxal]

Alik писал(а):

Модифицированная матрица $M$ полного троичного разложения размером $3^p\times (p+1)$, где последний столбец $p+1$ состоит из $-1$. Cоставим исходную систему уравнений вида $MX=B$ и oпределим строки $M$, где первая ненулевая цифра будет $-1$. Столбец свободных членов $B$ содержит $-1$ ровно в этих же строках, на остальных местах стоят нули, вектор неизвестных $X=x_1, x_2, \dots, x_{p+1}$. Для любого $p\in\mathbb{N}$ рассмотрим подсистемы уравнений с двумя неизвестными $x_i, x_{p+1}$ составленные из исходной, к примеру

$$ \left[\begin{array}{cccc} -1&0&0&-1\\ 1&0&0&-1\\ \end{array} \right] \times \left[\begin{array}{cccc} x_1\\ x_{p+1}\\ \end{array} \right] = \left[\begin{array}{cccc} -1\\ 0\\ \end{array} \right] $$

Очевидно, что таких подсистем можно составить $p$ штук, а их решением будет пара $x_i=1/2, x_{p+1}=1/2$.

Уже лучше, но...
Матричная запись у вас неверная. Здесь, наверное, лучше записывать в виде систем уравнений:
$\begin{cases} -1\cdot x_1 - 1\cdot x_{p+1} &= -1\\ 1\cdot x_1 - 1\cdot x_{p+1} &= 0\end{cases}$

Alik писал(а):

Теперь зафиксируем индекс $i$, допустим $i=1$ и рассмотрим подсистемы уравнений с тремя неизвестными $x_1,x_i, x_{p+1}$, при условии что $x_1=1/2$.

Все такие подсистемы имеют вид (полагаем $i=2$):
$\begin{cases} -1\cdot x_1 - 1\cdot x_2 - 1\cdot x_{p+1} &= -1\\ -1\cdot x_1 + 1\cdot x_2 - 1\cdot x_{p+1} &= -1\\ 1\cdot x_1 - 1\cdot x_2 - 1\cdot x_{p+1} &= 0\\ 1\cdot x_1 + 1\cdot x_2 - 1\cdot x_{p+1} &= 0\end{cases}$
и при $x_1=1/2$ сводится к:
$\begin{cases} 1\cdot x_2 - 1\cdot x_{p+1} &= -1/2\\ 1\cdot x_2 - 1\cdot x_{p+1} &= -1/2\end{cases}$
Откуда $x_2=0$ и аналогично и все последующие $x_3=x_4=\dots=x_p=0$ и $x_{p+1}=1/2$.

Alik писал(а):

Повторяя подобную процедуру найти общую формулу для $x_1, x_2, \dots, x_p$ и максимальное количество различных $x_{p+1}$.

Описанная процедура приводит к однозначному ответу, указанному выше.

[Alik]

Здравствуйте, сразу оговорюсь, что эта задачка в том или ином виде формулировалась здесь http://dxdy.ru/topic11598.html. Из прошлой версии мало что можно было понять, поэтому новая, переосмысленная формулировка звучит так:
Пусть имеется матрица $A$ размером $27\times 4$, которая представляет собой троичную запись чисел от $-26$ до $26$ с добавлением последнего столбца из $-1$. Имеется также вектор неизвестных $X=x_1, \dots, x_4 и вектор свободных членов $B$, который формируется по следующему принципу. Определим строки $A$, где первая ненулевая цифра будет $-1$, вектор $B$ содержит $-1$ ровно в этих же строках, на остальных местах стоят нули.
Пусть количество неизвестных $i=1 \dots 4, для каждого $i$ составляется некоторое количество $n_i$ систем уравнений вида $a\times x=b$. Матрица коэффициентов $a$ набирается из строк матрицы $A$ с отбрасыванием лишних нулей. Вектор $b$ состоит из элементов вектора $B$ соответствующих этим строкам.
Обязательное условие: $x_4$ должен присутствовать в системе. В большинстве случаев число уравнений будет превышать число неизвестных (избыточные системы).
Найти суммарное количество систем уравнений

$$N=\sum_{i=1}^{4} n_i $$

проверить какие из этих систем имеют единственное решение (теорема Кронекера-Капелли), для каких систем найденное значение $x_4$ дублируется и сколько раз.

\[ A = \left[ {\begin{array}{*{20}c} \begin{array}{r} {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ \end{array} & \begin{array}{r} {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{1}} \\ {\rm{1}} \\ \end{array} & \begin{array}{r} {\rm{ - 1}} \\ {\rm{ 0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{ 0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{ 0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{ 0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{1}} \\ \end{array} \\ \end{array}\begin{array}{*{20}c} {} & \begin{array}{r} {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ \end{array} \\ \end{array}} \right]\begin{array}{*{20}c} {} & {X = } \\ \end{array}\left[ \begin{array}{r} {\rm{x}}_1 \\ {\rm{x}}_2 \\ {\rm{x}}_3 \\ {\rm{x}}_4 \\ \end{array} \right]\begin{array}{*{20}c} {} & {B = } \\ \end{array}\left[ \begin{array}{r} {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{ - 1}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ {\rm{0}} \\ \end{array} \right] \]

В качестве примера рассмотрим простейший случай $i=2$, неизвестные $x_1,x_2$ не используются:
$\begin{cases} -1\cdot x_3 - 1\cdot x_4 &= -1\\ 1\cdot x_3 - 1\cdot x_4 &= 0\end{cases}$
Решение: $x_3=x_4=1/2$
Для избыточной системы с $i=4$

\[ \left\{ \begin{array}{c} {\rm{ 1}} \cdot x_1 {\rm{ - 1}} \cdot x_2 {\rm{ - 1}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = - 1}} \\ {\rm{ - 1}} \cdot x_1 {\rm{ + 0}} \cdot x_2 {\rm{ - 1}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = - 1}} \\ {\rm{ - 1}} \cdot x_1 {\rm{ - 1}} \cdot x_2 {\rm{ + 0}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = - 1}} \\ {\rm{ 1}} \cdot x_1 {\rm{ + 1}} \cdot x_2 {\rm{ + 0}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = 0}} \\ {\rm{ 1}} \cdot x_1 {\rm{ + 0}} \cdot x_2 {\rm{ + 1}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = 0}} \\ {\rm{ - 1}} \cdot x_1 {\rm{ + 1}} \cdot x_2 {\rm{ + 1}} \cdot x_3 {\rm{ - 1}} \cdot x_4 {\rm{ = 0}} \\ \end{array} \right. \]

решением будет $x_1=1/6, x_2=x_3=1/3$, значение $x_4=1/2$ совпадает с предыдущим

[maxal]

Alik, предупреждение за дублирование тем!

Добавлено спустя 31 минуту 21 секунду:

Re: Количество систем уравнений имеющих решение

Alik писал(а):

Пусть количество неизвестных $i=1 \dots 4, для каждого $i$ составляется некоторое количество $n_i$ систем уравнений вида $a\times x=b$. Матрица коэффициентов $a$ набирается из строк матрицы $A$ с отбрасыванием лишних нулей. Вектор $b$ состоит из элементов вектора $B$ соответствующих этим строкам.
Обязательное условие: $x_4$ должен присутствовать в системе. В большинстве случаев число уравнений будет превышать число неизвестных (избыточные системы).
Найти суммарное количество систем уравнений

$$N=\sum_{i=1}^{4} n_i $$

проверить какие из этих систем имеют единственное решение (теорема Кронекера-Капелли), для каких систем найденное значение $x_4$ дублируется и сколько раз.

Снова непонятно пишите. Попробую переформулировать, как это понял я, а заодно и вычислить $n_i$.
Пусть $p=3$ (для совместимости с предыдущим обсуждением). Пусть $i$ некоторое число от 1 до $p+1$. Выберем какие-то $i-1$ переменных из $x_1, \dots, x_p$, а также переменную $x_{p+1}$ (число способов такого выбора: ${p\choose i-1}$), а в системе рассмотрим все строки, в которых невыбранным переменным соотвествуют нулевые коэффициенты (количество таких строк равно $3^{i-1}$), а из них составим всевозможные системы уравнений (выбирая различные подмножества из "хороших" строк, их $2^{3^{i-1}}$).
Таким образом,

$$n_i(p) = {p\choose i-1} 2^{3^{i-1}}$$

и

$$N(p) = \sum_{i=1}^{p+1} {p\choose i-1} 2^{3^{i-1}}.$$

Для $p=3$ получаем:
$n_1 = 2,\quad n_2 = 24,\quad n_3 = 1536,\quad n_4 = 134217728$
и
$N=134219290.$

Похоже на правду?

P.S. Построение систем надо понимать в совокупности в выбранным набором переменных. Так, например, для каждого выбранного набора переменных у нас среди прочих будет пустая система (состоящая из нулевого числа уравнений), и формально говоря, эти пустые системы будут различны, так как решать их надо относительно разных наборов переменных.

[Alik]

maxal писал(а):

Пусть $p=3$ (для совместимости с предыдущим обсуждением). Пусть $i$ некоторое число от 1 до $p+1$. Выберем какие-то $i-1$ переменных из $x_1, \dots, x_p$, а также переменную $x_{p+1}$ (число способов такого выбора: ${p\choose i-1}$)

до сих пор понятно, три уточняющих вопроса:
1) почему количество строк набранных из матрицы $A$ в которых невыбранным переменным соотвествуют нулевые коэффициенты равно $3^{i-1}$?
2) что такое "хорошие строки"? Я так понял, что это те же самые строки из предыдущего пункта.
3) почему количество систем уравнений, составленных из этих строк равно $2^{3^{i-1}}$

Вы конечно же правы в том, что я не до конца изложил условия

maxal писал(а):

Снова непонятно пишите. Попробую переформулировать, как это понял я, а заодно и вычислить $n_i$.

Поэтому ответ

maxal писал(а):

Для $p=3$ получаем:
$n_1 = 2,\quad n_2 = 24,\quad n_3 = 1536,\quad n_4 = 134217728$ и $N=134219290.$

получился "завышенный", т.е учитываются все перестановки. Поясню на двух предыдущих примерах.
В первом $i=2$, $x_1,x_2$ не используются и решение: $x_3=1/2$, $x4=1/2$. Мне абсолютно не важно кто будет выступать в качестве $x_3=1/2$, будь это $x_2$ или $x_1$
результат $x_4=1/2$ не изменится, только неиспользуемые переменные будут под другими именами. Таким образом, для $i=2$ общее число систем уравнений равно трем, а интересует только одна, у которой в решение входит скажем старший разряд (первый столбец матрицы $A$), т.е $x_1=1/2$, $x_4=1/2$
Тоже самое во втором примере, где $i=4$ и решение $x_1=1/6, x_2=x_3=1/3$, $x_4=1/2$, аналогичные этому случаи: $x_2=1/6, x_1=x_3=1/3$ или $x_3=1/6, x_1=x_2=1/3$ не учитываются,

[maxal]

Alik писал(а):

maxal писал(а):

Пусть $p=3$ (для совместимости с предыдущим обсуждением). Пусть $i$ некоторое число от 1 до $p+1$. Выберем какие-то $i-1$ переменных из $x_1, \dots, x_p$, а также переменную $x_{p+1}$ (число способов такого выбора: ${p\choose i-1}$)

до сих пор понятно, три уточняющих вопроса:
1) почему количество строк набранных из матрицы $A$ в которых невыбранным переменным соотвествуют нулевые коэффициенты равно $3^{i-1}$?
2) что такое "хорошие строки"? Я так понял, что это те же самые строки из предыдущего пункта.
3) почему количество систем уравнений, составленных из этих строк равно $2^{3^{i-1}}$

1) Потому что, мы можем варьировать коэффициенты только при $i-1$ выбранных переменных (а значение коэффициента при $x_{p+1}$ предопределено), и каждый коэффициент может принимать независимо три различных значения: $-1, 0, 1$. Так и получается $3^{i-1}$.
2) Да.
3) Количество подмножеств $k$-элементного множества равно $2^k$. В нашем случае множеством выступает множество "хороших" строк, а их число равно $3^{i-1}$.

Alik писал(а):

Поэтому ответ

maxal писал(а):

Для $p=3$ получаем:
$n_1 = 2,\quad n_2 = 24,\quad n_3 = 1536,\quad n_4 = 134217728$ и $N=134219290.$

получился "завышенный", т.е учитываются все перестановки. Поясню на двух предыдущих примерах.
В первом $i=2$, $x_1,x_2$ не используются и решение: $x_3=1/2$, $x4=1/2$. Мне абсолютно не важно кто будет выступать в качестве $x_3=1/2$, будь это $x_2$ или $x_1$
результат $x_4=1/2$ не изменится, только неиспользуемые переменные будут под другими именами. Таким образом, для $i=2$ общее число систем уравнений равно трем, а интересует только одна, у которой в решение входит скажем старший разряд (первый столбец матрицы $A$), т.е $x_1=1/2$, $x_4=1/2$
Тоже самое во втором примере, где $i=4$ и решение $x_1=1/6, x_2=x_3=1/3$, $x_4=1/2$, аналогичные этому случаи: $x_2=1/6, x_1=x_3=1/3$ или $x_3=1/6, x_1=x_2=1/3$ не учитываются,

Проблема в том, что переменные тут, вообще говоря, не являются симметричными в виду не совсем "коррелированного" с ними столбца свободных членов. То есть, например, вам неважно $x_1$ или $x_3$ присутствует в системе, но уравнения могут качественно зависеть от того, какая именно переменная присутствует - сравните:
$1\cdot x_1 - 1\cdot x_2 -1\cdot x_4 = 0$
или
$1\cdot x_3 - 1\cdot x_2 -1\cdot x_4 = -1$
Если учитывать возможную симметрию систем, то нужно отдельно рассматривать верхнюю и нижнюю часть системы, и выражения для $n_i$ тут будут сложнее. Подробнее напишу чуть позже.

Добавлено спустя 26 минут 53 секунды:

На самом деле учесть возможную симметрию можно так: считать, что выбранные переменные всегда идут по порядку (за возможным исключением $x_{p+1}$). Дело в том, что коэффициенты перед выбранной переменной с наименьшим индексом, пусть $x_s$, определяют свободные члены, а все остальные переменные за счет симметрии можно "подвинуть" вплотную к $x_s$.
Таким образом, в предыдущем выражении для $n_i$ нужно всего лишь заменить ${p\choose i-1}$ на $p+2-i$ для $i>1$ (т.е. число способов выбрать $i-1$ последовательных переменных из $p$ штук) и $1$ для $i=1$:

$$n_1(p) = 2$$

(пустая система и система, состоящая из одного уравнения $-1\cdot x_{p+1} = -1$);

$$n_i(p) = (p+2-i) 2^{3^{i-1}}$$

при $i\geq 2$;
и

$$N(p) = 2 + \sum_{i=2}^{p+1} (p+2-i) 2^{3^{i-1}}.$$

Для $p=3$ получаем:
$n_1 = 2,\quad n_2 = 24,\quad n_3 = 1024,\quad n_4 = 134217728$
и
$N=134218778.$

[Alik]

Снова уточнение условий на примере: дело в том, что для трех переменных матрица $A$ содержит повторяющиеся строки (допустим $-1 -1 -1$ три раза), это говорит о том, что для случая $i=3$ нужно рассматривать сокращенную матрицу $A'$ размером $9\times (2+1)$ и соответствующий вектор $B'$.
Таким образом рассуждения

Цитата:

1) Почему количество строк набранных из матрицы $A$ в которых невыбранным переменным соотвествуют нулевые коэффициенты равно $3^{i-1}$? Потому что, мы можем варьировать коэффициенты только при $i-1$ выбранных переменных (а значение коэффициента при $x_{p+1}$ предопределено), и каждый коэффициент может принимать независимо три различных значения: $-1, 0, 1$.
2) Что такое "хорошие строки"? Я так понял, что это те же самые строки из предыдущего пункта. Да.
3) Почему количество систем уравнений, составленных из этих строк равно $2^{3^{i-1}}$? Количество подмножеств $k$-элементного множества равно $2^k$. В нашем случае множеством выступает множество "хороших" строк, а их число равно $3^{i-1}$.

нужно подкорректировать

[maxal]

Alik писал(а):

Снова уточнение условий на примере: дело в том, что для трех переменных матрица $A$ содержит повторяющиеся строки (допустим $-1 -1 -1$ три раза), это говорит о том, что для случая $i=3$ нужно рассматривать сокращенную матрицу $A'$ размером $9\times (2+1)$ и соответствующий вектор $B'$.

Какую конкретно матрицу $A'$ и вектор $B'$ вы имеете в виду?

[Alik]

Не судите строго, просто MathType под рукой нет (делаю в него paste из MATLAB).
В матрице ниже три первых столбика - это матрица A', последний столбик - вектор B'

    -1    -1    -1    -1
     0    -1    -1    -1
     1    -1    -1    -1
    -1     0    -1    -1
     0     0    -1    -1
     1     0    -1     0
    -1     1    -1     0
     0     1    -1     0
     1     1    -1     0

[Alik]

maxal, я тут еще немножко поигрался с MATLAB, в результате для матрицы $A$ размером $27\times 4$ нашлось всего 28 систем уравнений имеющих решение. Подсчитывались они методом подбора переменных $x_1, \dots, x_3$ так чтобы $x_4$ принимал различные значения. То, что меня заинтриговало и чему нет аналитического объяснения - это то, что множество $x_4$ в точности соответствует последовательности Фарея 8-го порядка $F_8$
http://en.wikipedia.org/wiki/Farey_sequence