$n$ and $k$ are positive integers, not necessarily distinct. You are given two stacks of cards with a number written on each card, as follows. Stack A has $n$ cards. On each card a number in the set $\{ 1 , \ldots , k \}$ is written. Stack B has $k$ cards. On each card a number in the set $\{ 1 , \ldots , n \}$ is written. Numbers may repeat in either stack. From this, you play a game by constructing a sequence $t _ { 0 } , t _ { 1 } , t _ { 2 } , \ldots$ of integers as follows. Set $t _ { 0 } = 0$. For $j > 0$, there are two cases: If $t _ { j } \leq 0$, draw the top card of stack $A$. Set $t _ { j + 1 } = t _ { j } +$ the number written on this card. If $t _ { j } > 0$, draw the top card of stack $B$. Set $t _ { j + 1 } = t _ { j } -$ the number written on this card. In either case discard the taken card and continue. The game ends when you try to draw from an empty stack. Example: Let $n = 5 , k = 3$, stack $A = 1,3,2,3,2$ and stack $B = 2,5,1$. You can check that the game ends with the sequence $0,1 , - 1,2 , - 3 , - 1,2,1$ (and with one card from stack $A$ left unused). (i) Prove that for every $j$ we have $- n + 1 \leq t _ { j } \leq k$. (ii) Prove that there are at least two distinct indices $i$ and $j$ such that $t _ { i } = t _ { j }$. (iii) Using the previous parts or otherwise, prove that there is a nonempty subset of cards in stack $A$ and another subset of cards in stack $B$ such that the sum of numbers in both the subsets is same.
$n$ and $k$ are positive integers, not necessarily distinct. You are given two stacks of cards with a number written on each card, as follows.
Stack A has $n$ cards. On each card a number in the set $\{ 1 , \ldots , k \}$ is written.\\
Stack B has $k$ cards. On each card a number in the set $\{ 1 , \ldots , n \}$ is written.\\
Numbers may repeat in either stack. From this, you play a game by constructing a sequence $t _ { 0 } , t _ { 1 } , t _ { 2 } , \ldots$ of integers as follows. Set $t _ { 0 } = 0$. For $j > 0$, there are two cases:\\
If $t _ { j } \leq 0$, draw the top card of stack $A$. Set $t _ { j + 1 } = t _ { j } +$ the number written on this card.\\
If $t _ { j } > 0$, draw the top card of stack $B$. Set $t _ { j + 1 } = t _ { j } -$ the number written on this card.\\
In either case discard the taken card and continue. The game ends when you try to draw from an empty stack. Example: Let $n = 5 , k = 3$, stack $A = 1,3,2,3,2$ and stack $B = 2,5,1$. You can check that the game ends with the sequence $0,1 , - 1,2 , - 3 , - 1,2,1$ (and with one card from stack $A$ left unused).
(i) Prove that for every $j$ we have $- n + 1 \leq t _ { j } \leq k$.
(ii) Prove that there are at least two distinct indices $i$ and $j$ such that $t _ { i } = t _ { j }$.
(iii) Using the previous parts or otherwise, prove that there is a nonempty subset of cards in stack $A$ and another subset of cards in stack $B$ such that the sum of numbers in both the subsets is same.