TAOCP 7.2.2.2 Exercise 107

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: 2m17s

Solution

The statement supplied here does not contain enough information to determine the example pattern. The missing figure is essential for part (a).

The only data given about the example are

$p=6,\qquad n=13,$

and that the first row of the matrix is

$1111101111101.$

A gipatsi pattern is a $p\times n$ matrix $(x_{i,j})$, so the tomographic parameters require all entries $x_{i,j}$:

c_j=\sum_{i=1}^{p}x_{i,j},$$ $$a_d=\sum_{i+j\equiv d\pmod p}x_{i,j},\qquad b_d=\sum_{2i+j\equiv d\pmod{2p}}x_{i,j}.$$ The first row alone determines only the six values involving $i=1$. The remaining five rows of the matrix are not specified in the text provided, and the instruction that row $i$ is shifted right by $i-1$ places applies to the actual woven pattern, not to the entries of the matrix $(x_{i,j})$ themselves. Therefore the missing rows cannot be reconstructed from the first row without the figure. Part (b) also depends on the complete parameter tuple from part (a). Determining whether another gipatsi pattern has the same parameters requires comparing possible $6\times13$ matrices satisfying the same constraints. The figure containing the example matrix must be supplied before the numerical parameters and the uniqueness question can be solved.