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

Solutions to all three questions of the University of Oxford examination held on 29 May 2023, including all 23 lettered parts. The paper allowed candidates to answer two questions; all three are solved here. Source release: released examination archive, member 2022/T/a16607w1.pdf, whose cover dates the examination to Trinity Term 2023. Question statements and the source illustration are omitted.

Let $V$ be the traversable squares and $H\subseteq V$ the exits. Sample the state space at the end of each complete round, so a live state is $s=(r,f)\in V\times V$ with $r\ne f$. The given starting positions specify the initial state. The board and exits are fixed problem data, rather than changing components of the state space.

The rabbit has at most five actions: stay or move to one of its traversable orthogonally adjacent squares. A search transition model first applies that action, giving $r^{\prime }$, and immediately checks for capture at $r^{\prime }=f$. Otherwise hold $r^{\prime }$ fixed and apply the fox rule twice, checking for capture after each step. A capture is terminal failure; it must not be overlooked merely because the fox could subsequently move elsewhere. A surviving successor is $(r^{\prime },f^{\prime \prime })$. Equivalently, omit actions whose complete-round outcome is capture.

The goal test is the rabbit is on an exit after surviving the fox's entire turn: $r^{\prime }\in H$ and no capture occurred in that round. Merely entering an exit before the fox moves is insufficient. Each surviving search transition model step has cost one when minimizing rounds.

Only legal moves are considered when applying the stated horizontal preference: try a legal horizontal step that reduces horizontal separation, otherwise a legal vertical step that reduces vertical separation, otherwise stay. If a blocked preferred direction is instead interpreted as forcing a stay immediately, the counterexamples below and all completeness and optimality conclusions remain valid.

Write $F=|V|\le mn$. The ordered position pairs give at most $F^2$ states, or $F(F-1)$ live states after excluding capture. Thus the usual Big O notation estimate is $O(m^2{n}^2)$. An additional terminal-failure marker changes this by only one.

For $k$ distinguishable foxes, retain $(r,f_1,\dots ,f_k)$. Different foxes may share a square; none may share the rabbit's square in a live state. There are at most $F(F-1{)}^k$ live position tuples, giving $O((mn{)}^{k+1})$. These counts describe possible encodings; obstacles, starting positions and the fixed fox rule can make the reachable state space much smaller.

The branching factor of the search tree is at most five, so through depth $d$ it has at mostnodes in Big O notation. With no depth bound, the search tree can be infinite, despite the finite state space: tree search retains different action histories even when they end at the same position pair.

For a concrete repeating history, use a two-row, three-column board, indexed from zero, with the sole obstacle $(0,1)$, rabbit at $(0,2)$ and fox at $(0,0)$. Repeated rabbit stays leave the fox blocked horizontally with no vertical separation to reduce. Hence the same live state can repeat forever. An exit at $(1,2)$ is nevertheless safely reachable in one round.

Breadth-first tree search is complete and optimal for minimizing rounds. If a successful escape has finite length $d$, there are only finitely many nodes at depths below $d$, since the branching factor is at most five. Breadth-first tree search therefore reaches a shallowest successful node after finite work, even if other branches continue forever.

It is an optimal search algorithm because every search transition model step costs one round, so minimum depth is exactly the desired minimum number of rounds. The goal test must be applied to the surviving complete-round successor. Here a complete search algorithm guarantees finding an escape when one exists; it need not terminate on every unsolvable instance.

For incompleteness, use the two-row, three-column board from part (c), with exit $(1,2)$. If stay is the first action explored, depth-first tree search follows the repeating state forever. Moving the rabbit down instead survives the round: under legal horizontal-then-vertical movement the fox moves to $(1,0)$ and then $(1,1)$, leaving the rabbit safely at the exit. Thus a one-round escape exists but is never reached in this action order.

