Combinatorics Problem: Box Riddle A huge group of people live a bizarre box based existence. Every day, everyone changes the box that they're in, and every day they share their box with exactly one person, and never share a box with the same person twice.
One of the people of the boxes gets sick. The illness is spread by co-box-itation. What is the minimum number of people who are ill on day n?

Additional information (not originally included in problem):
Potentially relevant OEIS sequence: http://oeis.org/A007843
 A: I used brute forcing, minimizing as possible, until day 20, then I was comfortable enough to try to make an educated guessing about the minimum number of patients on successive days. A pattern emerged quite evidently, and the number was exactly the sequence of oeis.org/A007843. First thing I have noticed, after having all the results of the first 20 days written down, is that whenever the minimum number of patients becomes a power of 2, it becomes clearly obvious how long the containment of illness, in the minimum case, is going to be valid: it is given as $\log_2 x$, where x is the minimum number of patients. So I have rewritten the minimum number of patients in terms of powers of 2 $ (2^0, 2^1, 2^2, 2^2+2^1, 2^3, 2^3+2^1, 2^3+2^2, 2^3+2^2+2^1, 2^4, 2^4+2^1, 2^4+2^2, 2^4+2^2+2^1, 2^4+2^3, 2^4+2^3+2^1, 2^4+2^3+2^2, 2^4+2^3+2^2+2^1, ...).$ Each item in this sequence represents the minimum number of patients at some point in time, in consecutive order. Note that, the exponent of the last term in each item exposes the number of days in which the illness is going to keep contained at the same level exhibited by the item's value, that is (1 patient at Day 0, 2 patients for 1 day, 4 patients for 2 days, 6 patients for 1 day, 8 patients for 3 days, 10 patients for 1 day, 12 patients for 2 days, ...). So the sequence of the successive days starting at Day 0 is (1, 2, 4, 4, 6, 8, 8, 8, 10, 12, 12, 14, 16, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 26, 28, 28, 30, ...) as displayed at OEIS sequence. (I wanted to post this as a comment but it seems that I am not allowed to?)
A: Just in case this helps someone:

(In each step we must cover a $N\times N$ board with $N$ non-self attacking rooks, diagonal forbidden).
This gives the sequence (I start numbering day 1 for N=2) : (2,4,4,6,8,8,8,10,12,12,14,16,16,16)
Updated:  a. Brief explanation: each column-row corresponds to a person; the numbered $n$ cells shows the pairings of sick people corresponding to day $n$ (day 1: pair {1,2}; day 2: pairs {1,4}, {2,3})
b. This, as most answers here, assumes that we are interested in a sequence of pairings that minimize the number of sick people for all $n$. But it can be argued that the question is not clear on this, and that might be interested in minimize the number of sick people for one fixed $n$.  In this case, the problem is simpler, see Daniel Martin's answer.
A: If we want to minimize the number of infected people only after a fixed number $n$ of days -- meaning we do not an answer that is a function of $n$ as $n$ tends to infinity -- then the answer depends on the parity of $n$: for odd $n$, the answer is $n + 1$, while for even $n$ the answer is $n + 2$.
First observe that there cannot be less then $n + 1$ infected individuals at day $n$ since the first infected guy has shared boxes with at least $n$ other indiviuals.
Let us now assume $n$ is odd. Take a set $V$ containing $n + 1$ citizens of the box world (one of them is the infected one). Take a complete graph on $V$. Decompose its edges into perfect matchings $M_1, \dots, M_{n}$. Each perfect matching $M_i$ tells you how the co-box-itation will be at day $i$. Assume people outside of $V$ share boxes only with people outside of $V$ during these $n$ days. This scheme makes everyone in $V$ sick at day $n$ while nobody outside of $V$ is sick at day $n$. 
For $n$ days, with $n$ even, the proof that there can be as little as $n + 2$ infected individuals is similar to the previous paragraph. 
The proof that there cannot be less than $n + 2$ infected individuals is as follows. We already know that, at the end of day $n - 1$, there are at least $n$ infected individuals (because $n - 1$ is odd). If there are precisely $n$, it is because they have shared boxes among themselves during these $n - 1$ days. Since they are not allowed repeat partners, on the $n$-th day, each has to share a box with a non infected individual, which leads to $2n$ infected individuals at the end of day $n$. If there are exactly $n + 1$ infected individuals at the end of day $n - 1$, then it is still possible that some of them share a box on day $n$, but $n$ is even, so one of these $n + 1$ individuals will be forced to share a box with a healthy person.
-- EDITED --
In fact, every complete graph of even order may be decomposed into perfect matchings (see Theorem 3.5 on page 20 of the book One-Factorizations by W. D. Wallis). 
A: Let $f(n)$ be the minimum number of ill people on day $n$ (sequence $1, 2, 4, 4, 6, 8, 8, 8,\ldots$ if we start with $n=0$), let $g(n)$ be the maximal number of days the illness can be kept $\le n$ (sequence $0, 1, 2, 2, 4, 4, 5, 5, 8, 8, \ldots$ if we start with $n=0$), so that $g(n)=\max \{k\mid f(k)\le n\}$ and $f(n)=\min\{k\mid g(k)\ge n\}$ holds.
We want to show for $n\ge 1$ that $g(n)=r(n)+1$ where
$$\tag1 r(n):=\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n4\right\rfloor+\left\lfloor\frac n8\right\rfloor+\ldots$$
is the exponent of $2$ in $n!$.
By inspection, we see that $g(n)=r(n)+1$ holds at least for $n\in\{1,2,3,\ldots,9\}$.
Lemma 0: $f(n)$ is even for $n>0$. If $n>1$ is odd then $g(n)=g(n-1)$.
Proof: Obviously, after patient $0$ being the only ill person inititally, the ill persons come in pairs as per the last box they were in. The statement about $g$ is dual to this.$_\square$
Lemma 1: $f(n+f(n))\le 2f(n)$ and $g(2n)\ge g(n)+n$.
Proof: Make sure that $f(n)$ people are ill on day $n$, enter $f(n)$ fresh people and let them cobox with the first $f(n)$ people in a circular manner fo the next $f(n)$ days. The statement about $g$ is dual to this.$_\square$
Corollary: $g(n)\ge r(n)+1$ for all $n\ge 1$. $f(n)\le \mathrm{A007843}(n)$.
Proof: Observe that $r(2n+1)=r(2n)=r(n)+n$ so that lemmas 0 and 1 make induction on $n$ work. The claim about $f$ is dual (using the description at OEIS).$_\square$
Lemma 2: $g(n)\le n$. 
Proof: Just note that patient 0 cannot coboxitate with more than $n-1$ other people. $_\square$
Corollay: $g(n)=r(n)+1$ if $n$ is a power of $2$.

(to be continued)
