Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2014/iii/paper-37/6/a/solution
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 37 6 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let be the number of true values among . Count the ten clause occurrences for the two choices of . With , the three positive singletons contribute , the three negated-pair clauses contribute , and the last three clauses all hold. With , the four singleton clauses contribute , the negated pairs again contribute , and the last three contribute . ThereforeThe original three-literal clause is satisfied exactly when , and then a value of satisfies exactly seven gadget clauses. If , no choice reaches seven. Thus the required equivalence holds, and seven is also an upper bound for every assignment to the gadget. This is the seven-clause gadget for MAX-2SAT.
New to topics? Read the docs here!