For nonoptimality, use an unobstructed one-row board with columns $0,\dots ,6$, initial fox column $0$, initial rabbit column $4$, and exits at columns $3$ and $6$. Moving left once escapes at column $3$ with the fox at column $2$. Moving right twice escapes at column $6$ with successive fox positions $2,4$. A depth-first tree search that explores the latter route first returns two rounds although one suffices. This counterexample supplies an actual returned, suboptimal escape independently of the infinite-branch example.

Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic functionThis is Manhattan distance to the nearest exit, a relaxation heuristic. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.

To prove it is a consistent heuristic, consider a surviving one-round transition from $(r,f)$ to $(r^{\prime },f^{\prime })$. Let $e^{\prime }$ attain the minimum defining $h(r^{\prime },f^{\prime })$. The triangle inequality for Manhattan distance and the rabbit's move bound giveEvery successful terminal state has $h=0$. This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an admissible heuristic. Failed transitions need no successor estimate because they are discarded.

Breadth-first tree search remains complete but is not optimal for maximizing the bonus. Completeness depends on the finite branching factor and a finite successful depth, not on the objective used to compare escapes.

Use the one-row, seven-square example from part (e). The one-round escape at column $3$ leaves the fox at column $2$, so its graph distance to the exit, and hence the bonus, is $1$. The two-round escape at column $6$ leaves the fox at column $4$, giving bonus $2$. The earliest successful node therefore has bonus $1$ when bonus $2$ is achievable. Breadth-first tree search orders by rounds rather than terminal graph distance.

Breadth-first tree search is complete and is still not bonus-optimal. Fix any deterministic rule for choosing among equally short fox routes; the completeness argument again uses only the finite branching factor. The unobstructed corridor of part (g) has unique shortest paths, so its fox moves are exactly the same under the new strategy. The one-round bonus is $1$ and the two-round bonus is $2$, proving nonoptimality without any tie-breaking ambiguity.

If there is no route between fox and rabbit, the printed shortest-path rule needs a convention; letting the fox stay supplies a natural extension. The completeness argument is unchanged, and the counterexample above uses only connected squares. When the fox and rabbit initially belong to the same connected component of a graph, the shortest-path pursuit distance bound also makes every surviving branch finite. That additional property does not make the first escape maximize its bonus.

Let $d_t$ be the graph distance between fox and rabbit after round $t$, with $d_0$ their initial graph distance. Initial reachability makes $d_0$ finite, and ordinary moves preserve membership in their common connected component of a graph. After the rabbit's next move, the triangle inequality gives intermediate separation at most $d_t+1$. If that separation is at most two, the fox catches the rabbit that round. Otherwise the fox takes two steps along a shortest path, leavingThus a successful surviving history has at most $d_0-1$ rounds; if it does not escape by then, the next round captures it. The shortest-path pursuit distance bound excludes infinite live branches, even when the rabbit stays. Together with the finite branching factor, it makes the whole relevant search tree finite, so depth-first tree search eventually finds an escape whenever one exists.

For nonoptimality, take the corridor of part (g) and let depth-first tree search try left first. It immediately returns the one-round escape with bonus $1$, whereas trying right twice earns $2$. The decreasing separation proves termination, not optimality of the first returned escape.

In STRIPS, a state records the true ground facts; under the closed-world assumption, an absent fact is false. An action with positive preconditions $P$, add effects $A$ and delete effects $D$ applies when $P\subseteq S$, producing $(S\setminus D)\cup A$.

The given movement action adds the destination fact without deleting the old boat location. After its first crossing the boat can therefore be recorded at both banks, allowing physically impossible loading. Its source-bank symbol is also not a declared action parameter. Repair both issues by using the fully parameterized STRIPS actionHere $\mathrm{notEqual}(s,t)$ excludes a vacuous same-bank crossing. The two static inequality facts already supplied suffice.

The given loading action has no capacity check. Consecutive loads can put arbitrarily many items aboard. Introduce a nullary planning fluent $\mathrm{Empty}$, true initially, and repair loading toUnloading must restore $\mathrm{Empty}$, as in part (c). Including the bank $s$ explicitly as an action parameter removes the other unbound action variable. Equivalently, instantiate separate east-bank and west-bank actions.

