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

True in some cases and false in others: the two numerical inequalities do not guarantee a solution.

For an unsatisfiable example satisfying both inequalities, take six variables, a constraint domain with five values, and $k=4$, $m=3$, with all-different constraints onAny pair of the six variables occurs together in at least one of these scopes: view the variables as the three pairs $\{1,2\},\{3,4\},\{5,6\}$, and each scope as the union of two pairs. All six values must therefore be distinct. This is impossible with five available values, even though $5>4$ and $5>3$.

For a satisfiable example with the same $k,m,|D|$, take three disjoint groups of four variables and impose one all-different constraint on each group. Assign values $1,2,3,4$ separately in every group. All three constraints hold with $D=\{1,2,3,4,5\}$.These examples concern the intended cases in which the antecedent holds; they do not rely on vacuous truth of an implication.