Past exam of the computer science course of the University of Oxford / 2020

a

Solution

TODO: the classifications, chosen heuristic functions and least-cost outcomes for G1–G5 cannot be established from the corrupted original Figure 1. The missing edges, costs, priority labels and lower portions of the five search trees are required inputs. The surviving portions and the two heuristic function tables do not determine those answers. No reconstructed graph or invented expansion trace is assumed.

For a readable instance, depth-first search follows the deepest pending branch and breadth-first search expands by search depth; neither generally minimizes unequal edge costs. Uniform-cost search orders by path cost

g

, whereas A-star search orders by

g + h

. A displayed A-star search score would identify the estimate by subtracting the accumulated path cost. Under nonnegative costs and the usual terminating-search assumptions, uniform-cost search returns a least-cost goal state when testing goals on removal from the search frontier; A-star search additionally needs an admissible heuristic with appropriate reopening, or a consistent heuristic for the usual closed-set implementation. These rules explain how the missing information would be used, but cannot identify a particular damaged search tree.

b

Solution

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions

s \to t

of cost

10

s \to x

of cost

1

and

x \to t

of cost

1

, where

t

is the only goal state. The perfect heuristic is

h^{*} (s) = 2

h^{*} (x) = 1

h^{*} (t) = 0

. Greedy best-first search selects the direct goal of cost

10

because its priority is zero. The least path cost is

2

. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects

s, t

, while A-star search selects

s, x, t

: after expanding

s

, the A-star search priorities are

2

for

x

and

10

for the direct copy of

t

. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance

h^{*} (s)

. The first transition of a least-cost continuation has some successor