These repairs establish the planning state invariants that the boat is at exactly one bank, each item is either at one bank or aboard, and at most one item is aboard. The first two hold initially and are preserved by deleting the former location when adding the new one; the capacity marker permits loading only when no item is aboard. Grounding implicit location variables alone would not repair the missing delete effect or the missing capacity check.

The automated planning goal is the conjunction of the delivered-item facts:The boat need not separately be constrained to end west, although any successful plan with $n>0$ must bring the final item there before unloading it.

Use the STRIPS actionThe onboard precondition prevents inventing an item at a bank, and deleting $\mathrm{onBoat}(x)$ preserves the item's unique location. Restoring $\mathrm{Empty}$ preserves the one-item planning state invariant.

For $i=1,\dots ,n$, executeand, if $i<n$, append $\mathrm{Move}(\mathrm{WEST},\mathrm{EAST})$ before the next iteration.

Each load starts with an empty boat beside an undelivered item. Each unload leaves that item west and restores the loading precondition. By mathematical induction on $i$, after iteration $i$ the first $i$ items are west and the remaining items are east. Thus the automated planning goal holds after $2n-1$ crossings and $4n-1$ actions for $n\ge 1$. For $n=0$, the empty plan already achieves the goal.

Replace the one-place marker $\mathrm{Empty}$ by three nullary planning fluents $q_0,q_1,q_2$, meaning that zero, one or two items are aboard. Initially only $q_0$ is true. Exactly one of these facts is maintained. No additional object constants are needed.

For compactness, define the common loading preconditionsand common unloading preconditionsThe four STRIPS actions areHere the first unloading removes one of two items, and the last unloading removes the sole remaining item; items do not require fixed seat identities. The movement action remains as repaired in part (a) and changes none of the occupancy facts.

The planning state invariant is $q_j$ true exactly when $j$ items are aboard. Every action changes the marker by the same amount as the actual onboard count, so it follows by mathematical induction from the initial empty boat. In particular, a third load is impossible.

Partition the items into successive groups of size two, with a singleton final group if $n$ is odd. For a pair $(x,y)$ on the east bank, executeFor a singleton $x$, executeReturn the empty boat east between groups. Each group starts and ends with marker $q_0$, and its items finish west, proving all preconditions and the final goal by mathematical induction over the groups. For $n\ge 1$ there are $\lceil n/2\rceil$ outward journeys and $2\lceil n/2\rceil -1$ crossings in total; $\lceil \cdot \rceil$ is the ceiling function. Again $n=0$ needs no actions.

Keep the corrected one-place STRIPS model, replace the item constants and their initial typing facts by $\mathrm{FOX},\mathrm{RABBIT},\mathrm{CARROT}$, and require all three west in the goal. The farmer travels with the boat, so the boat's bank also records where supervision is available. The new requirement concerns the bank being left: incompatible items may coexist at the farmer's current bank, but must not be left there together.

Here is a compilation using only ordinary positive STRIPS preconditions. Replace $\mathrm{onBoat}(x)$ everywhere by $\mathrm{at}(x,\mathrm{BOAT})$, extending the item's possible locations toThe boat itself still has only bank locations, enforced by $\mathrm{isBank}$. Initialize a static relation $\mathrm{SafePair}(p,q,s)$ for every $p,q\in \mathcal{L}$ and bank $s$ except $p=q=s$. It states that two incompatible items at locations $p,q$ are not both on the bank about to be left.

Introduce planning safety certificates $\mathrm{SafeToSail}(\mathrm{EAST})$ and $\mathrm{SafeToSail}(\mathrm{WEST})$, neither initially true. The following checking action grants a certificate:Add $\mathrm{SafeToSail}(s)$ to the preconditions of $\mathrm{Move}(s,t)$. Every load, unload and move deletes both certificate facts. The other movement and capacity effects remain unchanged.

Deleting certificates on every location change prevents a stale safety check from authorizing a later unsafe departure. A certificate is granted only for the actual current locations and only when both incompatible pairs are separated on the departure bank. During a crossing the remaining bank is therefore safe; on arrival the farmer supervises the destination bank. This proves the required safety property by mathematical induction over crossings. The static $\mathrm{SafePair}$ facts are never changed.

