Advanced Algorithms Quiz 1: 29 October 2023 (September 2023 term)

Which of the following statements is true?

Statement 1: For every graph $G$ and every maximum flow on $G$, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that's possible in the graph.

Statement 2: Suppose the maximum $(s,t)$-flow of some graph has value $f$. Now we increase the capacity of every edge by 1. Then the maximum $(s,t)$-flow in this modified graph will have value at most $f + 1$.

Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ).

P: W > X > Y > Z
Q: X > Y > Z > W
R: W > X > Z > Y
S: X > Y > W > Z

and

W: S > Q > R > P
X: P > S > Q > R
Y: R > P > Q > S
Z: R > P > S > Q

Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}.

Which of the following is a blocking pair in the matching above?

Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$. Suppose we are also given capacity constraints are as follows:

$c(w_2) = c(y_1) = c(y_3) = 1,$

$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$

$c(x_1) = c(z_2) = 3$

$c(w_i, x_j) = 1, \text{ for all } w_i \in W \text{ and all } x_j \in X,$

$c(y_i, z_j) = 1, \text{ for all } y_i \in Y \text{ and all } z_j \in Z$

$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$

$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$

Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints.

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i + 1$ or Stone $i + 2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] — H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

Which of the following is a valid recurrence for dp[i]?

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i + 1$ or Stone $i + 2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] — H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i + 1$ or Stone $i + 2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] — H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

Consider the following process. At all times you have a single positive integer $x$, which is initially equal to 1 . In each step, you can either increment $x$ or double $x$. Your goal is to produce a target value $n$. For example, you can produce the integer 10 in four steps as follows:

$1 \xrightarrow{+1} 2 \xrightarrow{\times 2} 4 \xrightarrow{+1} 5 \xrightarrow{\times 2} 10$

Obviously you can produce any integer $n$ using exactly $n - 1$ increments, but for almost all values of $n$, this is horribly inefficient.

Based on the above data, answer the given subquestions.

Consider the following process. At all times you have a single positive integer $x$, which is initially equal to 1 . In each step, you can either increment $x$ or double $x$. Your goal is to produce a target value $n$. For example, you can produce the integer 10 in four steps as follows:

$1 \xrightarrow{+1} 2 \xrightarrow{\times 2} 4 \xrightarrow{+1} 5 \xrightarrow{\times 2} 10$

Obviously you can produce any integer $n$ using exactly $n - 1$ increments, but for almost all values of $n$, this is horribly inefficient.

Based on the above data, answer the given subquestions.

Consider the following process. At all times you have a single positive integer $x$, which is initially equal to 1 . In each step, you can either increment $x$ or double $x$. Your goal is to produce a target value $n$. For example, you can produce the integer 10 in four steps as follows:

$1 \xrightarrow{+1} 2 \xrightarrow{\times 2} 4 \xrightarrow{+1} 5 \xrightarrow{\times 2} 10$

Obviously you can produce any integer $n$ using exactly $n - 1$ increments, but for almost all values of $n$, this is horribly inefficient.

Based on the above data, answer the given subquestions.

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Suppose Alice has two heaps of sizes one and five, and Bob has one box with three heaps of sizes 1, 3, and 5 respectively. Can Bob pick a heap to ensure a win?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Suppose Alice has five heaps of sizes 1, 2, 3, 4, 5, and Bob has two boxes: one with three heaps of sizes 6, 7, 8, and another one with two heaps of sizes 9 and 10. Can Bob pick one heap from each box to ensure a win?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Suppose Alice has two heaps of the same size. Who wins in this setting?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Suppose Bob has $b$ boxes. Let $S_i$ denote set of heap sizes in the $i$-th box. Let $S$ denote the set of heap sizes that Alice has. Interpret each heap size as a 10-length bit vector (adding leading zeroes as necessary) based on the binary representation of the number: for example, a heap of size $5$ would be $\langle 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 \rangle$. Therefore, all heap sizes are elements of the vector space $\mathbb{F}_2^{10}$, where $\mathbb{F}_2$ is the field over two elements $\{0, 1\}$ with the operation being addition modulo two. If Bob selects heaps with sizes $h_i \in S_i$ and these choices guarantee a win for Bob, then the set $\{h_i \quad 1 \leqslant i \leq b\} \cup S$ is:

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Let $b$ be a positive integer. For this question, we refer to the numbers $\{1, \ldots b\}$ as colors.

Consider the following set system $(U, \mathcal{F})$:

• the universe $U$ is a set of numbers, and each number is colored with a color from $\{1, \ldots, b\}$, and
• a subset $S \subseteq U$ belongs to $\mathcal{F}$ if and only if $S$ contains exactly one element of $U$ of each color.

For example, if $b = 2$ and $U = \{23, 32, 41, 56, 90, 95\}$, where the odd elements have color $1$ and even elements have color $2$, then the family $\mathcal{F}$ consists exactly of two-sized subsets of $U$ that have one odd element and one even element.

Now, if $b = 3$ and $U = \{11, 22, 33, 44, 55, 66, 77, 88, 99\}$, where the elements $\{11, 22, 33\}$ have color $1$, $\{44, 55, 66\}$ have color $2$, and $\{77, 88, 99\}$ have color $3$, then which of the following sets belong to $\mathcal{F}$?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Consider the set system from the previous question. Does it form a matroid?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Consider a slight modification of the set system introduced earlier. As before, let $b$ be a positive integer. We again refer to the numbers $\{1, \ldots b\}$ as colors.

Consider the following set system $(U, \mathcal{F})$:

• the universe $U$ is a set of numbers, and each number is colored with a color from $\{1, \ldots, b\}$, and
• a subset $S \subseteq U$ belongs to $\mathcal{F}$ if and only if $S$ contains at most one element of $U$ of each color.

Now, if $b = 3$ and $U = \{11, 22, 33, 44, 55, 66, 77, 88, 99\}$, where the elements $\{11, 22, 33\}$ have color $1$, $\{44, 55, 66\}$ have color $2$, and $\{77, 88, 99\}$ have color $3$, then which of the following sets belong to $\mathcal{F}$?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Consider the modified set system from the previous question. Does it form a matroid?

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

The solution that is sought by Bob can be viewed as the problem of finding a largest independent set in the: