TAOCP 7.2.2.2 Exercise 106

The input data consist of three independent families of integer-valued sums.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.2: Satisfiability

Exercise 106. [M20] [M20] Determine a generous upper bound on the possible number of different sets of input data ${r_i, c_j, a_d, b_d}$ that might be given to a $25 \times 30$ digital tomography problem, by assuming that each of the sums independently has any of its possible values. How does this bound compare to $2^{750}$?

Verified: yes
Solve time: 3m11s

The input data consist of three independent families of integer-valued sums.

For a $25\times 30$ grid:

  • Row sums: $r_i$, $1 \le i \le 25$, each satisfies $0 \le r_i \le 30$, hence $31$ possibilities per row sum.
  • Column sums: $c_j$, $1 \le j \le 30$, each satisfies $0 \le c_j \le 25$, hence $26$ possibilities per column sum.
  • Diagonal sums: there are $25+30-1=54$ diagonals in each direction. Each diagonal sum counts at most 25 cells, so each lies in ${0,\dots,25}$, giving $26$ possibilities per diagonal sum. There are two directions, so $108$ diagonal sums total.

Under the assumption that all sums vary independently over their allowed ranges, the total number of possible input datasets is

$$ N = 31^{25}\cdot 26^{30}\cdot 26^{108} = 31^{25}\cdot 26^{138}. $$

A clean upper bound

We bound each factor by a power of 2:

Since $31 < 32 = 2^5$ and $26 < 32 = 2^5$, we obtain

$$ N < 32^{25}\cdot 32^{138} = 32^{163}. $$

Now rewrite in powers of 2:

$$ 32^{163} = (2^5)^{163} = 2^{815}. $$

Hence a generous upper bound is

$$ N < 2^{815}. $$

Comparison with $2^{750}$

To compare, it suffices to show that $N$ is already larger than $2^{750}$. Using lower bounds:

We use

$$ \log_2 31 > 4.95 \quad \text{(since }2^{4.95} \approx 30.9 < 31\text{)}, $$

and

$$ \log_2 26 > 4.7 \quad \text{(since }2^{4.7} \approx 25.99 < 26\text{)}. $$

Therefore,

$$ \log_2 N = 25\log_2 31 + 138\log_2 26

25(4.95) + 138(4.7). $$

Compute:

$$ 25(4.95)=123.75,\quad 138(4.7)=648.6, $$

so

$$ \log_2 N > 772.35. $$

Thus

$$ N > 2^{772.35} > 2^{750}. $$

Conclusion

We have the clean bounds

$$ 2^{772.35} < N < 2^{815}. $$

In particular, the number of possible input datasets is far larger than $2^{750}$, since even the lower bound already exceeds $2^{750}$.