Write $F,R,C$ for the three item constants, $E,W$ for the banks, $L,U,M$ for the corrected load, unload and move actions, and $K_s$ for $\mathrm{Check}(s,p_F,p_R,p_C)$ instantiated with the items' actual current locations. A fully executable plan in the STRIPS model of part (g) isThus the seven crossings carry rabbit west, nothing east, fox west, rabbit east, carrot west, nothing east, rabbit west.

Immediately before those crossings, the items left on the departure bank are respectively $\{F,C\},\{R\},\{C\},\{F\},\{R\},\{F,C\},\varnothing$. None contains an incompatible pair, so each displayed $K_s$ has its safety preconditions. Each loaded crossing carries exactly one item, and all three finish west.

For fair division, let $J=\{1,\dots ,m\}$ and let the additive valuation of agent $i$ be $v_i(S)={\sum }_{j\in S}{v}_{ij}$. Use one variable $X_i$ per agent, with constraint domain $\mathcal{P}(J)$, the power set of the items. Empty bundles are permitted in this original formulation.

Require pairwise disjoint sets:Each such binary constraint involves exactly $X_i,X_{\ell }$. Require complete allocation by the single all-variable constraintFinally impose the envy-free allocation binary constraintseach on $X_i,X_{\ell }$. The two directions for a pair use different agents' additive valuations and must both hold. These conditions give precisely an ordered set partition of the items that is an envy-free allocation.

Use one variable $Y_j$ per item, with constraint domain $\{1,\dots ,n\}$. Its value is the recipient agent. Every assignment automatically allocates each item exactly once, so separate coverage and disjointness constraints are unnecessary.

For every ordered pair $i\ne \ell$, imposeHere $1$ is an indicator function. The constraint involves every $Y_j$ with $v_{ij}\ne 0$; one may formally give it scope $\{Y_1,\dots ,Y_m\}$, since zero coefficients make the other variables irrelevant. These constraints state envy-free allocation using the comparing agent's additive valuation on both sides. In contrast to part (a), they generally involve more than two variables.

With agent variables, each constraint domain has cardinality $2^m$. Their total number of listed domain values is $n{2}^m$, while the Cartesian product of the domains hascomplete assignments before constraints.

With item variables, each constraint domain has cardinality $n$. Their total number of listed domain values is $mn$, while their Cartesian product hascomplete assignments. These are raw domain-space sizes. The larger agent-variable space includes overlaps and missing items; imposing the allocation constraints reduces it to the same $n^m$ actual complete allocations represented directly by item variables.

Before using no-waste allocation to restrict the constraint domains, there is one constraint graph vertex for each of $A,B,C,D,E$. Every distinct pair has a disjointness binary constraint, and also the two directional envy-free allocation constraints. Thus the constraint graph is the complete graph $K_5$, with all ten edges.

The nonempty-bundle and no-waste allocation requirements are unary and add no edges. The original all-item coverage constraint has been removed because this variant permits unallocated items.

Restrict each agent to nonempty bundles of items that they value positively. Let the positive-value supports beThe residual constraint domains are $D_i=\mathcal{P}(S_i)\setminus \{\varnothing \}$, with sizes $7,31,3,3,3$, respectively. The no-waste allocation and nonempty-bundle requirements are now built into these constraint domains.

If $S_i\cap S_{\ell }=\varnothing$, every pair $X_i\in D_i$, $X_{\ell }\in D_{\ell }$ is disjoint. Moreover, $v_i(X_{\ell })=v_{\ell }(X_i)=0$, so both envy-free allocation inequalities hold automatically because all values are nonnegative. Thus all three binary constraints disappear for the pairsThe only positive-support overlaps, and hence the remaining constraint graph edges, arewhere parentheses list the shared items.

