TAOCP 7.2.2.2 Exercise 107
Let $p=6$, $n=13$, and the first row be x_{1,\bullet} = 1111101111101, so
Section 7.2.2.2: Satisfiability
Exercise 107. ▶ [22] [22] Basket weavers from the Tonga culture of Inhambane, Mozambique, have developed appealing periodic designs called "gipatsi patterns" such as this:
$$\ldots \text{ [gipatsi pattern image] } \ldots$$
(Notice that an ordinary pixel grid has been rotated by $45°$.) Formally speaking, a gipatsi pattern of period $p$ and width $n$ is a $p \times n$ binary matrix $(x_{i,j})$ in which we have
$x_{i,1} = x_{i,n} = 1$ for $1 \le i \le p$. Row $i$ of the matrix is to be shifted right by $i - 1$ places in the actual pattern. The example above has $p = 6$, $n = 13$, and the first row of its matrix is 1111101111101. Such a pattern has row sums $r_i = \sum_{j=1}^{n} x_{i,j}$ for $1 \le i \le p$ and column sums $c_j = \sum_{i=1}^{p} x_{i,j}$ for $1 \le j \le n$, as usual. By analogy with (53), it also has
$$a_d = \sum_{i+j \equiv d \pmod{p}} x_{i,j}, \quad 1 \le d \le p; \qquad b_d = \sum_{2i+j \equiv d \pmod{2p}} x_{i,j}, \quad 1 \le d \le 2p.$$
a) What are the tomographic parameters $r_i$, $c_j$, $a_d$, and $b_d$ in the example pattern? b) Do any other gipatsi patterns have the same parameters?
Verified: no
Solve time: 6m46s
Correct solution
Let $p=6$, $n=13$, and the first row be
$$ x_{1,\bullet} = 1111101111101, $$
so
$$ S={1,2,3,4,5,7,8,9,10,11,13}, \qquad |S|=11. $$
Each row is obtained by a cyclic right shift by $i-1$, hence
$$ x_{i,j}=x_{1,,j-(i-1)\ (\mathrm{mod}\ 13)}. $$
(a) Tomographic parameters
Row sums $r_i$
Each row is a permutation of row 1, so the number of ones is preserved:
$$ r_i = 11, \qquad 1 \le i \le 6. $$
Column sums $c_j$
Fix $j$. The entry $x_{i,j}=1$ iff
$$ j-(i-1)\in S \pmod{13}. $$
Equivalently, as $i$ runs, each column is a cyclic window of length 6 over a fixed 11-element support. Direct counting (or the complement ${6,12}$) gives
$$ (c_1,\dots,c_{13}) = (5,5,5,5,6,5,5,5,5,5,5,5,5), $$
so every column has sum 5 except $j=5$, which has sum 6.
Diagonal sums $a_d$
By definition,
$$ a_d=\sum_{i+j\equiv d\ (\mathrm{mod}\ 6)} x_{i,j}. $$
We rewrite using the shift structure. If $x_{i,j}=1$, then $j=s+i-1\ (\mathrm{mod}\ 13)$ for some $s\in S$. Hence
$$ i+j \equiv i+(s+i-1)=2i+s-1 \pmod{6}. $$
So we count solutions of
$$ 2i+s-1 \equiv d \pmod{6}, \quad 1\le i\le 6,\ s\in S. $$
For fixed $s$, as $i=1,\dots,6$,
$$ 2i \equiv 2,4,0,2,4,0 \pmod{6}, $$
so each of $0,2,4$ occurs exactly twice. Therefore each fixed $s$ contributes:
- $2$ to each of three residue classes
$$ d \equiv s-1,\ s+1,\ s+3 \pmod{6}. $$
Now reduce $S$ modulo 6:
$$ \begin{aligned} S \bmod 6:\quad &1,7,13 \to 1 \ (\text{3 elements}),\ &2,8 \to 2, \quad 3,9 \to 3, \quad 4,10 \to 4, \quad 5,11 \to 5. \end{aligned} $$
Carrying out the induced contributions yields:
$$ a_d = \begin{cases} 14, & d \equiv 0,2,4 \pmod{6},\ 8, & d \equiv 1,3,5 \pmod{6}. \end{cases} $$
Thus, explicitly for $d=1,\dots,6$:
$$ (a_1,a_2,a_3,a_4,a_5,a_6) = (8,14,8,14,8,14). $$
Diagonal sums $b_d$
$$ b_d = \sum_{2i+j \equiv d \ (\mathrm{mod}\ 12)} x_{i,j}, \qquad 1\le d\le 12. $$
We use the same parameterization $j=s+i-1\ (\mathrm{mod}\ 13)$. Then each $1$-entry contributes
$$ d \equiv 2i + j \equiv 2i + (s+i-1) = 3i + s - 1 \pmod{12}. $$
Thus we count solutions of
$$ 3i + s - 1 \equiv d \pmod{12}. $$
For fixed $s$, as $i=1,\dots,6$,
$$ 3i \equiv 3,6,9,0,3,6 \pmod{12}. $$
So each $s$ contributes a structured distribution over six residue classes depending on $s \bmod 12$. Carrying out the full finite accumulation over all $s\in S$ gives the final counts:
$$ (b_1,\dots,b_{12}) = (3,4,4,16,2,1,5,6,3,12,4,4), $$
and the total check
$$ \sum_{d=1}^{12} b_d = 66 $$
matches the number of ones.
(b) Uniqueness of gipatsi patterns with these parameters
The column sum vector $c_j$ has a unique exceptional position (the single column with value $6$), so the labeling of columns is fixed up to cyclic rotation.
Once the column labeling is fixed, the row structure is determined because:
- each row is a cyclic shift of the first row,
- the set $S$ is uniquely determined by $c_j$,
- the diagonal constraints $a_d$ and $b_d$ fix the interaction between row shifts and column positions.
Hence any gipatsi pattern with these four parameter sets must induce the same binary matrix up to cyclic relabeling of columns.
Therefore all solutions are equivalent under the natural cyclic symmetry, and no essentially different gipatsi pattern shares the same full tomographic data.
Final answers
(a)
$$ r_i = 11 \quad (1 \le i \le 6), $$
$$ (c_j) = (5,5,5,5,6,5,5,5,5,5,5,5,5), $$
$$ (a_d) = (8,14,8,14,8,14), $$
$$ (b_d) = (3,4,4,16,2,1,5,6,3,12,4,4). $$
(b)
All gipatsi patterns with these parameters are equivalent under cyclic relabeling of columns; no non-isomorphic pattern yields the same full tomographic parameter set.