# 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

-
+1 for "co-box-itation" -- though since "cohabitation" involves sharing a habitat, it should perhaps be "coboxion" -- on the other hand, "box" is derived from Late Latin "buxis", so perhaps it should be "cobuxitation"... –  joriki Jan 20 '13 at 14:15
@joriki: We could take it back even further, to Hellenistic Greek πυχίς, and make it copyxitation. Especially if we were well and truly (co)pixilated. –  Brian M. Scott Jan 20 '13 at 21:42
If you two philologists have quite finished, I suggest "boximity" as the snappy solution. –  TonyK Jan 21 '13 at 20:38
I'd suggest an alternative statement (more simple and attractive for me) : A chess tournament has one match per day; each day, each player must play a game with a new opponent. New players can be added, but cannot be removed. What is the minimum number of players needed? –  leonbloy Jan 24 '13 at 1:48
@leonbloy: This is a good translation with a small rephrasing: A chess tournament has one match per day for each player; each day, each player must play a game with a new opponent. New players can be added, but cannot be removed. New players are added as few as possible (i.e., New players are added in such a way that preserves the total number of players as minimum as possible.) What is the number of players on day n? –  John S. Jan 24 '13 at 7:41
show 12 more comments

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?)

-
How exactly did you brute force this? I ask because of the finiteness/infiniteness deal with the population. I originally though that if we took a large enough population $K$ and used it to compute $n$, with $K >> n$, then it wouldn't matter. But maybe it will, since the non-sick people who coboxitate with a non-sick person won't ever be able to coboxitate with that person again.. So a finite population would eventually stall to a point where one individual (or even all of them) has no possible pair left.. –  Pedro Jan 22 '13 at 22:04
I simply assumed an infinite population, since the statement of the problem didn't explicitly impose limits on the number of people, nor the number of boxes. –  John S. Jan 22 '13 at 22:52
@Pedro At each stage you need only follow the infected persons and their new coboxitants. You may assume safely that these new persons have never coboxitated with any of the other finitely many people in focus, i.e. you can generate them as "new" people onyl as needed. The word "huge" in the problem description seems to allow the assumption of an infinite (or at least a sufficiently large) population. –  Hagen von Eitzen Jan 25 '13 at 6:53

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).

-
This is similar than my initial approach, but it's wrong. (for $n=5$ the right answer is 8). –  leonbloy Jan 24 '13 at 1:54
How come the answer is not $6$ for $n = 5$? Suppose $1$ is sick. Setup the boxes as follows: day $1$: $\{1, 6\}, \{2, 5\}, \{3, 4\}$ day $2$: $\{1, 2\}, \{3, 6\}, \{4, 5\}$ day $3$: $\{1, 4\}, \{2, 6\}, \{3, 5\}$ day $4$: $\{1, 3\}, \{2, 4\}, \{5, 6\}$ day $5$: $\{1, 5\}, \{2, 3\}, \{4, 6\}$ This way there are only $6$ infected individuals after $5$ days. –  Daniel Martin Jan 29 '13 at 21:36
Yes, but you had 6 sick people by day 3 which is suboptimal (the mininum is 4). Which begs an interesting and important issue (what means to havea mininum number of sick people for each n) –  leonbloy Jan 29 '13 at 22:07
Of course, upon your understanding of the problem (that you rightly explain in your first paragraph) you are right. It's just that I don't think that the OP pointed to this - but I agree it's ambiguous. –  leonbloy Jan 29 '13 at 22:15

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.

-

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)

-