Each listed pair really retains restrictions. For $AC$, $AB$, $BD$, $BE$, respectively, let both endpoints choose $\{1\}$, $\{3\}$, $\{4\}$, $\{6\}$: this violates disjointness while belonging to both residual constraint domains. The directional envy-free allocation inequalities are also individually nontrivial. For example, for $AB$, choosing $X_A=\{1\}$ and $X_B=\{3\}$ makes $A$ envious, while choosing $X_A=\{3\}$ and $X_B=\{4\}$ makes $B$ envious. The analogous shared-item comparisons apply on the other three edges.

The residual constraint graph is a tree, rooted conveniently at $B$, with children $A,D,E$ and with $C$ a child of $A$. Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.

For adjacent agents define the combined binary constraintA child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order $A\leftarrow C$, $B\leftarrow A$, $B\leftarrow D$, $B\leftarrow E$.

First, $C$ needs a nonempty subset of $\{1,2\}$. Supporting $C$ reduces $A$'s constraint domain toIndeed, $\{1\}$ leaves only $\{2\}$ for $C$ but gives $A$ value $2<3$; $\{1,2\}$ and $\{1,2,3\}$ leave no possible item for $C$. Each of the four retained choices has a compatible choice for $C$.

Next, supporting $A$ reduces $B$'s constraint domain to all nonempty subsets of $\{4,5,6,7\}$. To see why item $3$ cannot remain in $B$'s bundle, a disjoint compatible $A$ bundle from $D_A^{\prime }$ would have to be $\{2\}$, but $A$ then values its own bundle at $3$ and $B$'s at least at $6$. Conversely any nonempty subset of $\{4,5,6,7\}$ is compatible with $A=\{2\}$.

Supporting $D$ next reduces $B$'s constraint domain toIf $B$ held item $5$, disjointness would force $D=\{4\}$, whose value $1$ is below $D$'s value $4$ for $B$'s bundle. If $B$ holds $4$ but not $5$, then $D=\{5\}$, and $B$ needs value at least $6$ to avoid envying $D$. If $B$ holds neither, $D=\{4\}$ supports every nonempty subset of $\{6,7\}$.

Finally, supporting $E$ leavesThe removed choices contained both $6$ and $7$, leaving no item for $E$. Every displayed choice has a compatible choice for $E$.

Choose $B=\{6\}$, then supported child values, givingItems $3,5$ remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered $A,B,C,D,E$, isEach diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.

Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With $N$ variables and maximum constraint domain size $d$, the basic compatibility checks require $O(N{d}^2)$ time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.

Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: released examination archive, member 2022/T/a18330w1.pdf; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.

We use finite simple graphs throughout the graph arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an edge cover exists only when there is no isolated vertex; for a nonempty connected graph this excludes the one-vertex graph. These minor domain qualifications are made explicit in the affected solutions.

For a set function $f:2^V\to \mathbb{R}$, the four properties are:

Here monotone set function means nondecreasing under inclusion; it does not require strict increase.

The intersection–union definition of a submodular set function isThe diminishing returns characterization of submodularity says that its marginal increments decrease as the conditioning set grows:To obtain diminishing returns from submodularity, apply the intersection–union inequality to $A\cup \{x\}$ and $B$. Their intersection is $A$ and their union is $B\cup \{x\}$, giving exactly the displayed comparison.

Conversely, assume diminishing returns, and enumerate $A\setminus B=\{x_1,\dots ,x_m\}$. Put $C_j=(A\cap B)\cup \{x_1,\dots ,x_j\}$ and $D_j=B\cup \{x_1,\dots ,x_j\}$. Since $C_{j-1}\subseteq D_{j-1}$ and $x_j\notin D_{j-1}$, summing the marginal increment comparisons gives the telescoping sumRearrangement proves submodularity. When $A\setminus B$ is empty, both sums are zero, so the proof includes that case.

Yes: this is a monotone set function. Assume $V\ne \varnothing$, as required by its definition at the empty set. If $\varnothing \ne A\subseteq B$, every weight considered in the maximum over $A$ is considered in the maximum over $B$, hence $f(A)\le f(B)$. If $A=\varnothing$ and $B\ne \varnothing$, the minimum over $V$ is at most every weight in $B$, hence again $f(A)\le f(B)$. No sign condition on the weights is needed.

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).

