Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 3 / c / v

Always true for a nonempty finite constraint domain, as conventionally assumed. Write $q=|D|$ and identify its values with $\{0,\dots ,q-1\}$. For each satisfying assignment $(x_1,\dots ,x_n)$, simultaneously replace every value byThis permutation of the common constraint domain preserves every equality and inequality, hence every all-different constraint. The resulting $q$ assignments are distinct: equality of even one coordinate before and after a shift forces $a=0(\mathrm{mod}q)$. There is at least one variable, since $m>0$ and $k\ge 2$.

The cyclic group of shifts therefore partitions the solution set into disjoint orbits of size $q$. It follows thatThe conclusion includes an unsatisfiable instance, whose solution count is zero. Full permutation group orbits need not have size $q!$, because unused values can be permuted without changing an assignment; the cyclic-shift argument avoids that mistake.

If an empty constraint domain is permitted, there are zero assignments here, but the wording “divisible by $|D|$” then asks about divisibility by zero, which is ordinarily left undefined. The asserted divisibility uses the standard nonempty-domain convention, and the no-solution conclusion still holds for that degenerate input.