s^{'}

with

h^{*} (s) = c (s, s^{'}) + h^{*} (s^{'}) > h^{*} (s^{'}) .

Every older entry in the search frontier has estimate at least

h^{*} (s)

, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give

s

two successors

a, b

of cost

1

, add

a \to x

of cost

0

, and add

x \to t

and

b \to t

of cost

1

. The perfect heuristic has values

2

s

1

a, b, x

and

0

t

. Alphabetical priority ties let greedy best-first search select

s, a, b, t

, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfies

h^{*} (s) \leq c (s, s^{'}) + h^{*} (s^{'})

on every edge, by taking that edge and then a least-cost continuation. Thus

h^{*}

is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write

C^{*} = h^{*} (s_{0})

. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with

f = g + h^{*} = C^{*}

. A-star search therefore selects only search nodes with

f \leq C^{*}

. Since

g \geq 0

h^{*} (n) \leq g (n) + h^{*} (n) \leq C^{*} = h^{*} (s_{0}) .

This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

c

Solution

Let the input words be

s, t

, let

L

be their common length, let

Σ

be the finite alphabet, and let

D_{L}

contain the dictionary words of length

L

. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space

S = D_{L} \cup {s}

, with initial state

s

; including

s

handles an input word not itself in the dictionary.

At word

w

, an action is a position–letter pair

(i, ℓ)

with

1 \leq i \leq L

ℓ \in Σ

and

ℓ \neq = w_{i}

, permitted precisely when replacing

w_{i}

ℓ

gives

w^{'} \in D_{L}

. The search transition model returns that

w^{'}

, and the goal test is

w = t

. If

s = t

, the empty sequence is accepted; if

t \in / D_{L}

and

s \neq = t

, no transition can reach

t

Assign each permitted transition cost

1

. A search node at search depth

k

has

g (n) = j = 1 \sum k 1 = k .

Thus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

d

Solution

The proposed Hamming distance is both an admissible heuristic and a consistent heuristic. Write

h (w) = ∣ {i : w_{i} \neq = t_{i}} ∣.

Every position differing from the target must change at least once along any successful word ladder. One mutation changes only one position, so every solution from

w

has at least

h (w)

steps. This proves

h (w) \leq h^{*} (w)

, including an unreachable target with

h^{*} (w) = \infty

. Dictionary restrictions may force extra changes, but cannot remove that lower bound.

Adjacent words differ in one position, so their Hamming distances to

t

differ by at most one. Since every transition costs one,

h (w) \leq 1 + h (w^{'}), h (t) = 0.

These are exactly the consistent heuristic conditions. Equivalently, allowing all length-

L

words gives a relaxation heuristic whose exact distance is the Hamming distance; restoring the dictionary can only increase the minimum required number of steps.

e

Solution

The difficulty is representing dictionary membership and the one-letter relationship in positive conjunctive STRIPS preconditions; a finite dictionary nevertheless admits an exact encoding. Pure STRIPS does not provide string indexing, a “differs in one position” operator, arbitrary disjunctive tests or a procedure that calls a dictionary lookup. Those relationships must be represented by ground facts or compiled into ground actions.

One exact whole-word encoding uses a planning fluent

At (w)

and a static predicate

Next (w, w^{'})

containing exactly the permitted dictionary mutations. For the action schema

Change (w, w^{'})

, use

Pre Add Del = {At (w), Next (w, w^{'})}, = {At (w^{'})}, = {At (w)} .

Initialize

At (s)

and the static transition facts, and use goal

At (t)

. Only one

At

fact is true initially. Each applicable ground action deletes it and adds exactly its permitted successor, so mathematical induction proves that exactly one current-word fact remains true and that every plan is a legal word ladder. Conversely, every legal word ladder directly supplies a plan. An isolated non-dictionary start is handled as in (c). A shortest plan has the fewest mutations.

This encoding moves the hard lexical relationship into preprocessing. For

N

dictionary words, checking all ordered pairs takes

O (N^{2} L)

character comparisons, although indexing can do better; the number of stored transitions is at most

N L (∣Σ∣ - 1)

when all states are dictionary words. The STRIPS representation is finite, but its size and preprocessing cost matter.

A position-based representation instead uses planning fluents

Letter (i, ℓ)

. Changing position

i

must delete its old letter and add its new one; all other positions persist through the STRIPS update rule. Merely requiring each position to contain a letter admits non-dictionary strings. A disjunction over all dictionary words is not a positive conjunctive STRIPS precondition. It can be compiled into separate ground actions, each requiring every letter of a valid source word and changing one position to reach a valid destination. This again enumerates lexical cases and can be large. Arbitrary letter changes followed by an unconstrained “validate” action are unsound: several illegal intermediate strings could otherwise lead to a legal goal. Legality must hold after every mutation, not only at the endpoint.

2

a

Solution

For a finite constraint satisfaction problem, remove values violating unary restrictions before starting. The following backtracking algorithm makes independent copies of constraint domains at each branch, so failed forward checking cannot contaminate a sibling branch.

SOLVE(P):
    D := domains of P after unary filtering
    if some D[X] is empty: return failure
    return SEARCH({}, D)

SEARCH(assignment, D):
    if every variable is assigned: return assignment
    X := SELECT-UNASSIGNED-VARIABLE(assignment, D, P)
    for v in ORDER-DOMAIN-VALUES(X, assignment, D, P):
        if X=v is compatible with the current assignment:
            next_assignment := assignment extended by X=v
            next_domains := a deep copy of D
            next_domains[X] := {v}
            if INFERENCES(X, v, next_assignment, next_domains, P) succeeds:
                result := SEARCH(next_assignment, next_domains)
                if result is not failure: return result
    return failure

SELECT-UNASSIGNED-VARIABLE implements minimum remaining values: choose an unassigned variable with the smallest current constraint domain. Break ties by the degree heuristic, choosing the variable constrained to the greatest number of other unassigned variables; a fixed final tie rule makes execution reproducible. ORDER-DOMAIN-VALUES may use any complete ordering; ascending values suffice here.

INFERENCES implements forward checking: for each unassigned neighbor

Y

X

, remove every value incompatible with

X = v

, and fail if any constraint domain becomes empty. For higher-arity constraints, reject any completely instantiated violation and use a sound chosen filtering rule; the stated neighbor test is the usual binary case. Forward checking never removes a value used by a possible extension of the current assignment. Exhausting every surviving value therefore makes this finite backtracking procedure both sound and complete.^[ref]^[ref]

b

Solution

Forward checking makes minimum remaining values respond to current restrictions rather than the original constraint domain sizes. After

X = v

, its neighbors may have fewer choices, become forced or lose all choices. Minimum remaining values then selects the newly constrained variable early, while an empty constraint domain triggers immediate failure. The two mechanisms expose failure sooner and reduce wasted backtracking.

Forward checking only tests an unassigned neighbor against the newly assigned value. It need not check whether two still-unassigned variables have mutually supporting values. Arc consistency requires every value at either end of each binary constraint to have support in the other constraint domain, and AC-3 propagates deletions until this condition stabilizes or a constraint domain becomes empty.^[ref]

For example, let

X, Y, Z

initially have constraint domains

{1, 2}

with constraints

X \neq = Y

and

Y \neq = Z

. Assigning

X = 1

makes forward checking reduce

D_{Y}

{2}

, but leaves

D_{Z} = {1, 2}

. Arc consistency also deletes

2

from

D_{Z}

, leaving

{1}

. Neither procedure alone decides every general constraint satisfaction problem: a triangle of two-valued inequalities satisfies arc consistency but is unsatisfiable.

c

Solution

One solution is $(a, b, c, d, e) = (1, 2, 3, 2, 1)$ . Use ascending value order; after minimum remaining values and the degree heuristic, break any remaining variable tie alphabetically. Apply the unary restrictions first:

D_{a} = {1, 2}, D_{b} = {1, 2, 3}, D_{c} = D_{d} = D_{e} = {1, 2, 3, 4} .

Minimum remaining values selects

a

, even though

c

has greater initial vertex degree. Set

a = 1

. Forward checking removes

1

from the three neighbors

b, c, d

D_{b} = {2, 3}, D_{c} = D_{d} = {2, 3, 4}, D_{e} = {1, 2, 3, 4} .

Now

b

is the unique minimum remaining values choice. Set

b = 2

. Forward checking removes

2

from

c, e

D_{c} = {3, 4}, D_{d} = {2, 3, 4}, D_{e} = {1, 3, 4} .

Select

c

and set

c = 3

. Its remaining neighbors are

d, e

, so forward checking gives

D_{d} = {2, 4}, D_{e} = {1, 4} .

(4)

The two remaining variables tie on constraint domain size and each has one unassigned neighbor, so the degree heuristic also ties. Alphabetical order selects

d

; take

d = 2

. Since

2

is already absent from

D_{e}

, forward checking makes no further deletion. Finally choose

e = 1

. No empty constraint domain or violation occurs, so this branch needs no backtracking.

All eight binary constraints are checked explicitly by the unequal value pairs

(a, b) = (1, 2), (a, d) = (1, 2), (a, c) = (1, 3), (b, e) = (2, 1), (b, c) = (2, 3), (c, e) = (3, 1), (c, d) = (3, 2), (d, e) = (2, 1) .

(5)

The unary restrictions also hold. Equalities

a = e

and

b = d

are permitted because those pairs have no edges in the constraint graph.

d

Solution

Cutset conditioning selects a cycle cutset

C

: deleting its vertices makes the binary constraint graph a forest. Enumerate assignments to

C

, reject those violating internal constraints, and filter each remaining constraint domain against the chosen cutset values. Solve the residual components by tree-structured constraint satisfaction. Stop at a successful assignment, or report failure after all cutset assignments fail. Completeness follows by considering the restriction of any full solution to

C

; soundness follows by checking internal, crossing and residual constraints. With maximum constraint domain size

q

and

k

cutset variables, a typical bound is

O (q^{k} (n - k) q^{2})

for the residual forest work, with cutset and crossing checks added explicitly.^[ref]

Here take $C = {c, e}$ . The residual constraint graph has vertices

a, b, d

and only edges

ab, a d

, a tree rooted at

a

. Choose the consistent cutset values

c = 3, e = 1

. Filtering against these assignments gives

D_{a} = {1, 2}, D_{b} = {2}, D_{d} = {2, 4} .

The upward support pass from

b

deletes

a = 2

, because

b

can only equal

2

. The pass from

d

retains

a = 1

, which has support

2

4

. Assign

a = 1

at the root and then supported child values

b = 2, d = 2

. Together with

c = 3, e = 1

, this gives the solution in (c).

No singleton cycle cutset exists: deleting

a, b, d

e

leaves, respectively, a triangle on

b ce, a c d, ab c

ab c

; deleting

c

leaves the cycle in a graph

a - b - e - d - a

. Thus the two-element choice is also minimum, although the algorithm only requires a valid cutset.

e

Solution

Use an exactly-one constraint for each finite-domain variable and a Boolean clause forbidding each disallowed constraint tuple. Let the variables be

X_{1}, \dots, X_{n}

, with explicitly listed finite constraint domains

D_{i}

, and let constraint

C

have distinct-variable scope

S_{C}

and allowed relation

R_{C} \subseteq \prod_{i \in S_{C}} D_{i}

. Introduce a Boolean variable

p_{i, v}

for every

v \in D_{i}

, interpreted as

X_{i} = v

. The direct SAT encoding of finite-domain constraints is

φ_{P} = ⋀_{i} [(⋁_{v \in D_{i}} p_{i, v}) \land ⋀_{{u, v} \subseteq D_{i}, u \neq = v} (\neg p_{i, u} \lor \neg p_{i, v})] \land ⋀_{C} ⋀_{t \in F_{C}} (⋁_{i \in S_{C}} \neg p_{i, t_{i}}), F_{C} = (\prod_{i \in S_{C}} D_{i}) ∖ R_{C} .

In the middle logical conjunction, each unordered distinct pair is included once. The first Boolean clause requires at least one value, the pairwise Boolean clauses permit at most one, and a final Boolean clause is false exactly when all coordinates of one forbidden tuple are selected. The formula is in conjunctive normal form. An empty constraint domain produces an empty Boolean clause, correctly making the instance unsatisfiable.

For soundness of the reduction, a solution

x

of the constraint satisfaction problem gives the Boolean valuation

p_{i, v} = 1

exactly when

v = x_{i}

. Every exactly-one constraint holds; a forbidden tuple differs from

x

on at least one scoped coordinate, making its negative Boolean clause true. Thus

x

supplies a satisfying assignment for

φ_{P}

Conversely, a satisfying assignment selects a unique value

x_{i}

for every

X_{i}

. If a constraint failed, the selected scoped tuple would belong to

F_{C}

, and its entire negative Boolean clause would be false. That contradicts satisfiability. Hence

x

is a solution. Decoding takes

O (\sum_{i} ∣ D_{i} ∣)

by scanning the value indicators. This proves $P$ has a solution if and only if $φ_{P}$ is satisfiable.

For explicit size accounting, put

q_{i} = ∣ D_{i} ∣

r_{C} = ∣ S_{C} ∣

and

f_{C} = ∣ F_{C} ∣

. There are

\sum_{i} q_{i}

Boolean variables,

K = n + \sum_{i} (2 q _{i}) + \sum_{C} f_{C}

Boolean clauses, and

L = \sum_{i} q_{i} + 2 \sum_{i} (2 q _{i}) + \sum_{C} r_{C} f_{C}

literal occurrences. These formulas count nonempty scopes; a false zero-arity constraint contributes an empty Boolean clause, while a true one contributes none. Formula storage is

O (K + L)

literal-sized records; a bit-level encoding also stores indicator indices. With maximum constraint domain size

q

m

constraints and maximum arity

r

, this is bounded by

O (n q^{2} + m r q^{r})

for nontrivial domains and scopes. In the common binary case it is $O ((n + m) q^{2})$ .

The input representation matters: listing all forbidden tuples costs up to

\prod_{i \in S_{C}} q_{i}

tests per constraint. This is polynomial for bounded arity and explicitly represented domains, but can be exponential in the description length of a succinct high-arity constraint. The translation is valid in that case without constituting a polynomial-size reduction. If a compact constraint is supplied as a polynomial-size Boolean circuit, one may instead encode that circuit using auxiliary Boolean variables and local conjunctive normal form equivalences, with size proportional to the circuit. No compact representation is silently assumed.

For the instance in (c), after unary filtering there are

17

indicators. The five at-least-one Boolean clauses,

22

pairwise at-most-one Boolean clauses and

24

forbidden-equality Boolean clauses give $51$ Boolean clauses. Setting only

p_{a, 1}, p_{b, 2}, p_{c, 3}, p_{d, 2}, p_{e, 1}

true encodes the displayed solution.

f

Solution

The translation gives a sound and complete route through an optimized SAT solver; it trades access to general-purpose SAT machinery against encoding cost and the possible loss of constraint-specific structure. Modern SAT solvers use efficient unit propagation, adaptive branching and clause learning. Learned Boolean clauses can summarize conflicts involving many original variables, allowing later branches to avoid repeating the same failed combination. The reduction also offers a standard, reusable interface: improvements to a SAT solver can benefit many finite-domain constraint satisfaction problems.

The Boolean formula may be much larger than the original constraint satisfaction problem, especially for a succinct high-arity relation. One original variable becomes many indicators, and general branching may lose the interpretation that the minimum remaining values and degree heuristic exploit directly. Native constraint propagation can exploit a relation without enumerating all its forbidden tuples. Even in the binary case, stronger propagation does not follow just from switching to SAT.

For example, take

D_{X} = {1, 2}

D_{Y} = {a, b, c}

, and let the only allowed pairs be

(1, c), (2, a), (2, b)

. The forbidden-pair encoding contains

\neg p_{X, 1} \lor \neg p_{Y, a}

and

\neg p_{X, 1} \lor \neg p_{Y, b}

. If

p_{Y, c}

becomes false, arc consistency deletes

X = 1

because it has no support. Yet the direct encoding has no unit Boolean clause forcing

\neg p_{X, 1}

: both

a, b

remain possible individually, so plain unit propagation does not make that deletion. A SAT solver can eventually derive it through additional reasoning or search. Conversely, clause learning can combine information beyond the local consistency enforced by AC-3. Neither approach uniformly dominates: performance depends on representation, propagation strength and the instance's structure; both still face exponential worst-case search on general inputs.

3

a

Solution

Depth-first search computes minimax search values with much less live storage and naturally supports alpha-beta pruning. A parent's value needs only its current best child value and the next child to visit. Once a child subtree has been evaluated, its internal search nodes can be discarded; a final value cannot usually be computed from a nonterminal frontier alone.

With branching factor

b

and horizon

d

, breadth-first search stores a frontier of order

b^{d}

. A depth-first search implementation storing sibling lists uses

O (b d)

space complexity; lazy successor generation can reduce this to

O (d)

frames plus game-state storage. Both unpruned traversals have

O (b^{d})

time complexity for

b > 1

. Depth-first search also supplies a completed sibling outcome early, allowing alpha-beta pruning to reject later subtrees before generating them.

b

Solution

Use utilities from A's viewpoint, with A maximizing and B minimizing. The following alpha-beta pruning code assumes a finite horizon or terminating game tree; leaf evaluation uses terminal utility when available and a specified horizon estimate otherwise.

ALPHABETA(state, depth, alpha, beta, maximizing):
    if state is terminal or depth == 0:
        return EVALUATE(state)
    if maximizing:
        value := -infinity
        for child in SUCCESSORS(state):
            value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
            alpha := max(alpha, value)
            if alpha >= beta: break
        return value
    else:
        value := +infinity
        for child in SUCCESSORS(state):
            value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
            beta := min(beta, value)
            if alpha >= beta: break
        return value

Call the root with

(- \infty, + \infty)

and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.

The bound

α

records an outcome already available to MAX on the active ancestor path;

β

records one already available to MIN. At a MIN node, once a child gives value at most

α

, further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least

β

. Returned values from cut-off subtrees can be bounds rather than exact local minimax search values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.^[ref]

c

Solution

With excellent move ordering, the new horizon is approximately $2 d$ ; without a move ordering assumption, no doubling is guaranteed. For

b > 1

, a full minimax search to depth

d

visits

Θ (b^{d})

search nodes, so the budget

n

has

d \approx lo g_{b} n

. Perfectly ordered alpha-beta pruning evaluates only about

Θ (b^{d^{'} /2})

leaves at depth

d^{'}

. More precisely, for a complete uniform game tree, the best leaf count is

b^{⌈ d^{'} /2 ⌉} + b^{⌊ d^{'} /2 ⌋} - 1

. Equating the dominant costs gives

b^{d^{'} /2} \approx n \approx b^{d}, d^{'} \approx 2 lo g_{b} n \approx 2 d .

Constant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at

Θ (b^{d^{'}})

, giving no asymptotic depth improvement. For

b = 1

, there is no branching to prune and the doubling argument does not apply.^[ref]

d

Solution

Expectiminimax adds chance nodes to the MAX and MIN decisions. A chance node uses

V (s) = \sum_{j} p_{j} V (s_{j}),

so exact evaluation generally needs all outcomes with positive probability. An unfavorable child does not determine the expected value: a later, sufficiently favorable child can offset it. Ordinary alpha-beta pruning therefore does not directly discard the remaining outcomes.

Random outcomes also enlarge the effective branching factor. If each player decision has

b

choices and each action has

c

chance outcomes, exploring

d

player decisions can require order

(b c)^{d}

leaves rather than

b^{d}

. Under the same budget, this gives roughly

d_{stochastic} \approx \frac{l o g n}{l o g b + l o g c}

before additional pruning benefits available in the deterministic game are considered. Exact probability calculations add overhead as well. These effects explain the typically shallower horizon; randomness alone is not a theorem of inevitable slowdown. Known utility bounds permit some expected value bounds and specialized pruning, and chance sampling can trade exactness for speed.^[ref]

e

Solution

Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let

V (s) = (U_{A} (s), U_{B} (s))

. At an A-node choose

s^{*} \in arg max_{s^{'} \in Children (s)} V_{A} (s^{'}), V (s) = V (s^{*}),

and at a B-node replace

V_{A}

V_{B}

. Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.^[ref]

In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because

1 > 0

, the middle B-node prefers its first leaf because

2 > - 2

, and the right B-node prefers its second leaf because

3 > 1

. Their propagated utility pairs, from left to right, are

(1, 1), (- 1, 2), (- 1, 3) .

At the root A compares

1, - 1, - 1

and chooses the left child. Thus the root pair is $(1, 1)$ , with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.

f

Solution

The usual alpha-beta pruning inference fails because increasing B's utility need not decrease A's utility. A partially explored B-node may have found a child unfavorable to A, but B may prefer an unseen child favorable to A as well. An observed low A-coordinate therefore supplies no upper bound on the A-coordinate ultimately propagated by B.

For a concrete counterexample, let a root A-node already have an alternative outcome

(1, 0)

. In another B-node, the first explored child yields

(0, 1)

. A zero-sum-style cutoff would discard its remaining children because

0 < 1

. But an unseen child with outcome

(100, 2)

is preferred by B, and makes the complete B-node return

(100, 2)

, which A strictly prefers to its incumbent. Such a cutoff changes the answer.

The problem persists even after observing a large B-coordinate: without a known relation between coordinates or useful global utility bounds, an unseen pair may have still larger values for both players. Hence there is no generally valid ordinary scalar alpha-beta pruning rule for unrestricted general-sum games. This does not rule out all search pruning: additional bounds, dominance information or a relationship between players' utilities can justify specific cutoffs, as in (g).

g

Solution

Consider a B-node whose parent is an A-node with an already completed incumbent outcome having A-coordinate

α

. At the B-node, let

(x, y)

be the best completed child pair found so far according to B's coordinate. Every remaining child can be skipped, and this B-option discarded by its parent, if

ϵ - y \leq α, equivalently y \geq ϵ - α .

Use a strict inequality if ties must remain open; equality is safe under the fixed rule that the parent retains its already selected child on an A-coordinate tie. This is a nearly-zero-sum pruning rule.

To prove it, note first that a completed max-n search value is some terminal utility pair: each backup copies one entire child pair. Thus the nearly-zero-sum inequality holds at every completed subtree, not just at leaves. Since B maximizes its own coordinate, the ultimately selected pair

(u, v)

at this B-node has

v \geq y

. Therefore

u + v \leq ϵ ⟹ u \leq ϵ - v \leq ϵ - y \leq α .

The already available A-option is at least as good, so remaining children of this B-node cannot alter the parent's selected continuation under the stated tie rule. The second half of the two-sided nearly-zero-sum condition also gives

x + y \geq - ϵ

, hence

u \leq ϵ - y \leq x + 2 ϵ .

Consequently $x + 2 ϵ \leq α$ is another sufficient cutoff, useful if one phrases the test using the observed A-coordinate. The pair-based test is sharper: the value of

y

can certify a cutoff even when the conservative

x + 2 ϵ

test cannot.

When

ϵ = 0

, every pair satisfies

y = - x

, and the rule reduces to

x \leq α

, the ordinary MIN-node alpha-beta pruning cutoff. The extra

2 ϵ

in the A-coordinate-only condition is necessary in general: an observed pair

(- 1, 0)

satisfies the bound for

ϵ = 1

, but B prefers an unseen

(1 - δ, δ)

for

0 < δ < 1

. A increases by almost

2 ϵ

; using just

x + ϵ

as the upper bound would be invalid.

Implementation must discard the ruled-out B-option at its parent rather than return

(x, y)

as an exact completed utility pair. The proof uses an actual completed alternative at that parent; it does not authorize passing arbitrary distant ancestor bounds through general-sum game backups as if every scalar alpha-beta pruning invariant still held. With these local certified cutoffs, an induction over completed subtrees preserves the selected pair and hence the root outcome.

Computational game theory (A15684W1)

Source paper: released examination archive, member 2019/T/a15684w1.pdf. The dated cover identifies the undergraduate Second Public Examination, Trinity Term 2020, Friday 5 June, opening at 09:30 BST. The archive directory is misleading. The cover allows four hours for completion and upload; all printed parts are solved below.

1

a

Solution

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are

b

and

nb

; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization

M = 1

. The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is

n /2

to each initial dataset.

The bimatrix game has payoffs

X : b X : nb Y : b (\frac{n + 2}{2 ( n + 3 )} - \frac{P}{2}, \frac{n + 4}{2 ( n + 3 )} - \frac{P}{2}) (\frac{1}{n + 3}, \frac{n + 2}{n + 3} - P) Y : nb (\frac{n + 1}{n + 3} - P, \frac{2}{n + 3}) (\frac{1}{3}, \frac{2}{3}) .

For example, joint purchase gives dataset sizes

1 + n /2

and

2 + n /2

, total

3 + n

, and each buyer pays

P /2

. A sole buyer gets the full corpus and pays

P

. The total payoff is

1 - P

whenever a purchase occurs and

1

when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, set

t = \frac{n}{n + 3}, 0 < t < 1.

The payoff differences “buy minus do not buy,” with the other player's action held fixed, are

Δ_{X} Δ_{Y} opponent does not buy \frac{2 t}{3} - P \frac{t}{3} - P opponent buys \frac{t - P}{2} \frac{t - P}{2} .

These four differences give all the best response comparisons without mixing up row and column payoffs.

b

Solution

A weakly dominant strategy must be a best response to either opponent action. For X this requires

\frac{2 t}{3} - P \geq 0, \frac{t - P}{2} \geq 0.

The first is stronger because

t > 0

. Thus

X: b is weakly dominant iff 0 < P \leq \frac{2 n}{3 ( n + 3 )} .

For Y the comparisons are

t /3 - P \geq 0

and

(t - P) /2 \geq 0

Y: b is weakly dominant iff 0 < P \leq \frac{n}{3 ( n + 3 )} .

Below each upper endpoint the corresponding strategy is strictly better against both opponent actions; at the endpoint one comparison ties and the other is strict. Thus the answers also satisfy the convention that weak dominance requires a strict advantage somewhere. Since expected payoffs are linear in the opponent's mixing probability, checking both opponent pure strategies suffices for every opponent mixed strategy.

c

Solution

At joint purchase, each player's gain from continuing to buy rather than deviating to

nb

(t - P) /2

. Both actions are best responses exactly when this is nonnegative. Therefore

(b, b) is a Nash equilibrium iff 0 < P \leq \frac{n}{n + 3} .

At equality both players are indifferent to their individual unilateral deviations, which is permitted in a Nash equilibrium. The condition is less restrictive than requiring either player's action to be a weakly dominant strategy: only the opponent's actual action needs to be considered.

d

Solution

When neither buys, X's unilateral deviation gains

2 t /3 - P

, while Y's gains

t /3 - P

. For both to be nonpositive,

P

must exceed the larger threshold. Hence

(nb, nb) is a Nash equilibrium iff P \geq \frac{2 n}{3 ( n + 3 )} .

Equality is included because a zero-gain deviation does not violate a Nash equilibrium. Consequently both joint-purchase and joint-nonpurchase Nash equilibria exist throughout

2 t /3 \leq P \leq t

, a coordination region.

e

Solution

Neither asymmetric purchase outcome is a Nash equilibrium for any permitted $P > 0, n > 0$ . At

(b, nb)

, X's chosen purchase requires

P \leq 2 t /3

, but Y's chosen nonpurchase, against X buying, requires

P \geq t

. These requirements are incompatible because

2 t /3 < t

(nb, b)

, Y's chosen purchase requires

P \leq t /3

, whereas X's nonpurchase against a buying Y requires

P \geq t

. Again the inequalities are incompatible. Thus every Nash equilibrium in pure strategies has both players taking the same action; the conclusion is stronger than merely observing symmetry in their available actions, since their original market shares differ.

f

Solution

Write

P = 999/1000

. If

t > P ⟺ \frac{n}{n + 3} > \frac{999}{1000} ⟺ n > 2997,

then both players prefer buying against a buyer, since

(t - P) /2 > 0

. Both prefer not buying against a nonbuyer:

2 t /3 < 2/3 < P

and

t /3 < 1/3 < P

. These strict opposite best responses give the interior crossing of a coordination game.

An explicit fully mixed Nash equilibrium follows from indifference. Let

p

be X's probability of buying and

q

Y's. X is indifferent when

(1 - q) (\frac{2 t}{3} - P) + q \frac{t - P}{2} = 0,

and Y is indifferent when

(1 - p) (\frac{t}{3} - P) + p \frac{t - P}{2} = 0.

Solving gives

p = \frac{2 ( P - t /3 )}{P + t /3}, q = \frac{2 ( P - 2 t /3 )}{P - t /3}, t = \frac{n}{n + 3}, n > 2997.

(4)

Both numerators and denominators are positive. For

p < 1

the required inequality is

2 P - 2 t /3 < P + t /3

, equivalent to

P < t

; the same comparison for

q < 1

again reduces to

P < t

. Thus

p, q \in (0, 1)

, and the equations make both actions best responses for each player. By linearity of expected payoff, neither player can profit by any other mixed strategy. At

n = 2997

these formulas reach

p = q = 1

and are not fully mixed; the strict threshold matters.

2

a

Solution

The assignment is Pareto optimal. Write

a_{i}

for the room selected by the

i

th student. Suppose another assignment

a^{'}

makes every student at least as well off. The first student already selected their uniquely most valuable room, so

a_{1}^{'} = a_{1}

. Once the rooms of students

1, \dots, i - 1

are fixed, the rooms available to student

i

in the original serial dictatorship are exactly the rooms that remain after those fixed assignments. Student

i

chose the unique maximum among them, so weak improvement requires

a_{i}^{'} = a_{i}

Mathematical induction fixes every student's room. Thus

a^{'} = a

and nobody can be strictly better off, contradicting the definition of a Pareto improvement. Strict room rankings and the absence of allocation externalities are the essential assumptions: a student's utility is determined solely by their own room.^[ref]

b

Solution

No: arbitrary ties can produce an assignment that is not Pareto optimal. A two-student counterexample suffices. Give the first student value

1

for both rooms; give the second student value

1

for

r_{1}

and

0

for

r_{2}

. If the first student breaks the tie by taking

r_{1}

, the second must take

r_{2}

, and the utility vector is

(1, 0)

Swapping the rooms gives utility vector

(1, 1)

, so it is a Pareto improvement. Both choices in the original run maximized the corresponding student's available room value. The strict-ranking argument from (a) fails because the first student's utility need not decrease when that student's room changes.

c

Solution

The equilibrium assignment is $(S_{1}, S_{2}, S_{3}, S_{4}) \mapsto (r_{2}, r_{3}, r_{4}, r_{1})$ , with utility vector $(0.7, 0.7, 0.9, 0.4)$ . Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student

S_{4}

receives the last room and has no remaining choice. Given the first two rooms,

S_{3}

chooses the remaining room maximizing their own room value plus

0.4

if adjacent to

S_{2}

The following complete third-stage comparisons summarize the continuations. The utility in the last column is

S_{2}

's resulting utility, after

S_{3}

makes the indicated best response.

$S_{1}$ room	$S_{2}$ room	Optimal $S_{3}$ room	Resulting $U_{2}$
$r_{1}$	$r_{2}$	$r_{4}$	$0.5$
$r_{1}$	$r_{3}$	$r_{2}$	$0.7$
$r_{1}$	$r_{4}$	$r_{2}$	$0$
$r_{2}$	$r_{1}$	$r_{4}$	$0$
$r_{2}$	$r_{3}$	$r_{4}$	$0.7$
$r_{2}$	$r_{4}$	$r_{3}$	$0.4$
$r_{3}$	$r_{1}$	$r_{2}$	$0.4$
$r_{3}$	$r_{2}$	$r_{4}$	$0.5$
$r_{3}$	$r_{4}$	$r_{2}$	$0$
$r_{4}$	$r_{1}$	$r_{2}$	$0.4$
$r_{4}$	$r_{2}$	$r_{1}$ or $r_{3}$	$0.9$
$r_{4}$	$r_{3}$	$r_{2}$	$0.7$

For example, after

S_{1}

takes

r_{2}

and

S_{2}

takes

r_{3}

, student

S_{3}

compares

r_{1}

0

, with

r_{4}

0.5 + 0.4 = 0.9

. Choosing

r_{4}

also gives

S_{2}

the adjacency bonus, making

U_{2} = 0.3 + 0.4 = 0.7

. The last room

r_{1}

is adjacent to

S_{1}

r_{2}

The table makes

S_{2}

choose

r_{3}, r_{3}, r_{2}, r_{2}

after first-stage choices

r_{1}, r_{2}, r_{3}, r_{4}

, respectively. Their resulting consequences for

S_{1}

are

0.5, 0.7, 0

, and either

0

0.4

. Thus

S_{1}

strictly prefers

r_{2}

, proving the displayed outcome.

There is an off-path tie for

S_{3}

after

(r_{4}, r_{2})

, so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives

S_{1}

at most

0.4

after choosing

r_{4}

, below

0.7

. The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.

d

Solution

No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs

{S_{1}, S_{4}}

and

{S_{2}, S_{3}}

and friendship bonus

0.4

for each student:

S_{1} S_{2} S_{3} S_{4} r_{1} 0.50 0.01 0.01 0.01 r_{2} 0.30 0.50 0.70 0.50 r_{3} 0.02 0.30 0.02 0.02 r_{4} 0.01 0.02 0.50 0.03

Each row is strictly ranked and every room value is positive. In picking order

S_{1}, S_{2}, S_{3}, S_{4}

, backward induction gives the following continuations. Room numbers in a tuple are listed in student order.

S_{1} choice r_{1} r_{2} r_{3} r_{4} resulting assignment (r_{1}, r_{3}, r_{2}, r_{4}) (r_{2}, r_{3}, r_{4}, r_{1}) (r_{3}, r_{2}, r_{4}, r_{1}) (r_{4}, r_{2}, r_{3}, r_{1}) U_{1} 0.50 0.70 0.02 0.01

To check

S_{2}

's incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively

(0.50, 0.70, 0.02)

(0.01, 0.70, 0.42)

(0.41, 0.50, 0.02)

and

(0.41, 0.90, 0.70)

. Student

S_{3}

's own best responses determine those figures, and

S_{4}

again takes the remaining room. All comparisons selecting these continuations are strict.

Hence

S_{1}

chooses

r_{2}

and the subgame perfect equilibrium outcome is

a = (r_{2}, r_{3}, r_{4}, r_{1}), U (a) = (0.70, 0.70, 0.90, 0.41) .

But the feasible assignment

a^{'} = (r_{1}, r_{3}, r_{4}, r_{2}), U (a^{'}) = (0.90, 0.70, 0.90, 0.90)

(4)

strictly improves

S_{1}

and

S_{4}

and leaves

S_{2}, S_{3}

unchanged. Thus

a

is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If

S_{1}

alone takes

r_{1}

, the later best responses lead to

(r_{1}, r_{3}, r_{2}, r_{4})

, not to

a^{'}

; anticipating that reaction gives

S_{1}

only

0.50

e

Solution

Every subgame perfect equilibrium outcome is Pareto optimal under the stated consecutive-friend and bonus conditions. Partition the choosing order into blocks: a single student without a friend, or two friends who choose consecutively. Their slots in the choosing order are adjacent; the proof must separately establish when their allocated rooms will be adjacent.

Let

R

be the rooms remaining before a friend block, with leader

i

and follower

j

. Because

0 \leq v_{i, r}, v_{j, r} \leq 1

and

f_{i}, f_{j} > 1

, each friend strictly prefers every adjacent-to-friend allocation to every nonadjacent one. After leader

i

takes room

r

with an available adjacent room, follower

j

therefore takes their uniquely highest-valued room among the available neighbors of

r

. The leader consequently knows they will receive the adjacency bonus.

R

contains at least one pair of adjacent rooms, let

E (R)

be its nonisolated rooms: the rooms having an available neighbor. Leader

i

must choose from

E (R)

, because choosing there guarantees utility greater than

1

, whereas an isolated choice gives at most

1

. Since the bonus is then fixed and room values are distinct, the leader chooses their unique maximum-value room in

E (R)

. The follower chooses their unique best neighbor. Later students cannot change either allocated room, so later play cannot alter these two students' utilities.

R

contains no adjacent pair, neither friend can obtain the bonus under any allocation of rooms from

R

. Both simply choose their uniquely most valuable remaining room in turn. Removing rooms cannot create a new physical adjacency, so no hidden later move can change that conclusion. A one-student block likewise chooses their unique best available room.

Now compare the equilibrium assignment

a

with any proposed Pareto improvement

a^{'}

. Induct over these blocks, assuming earlier blocks' rooms are already fixed. Thus

a

and

a^{'}

have the same remaining set

R

at the present block. A lone student's room must stay fixed by strict preferences.

For a friend block obtaining adjacency in

a

, both students must retain adjacency in

a^{'}

: losing a bonus larger than

1

cannot be compensated by any room-value increase. The leader's room in

a^{'}

must therefore belong to

E (R)

. It cannot differ from the unique highest-valued room the leader selected there without reducing that leader's utility. Once the leader's room is fixed, the follower likewise must retain the uniquely best available neighbor. If

R

has no adjacent pair, both rooms stay fixed by the ordinary strict-ranking argument.

Thus every block's rooms are unchanged. The only assignment weakly improving all students is

a

itself, so no strict improvement is possible. This proves Pareto efficiency of serial dictatorship with consecutive friends. The proof applies to every subgame perfect equilibrium, since the required choices at each block are strict best responses determined by the available rooms.

3

a

Solution

A simple cooperative game is a transferable utility game

(N, v)

with

v : 2^{N} \to {0, 1}, v (\emptyset) = 0, v (N) = 1, S \subseteq T ⟹ v (S) \leq v (T) .

A coalition of value

1

is a winning coalition; a value-

0

coalition loses. The displayed definition uses the usual monotone, nontrivial convention: the empty coalition loses and the grand coalition wins.

b

Solution

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,

v (S) = {i, j} \subseteq S, i \neq = j \sum w_{ij},

where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at

i

ℓ_{i}

and add

\sum_{i \in S} ℓ_{i}

, counting each loop once. In particular,

v ({i}) = ℓ_{i}

when loops are allowed and is zero otherwise.^[ref]

c

Solution

No representation exists, even allowing arbitrary signed weights and self-loops. Every singleton coalition loses, so each loop weight must be

ℓ_{i} = v ({i}) = 0

. Every two-player coalition wins, which then forces

w_{12} = w_{13} = w_{23} = 1.

The represented grand-coalition value would consequently be

v ({1, 2, 3}) = ℓ_{1} + ℓ_{2} + ℓ_{3} + w_{12} + w_{13} + w_{23} = 3,

contradicting its required value

1

. The obstruction is the additive edge representation, not a restriction that weights be nonnegative: the singleton and pair values already determine every relevant weight.

d

Solution

Yes; without self-loops, such a nontrivial simple cooperative game has exactly one positive edge, of weight $1$ . For each pair,

w_{ij} = v ({i, j}) \in {0, 1},

because singleton and loop contributions are zero. Summing all edge weights gives

v (N) = 1

, so precisely one unordered pair

{a, b}

has weight

1

, and all other pairs have weight zero.

Thus the winning coalitions are exactly those containing both

a

and

b

. For any

0 \leq λ \leq 1

, set

x_{a} = λ, x_{b} = 1 - λ, x_{i} = 0 (i \in / {a, b}) .

This payoff vector is efficient, since

\sum_{i} x_{i} = v (N) = 1

. Every winning coalition receives

1

and every losing coalition receives a nonnegative total, so all inequalities

x (S) \geq v (S)

hold. Hence it belongs to the core of a cooperative game.

In fact these are all core allocations. Singleton conditions require

x_{i} \geq 0

, and the winning pair requires

x_{a} + x_{b} \geq 1

; efficiency then forces equality and zero payoffs outside the pair. The endpoints are both veto players, consistent with the general characterization of the core of a simple cooperative game.

e

Solution

No. Two positive self-loops and one negative edge give a simple cooperative game with an empty core of a cooperative game. Give players

1, 2

loop weights

ℓ_{1} = ℓ_{2} = 1

, put

w_{12} = - 1

, and give every other loop and edge weight zero. For a coalition

S

v (S) = 1_{{1 \in S}} + 1_{{2 \in S}} - 1_{{{1, 2} \subseteq S}} = 1_{{S \cap {1, 2} \neq = \emptyset}} .

Thus a coalition wins exactly when it contains player

1

or player

2

. This is monotone, has values in

{0, 1}

, and satisfies

v (\emptyset) = 0, v (N) = 1

. Extra players for any

n \geq 3

do not alter any coalition value.

The core singleton inequalities would require

x_{1} \geq 1

x_{2} \geq 1

and

x_{i} \geq 0

for every other player, while efficiency requires

\sum_{i} x_{i} = 1

. These requirements are inconsistent. Equivalently, the two disjoint winning singleton coalitions leave no veto player. Signed weights are essential to this particular representation and are permitted in the induced subgraph game model.

f

Solution

A loop-free induced subgraph game is a convex cooperative game if and only if every edge weight is nonnegative. Necessity follows by applying the supermodular inequality to

S = {i}

and

T = {j}

. Since both singleton values and the empty value are zero,

v ({i, j}) + v (\emptyset) \geq v ({i}) + v ({j}) ⟹ w_{ij} \geq 0.

Conversely, direct cancellation of common edge contributions gives, for any coalitions

S, T

v (S \cup T) + v (S \cap T) - v (S) - v (T) = \sum_{i \in S ∖ T j \in T ∖ S} w_{ij} .

Every summand is nonnegative, proving that

v

is a supermodular set function and hence convexity. Equivalently, a player's marginal contribution to

S

Δ_{i} (S) = \sum_{j \in S} w_{ij}

, which cannot decrease as

S

grows. This establishes the convexity criterion for an induced subgraph game directly.^[ref]

g

Solution

There is exactly one such nontrivial game for every $n \geq 1$ : the unanimity game requiring every player. Put

u_{N} (S) = {1, 0, S = N, S \neq = N . Number of games = 1.

It is a simple cooperative game, and permuting players preserves every coalition value. Thus it has the required symmetry of players in a cooperative game. It is also a convex cooperative game: if both

S, T

are winning, all four terms in the supermodular inequality have value

1

; if exactly one is winning, their union is

N

and their intersection loses, giving equality

1 = 1

; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For

n = 1

the same definition gives the sole player value

1

To prove uniqueness, first establish that convex simple games are unanimity games. If

S, T

are winning coalitions, the supermodular inequality gives

2 = v (S) + v (T) \leq v (S \cup T) + v (S \cap T) \leq 2,

so their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection

K

is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains

K

, and monotonicity makes every superset of

K

winning. Hence

v = u_{K}

K

were a proper nonempty subset of

N

, take

i \in K

and

j \in / K

, and let

T = N ∖ {i, j}

. Then

T \cup {i} = N ∖ {j}

contains

K

and wins, whereas

T \cup {j} = N ∖ {i}

loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus

K = N

, proving the claimed count. The “nontrivial” convention excludes the identically zero game; if that degenerate game were also called simple, it would supply one additional symmetric convex example.

Quantum information (A16608W1)

Solutions to all three questions of the 11 June 2020 paper. Released Oxford examination archive, member 2019/T/a16608w1.pdf. The dated cover establishes 2020 despite the archive directory. All displayed state vectors are normalized unless described as unnormalized conditional vectors. We use column vectors,

∣ ij ⟩ = ∣ i ⟩ \otimes ∣ j ⟩

, and the left tensor factor as the first wire. In a product of gates, the rightmost gate acts first. A global phase is physically irrelevant, but all relative signs and phases below are retained.

⟨ ϕ_{0} ∣ = (⟨ 0∣ - i ⟨ 2∣) / 2

and

⟨ ϕ_{2} ∣ = (⟨ 0∣ + i ⟨ 2∣) / 2

. Taking the complex conjugate in the bra is essential. Their squared norms are

1, 1, 1

, and

⟨ ϕ_{0} ∣ ϕ_{2} ⟩ = \frac{1}{2} {1 + (- i) (- i)} = 0, ⟨ ϕ_{0} ∣ ϕ_{1} ⟩ = ⟨ ϕ_{2} ∣ ϕ_{1} ⟩ = 0.

Thus they are an orthonormal set of three vectors in the three-dimensional inner product space

C^{3}

. Such a set is linearly independent and spans the space, so it is an orthonormal basis.

b

For an orthonormal basis, choosing coefficients with magnitudes

p_{j}

gives the required Born rule probabilities. More generally,

\sum_{j} p_{j} e^{i θ_{j}} ∣ ϕ_{j} ⟩

realizes the same distribution for arbitrary phases. The following are convenient examples of pure-state realization of a basis measurement distribution.

i

Solution

Choose $∣ ψ ⟩ = ∣0 ⟩$ . Since

∣0 ⟩ = (∣ ϕ_{0} ⟩ + ∣ ϕ_{2} ⟩) / 2

, the probability amplitudes in the measurement basis are

(1/ 2, 0, 1/ 2)

. Their squared moduli give

(1/2, 0, 1/2)

by the Born rule.

ii

Solution