Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 2 / g

Choose one global direction and impose it on every adjacent pair. Keep $X_i\in \{1,\dots ,m\}$, introduce $D\in \{+,-\}$, and impose for each $i<n$ the relationBecause the same $D$ occurs everywhere, transitivity gives either a strictly increasing whole sequence or a strictly decreasing one. Choosing independently between $<$ and $>$ at each edge would merely require adjacent values to differ and would incorrectly allow zigzags.

If a binary formulation is required, replace each ternary relation by a hidden-variable encoding. Add a variable $Y_i$ with domainUse three binary constraints: the sign component of $Y_i$ equals $D$, its first numeric component equals $X_i$, and its second equals $X_{i+1}$. These enforce exactly the relation above while leaving the original variable domains unchanged. Each auxiliary domain has $m(m-1)$ values.

For $n\ge 2$, the projected solutions in the original $X_i$ variables number $2\left(\genfrac{}{}{0ex}{}{m}{n}\right)$ when $m\ge n$, and zero otherwise. In particular $m=n=3$ gives exactly $(1,2,3)$ and $(3,2,1)$. For $n=1$, direction is irrelevant and the projected solutions number $m$, not $2m$.