CF 103306A - Alice Birthday

Rating: -
Tags: -
Solve time: 2m 17s
Verified: no

Solution

Setup

Let $(a_{ij})$ be an $m\times n$ contingency table with row sums

$r_i=\sum_{j=1}^n a_{ij}, \quad 1\le i\le m,$

and column sums

$c_j=\sum_{i=1}^m a_{ij}, \quad 1\le j\le n,$

with $\sum_{i=1}^m r_i=\sum_{j=1}^n c_j$.

Entries are ordered either row-wise as

$(a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{mn}),$

or column-wise as

$(a_{11},a_{21},\ldots,a_{m1},a_{12},\ldots,a_{mn}).$

Solution

a) $2\times n$ contingency tables and bounded compositions

Write the table as

$$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\ a_{21} & a_{22} & \cdots & a_{2n} \end{pmatrix}.$$

Column constraints give

$a_{1j}+a_{2j}=c_j,\quad 1\le j\le n,$

$a_{2j}=c_j-a_{1j}.$

Nonnegativity is equivalent to

$0\le a_{1j}\le c_j.$

The first row sum constraint becomes

$\sum_{j=1}^n a_{1j}=r_1.$

Thus a $2\times n$ contingency table is equivalent to choosing integers $a_{1j}$ satisfying

$\sum_{j=1}^n a_{1j}=r_1,\quad 0\le a_{1j}\le c_j.$

This is exactly a bounded composition of $r_1$ into $n$ parts with upper bounds $c_j$. The second row is then determined uniquely by $a_{2j}=c_j-a_{1j}$. This completes the equivalence. ∎

b) Lexicographically largest table (row-wise order)

The row-wise order compares entries sequentially:

$a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{mn}.$

At each position, the entry should be maximized subject to feasibility with remaining marginals.

For the first entry, $a_{11}$ satisfies

$0\le a_{11}\le \min(r_1,c_1).$

Maximal lexicographic choice gives

$a_{11}=\min(r_1,c_1).$

After fixing $a_{11}$, update residual parameters:

$r_1^{(1)}=r_1-a_{11},\quad c_1^{(1)}=c_1-a_{11}.$

Proceed inductively along row 1. For general $j$,

$a_{1j}=\min!\Big(r_1-\sum_{k=1}^{j-1}a_{1k},; c_j\Big).$

After completing row 1, all entries are forced in row 2 by

$a_{2j}=c_j-a_{1j}.$

For later rows $i\ge 2$, the same greedy rule applies with updated remaining row and column sums:

$a_{ij}=\min!\Big(r_i-\sum_{k<j}a_{ik},; c_j-\sum_{\ell<i}a_{\ell j}\Big).$

This construction is maximal at each step because any increase at an earlier position would violate either a row sum or a column sum, while any decrease reduces the lexicographic value immediately without enabling a compensating increase earlier in the order.

c) Lexicographically largest table (column-wise order)

Now the order is

$a_{11},a_{21},\ldots,a_{m1},a_{12},\ldots,a_{mn}.$

The same greedy principle applies in column-major traversal.

For column $1$, entries are chosen top to bottom:

$a_{11}=\min(r_1,c_1),$

then for $i>1$,

$a_{i1}=\min!\Big(r_i,; c_1-\sum_{k<i}a_{k1}\Big).$

After column $1$, residual row sums and column sum $c_1$ are updated, and the process repeats for column $2$, etc.

In general,

$a_{ij}=\min!\Big(r_i-\sum_{k<j}a_{ik},; c_j-\sum_{\ell<i}a_{\ell j}\Big),$

with traversal in column-major order.

The same feasibility argument as in part (b) shows that any deviation decreasing an earlier entry would worsen the lexicographic value, while any increase is infeasible due to exhausted row or column capacity.

d) Lexicographically smallest table

For the row-wise order, minimality is obtained by making each early entry as small as possible while preserving feasibility of completing the remaining table.

At position $(i,j)$, the entry must satisfy both:

$a_{ij}\ge 0,$

and remaining sums must be achievable:

$\sum_{\text{remaining}} a_{kl} = \text{remaining row sums} = \text{remaining column sums}.$

Thus we maximize the amount allocated later, so we minimize early entries subject to feasibility constraints.

This yields the reverse greedy rule:

$a_{ij}=\max!\Big(0,; r_i^{\text{rem}} + c_j^{\text{rem}} - \text{(maximum fill possible later)}\Big).$

In concrete sequential form, one computes each entry as the smallest value such that all remaining row sums can still be distributed into remaining columns without violating upper bounds.

For the special case structure implicit in contingency tables, this reduces to:

At step $(i,j)$ in row-major order,

$a_{ij}=\max!\Big(0,; r_i^{\text{rem}} - \sum_{k>j} c_k^{\max\text{alloc}}\Big),$

where remaining feasibility is ensured by keeping future entries at their column capacities when necessary.

An equivalent constructive interpretation is: fill the table from left to right, top to bottom, always leaving as much as possible for later entries consistent with row and column totals. This uniquely determines the lexicographically smallest feasible table.

The same principle applies in column-major order by symmetry.

e) Generation of all contingency tables in lexicographic order

A contingency table can be generated by viewing the row-wise sequence

$(a_{11},\ldots,a_{mn})$

as a constrained sequence with dynamic bounds.

At each step $(i,j)$, the variable $a_{ij}$ satisfies a bounded interval determined by remaining marginals:

$0 \le a_{ij} \le \min!\Big(r_i^{\text{rem}},; c_j^{\text{rem}}\Big).$

Fixing earlier entries reduces both residual row sums and column sums, producing updated bounds for subsequent entries.

Thus lexicographic generation proceeds exactly as Algorithm L in Section 7.2.1.3, but with variable bounds instead of binary constraints. At each step, one identifies the rightmost position in the current ordering whose value can be increased without violating any residual row or column constraint, increases it by $1$, and resets all later entries to their minimal feasible values, computed greedily from remaining row and column sums.

Feasibility is preserved because each step maintains invariants

$\sum_j a_{ij}=r_i,\quad \sum_i a_{ij}=c_j,$

and boundedness ensures finiteness of the search space. Lexicographic ordering follows from the fact that the first position of difference dominates all later positions in the ordering, so the algorithm mirrors the standard successor construction for bounded compositions extended to a two-dimensional constraint system.

This completes the solution. ∎