Yes, for arbitrary signed weights. A hyperedge meets both $S$ and $V\setminus S$ exactly when it meets both $V\setminus S$ and $S$. Therefore $\delta (S)=\delta (V\setminus S)$, and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.

No. Take the hypergraph with $V=\{a,b\}$ and its single hyperedge $\{a,b\}$ of weight $1$. Then $\{a\}\subseteq V$ but $f(\{a\})=1>0=f(V)$, violating the monotone set function property. This example already has strictly positive weights.

No for arbitrary signed weights. Give the same single hyperedge weight $-1$. For $A=\{a\}$ and $B=\{b\}$,This directly violates the defining inequality for a submodular set function.

With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.

For submodularity, write $f(S)={\sum }_{e\in E}w(e)q_e(S)$, where $q_e(S)$ is the indicator function that $e$ meets both sides. Fix $x\notin S$. If $x\notin e$, its marginal increment is zero. If $x\in e$, let $m=|e|\ge 2$ and $j=|S\cap (e\setminus \{x\})|$. Its marginal increment isFor $m=2$, the middle case is absent. As $S$ grows without acquiring $x$, $j$ can only increase, so these marginal increments can only decrease. Each $q_e$ therefore satisfies diminishing returns. Multiplying by $w(e)\ge 0$ and summing preserves the inequality, proving submodularity of $f$.

Use the chain lower bound for a submodular set function. Order $T=\{x_1,\dots ,x_n\}$, set $P_j=\{x_1,\dots ,x_j\}$ with $P_0=\varnothing$, and put $a_j=f(P_j)-f(P_{j-1})$. For each $U\subseteq T$, reveal its elements in this same order. Since $U\cap P_{j-1}\subseteq P_{j-1}$, diminishing returns and the normalised set function property giveApply this to each $T_i$ and interchange the finite sums. Every element occurs exactly $k$ times, soThis is the exact-cover inequality for submodular set functions. Some $a_j$ can be negative: exact multiplicity, rather than merely at least $k$ occurrences, is what makes the argument valid without monotonicity. In fact the nonnegative function hypothesis is unnecessary here. If $T=\varnothing$, every $T_i$ is empty and both sides vanish.

The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For $x\in V$, defineThe set function $h$ is a modular set function: the contributions of each element, and the constant $f(\varnothing )$, cancel inSubtracting this equality from the submodularity inequality for $f$ proves that $g$ is a submodular set function. Also $g(\varnothing )=0$, so it is a normalised set function.

For $x\notin S$, the inclusion $S\subseteq V\setminus \{x\}$ and diminishing returns implyAdding elements one at a time now proves that $g$ is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus $f=g+h$ has all the required properties.

Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing )=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing )=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.

A matroid is a pair $(X,\mathcal{I})$, where $X$ is a finite ground set and $\mathcal{I}\subseteq 2^X$ is its collection of matroid independent sets, satisfying the matroid independence axioms:

The last axiom is augmentation. In particular, every maximal matroid independent set within a given subset has maximum cardinality there: otherwise augmentation would enlarge it.

On fixed labelled ground sets of cardinality $1,2,3$, the numbers of matroids are respectively $2,5,16$.

For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving $2^2-1=3$ more possibilities: total $1+3+1=5$.

For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.

At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid $U_{2,3}$, or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if $\{a,b\}$ and $\{a,c\}$ were matroid dependent sets but $\{b,c\}$ a matroid independent set, augmentation from $\{a\}$ to $\{b,c\}$ would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives $3+1+3=7$ examples.

Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore $1+7+7+1=16$.

Up to matroid isomorphism, the numbers for $n=1,2,3$ are $2,4,8$. A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.

For $n=1$, the loop of a matroid and the nonloop are different types. For $n=2$, there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.

For $n=3$, the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid $U_{2,3}$. Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives $1+3+3+1=8$. The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.