mathematics - Six days of illness (Part 1)

Professor Halfbrain was severely ill last week, and he had to spend the six days from Monday till Saturday in the hospital. Luckily he has fully recovered by now. He told us that on each of these six days of illness he was visited by some of his 20 closest friends; and of course many of these friends visited him more than once. Professor Erasmus thought about this for some time, and then told me:

"No matter how and when and how often these 20 friends were visiting Professor Halfbrain on these six days of illness, one will be able to pick two days $D_1$ and $D_2$ and pick five friends $F_1,F_2,F_3,F_4,F_5$, such that the following holds for each friend $F_i$ with $1\le i\le5$: $F_i$ has either visited Halfbrain on both days $D_1$ and $D_2$, or $F_i$ has visited Halfbrain neither on day $D_1$ nor on day $D_2$."

Is this statement correct, or has professor Erasmus once again made a mathematical blunder?

Answer

Professor Halbrain

is correct. In fact, we can find eight friends satisfying the given condition.

Call the six days $D_1,\ldots,D_6$, and number the friends $1,\ldots,20$. For $i=1,2,\ldots,6$, let $x_i$ be the the vector whose $j$-th component ($j=1,2,\ldots,20$) is $1$ if friend $j$ visited Halfbrain on $D_i$, and $-1$ otherwise. Let $\langle\cdot,\cdot\rangle$ denote the usual scalar product of vectors.

For each $i,j$, let $A_{ij}$ be the number of friends who visited Halfbrain on both $D_i$ and $D_j$, or neither $D_i$ nor $D_j$. We have $\langle x_i,x_j\rangle=A_{ij}-(20-A_{ij})=2A_{ij}-20$, and in particular $\langle x_i,x_i\rangle=20$. Now: $$ 0\leq\left\langle \sum_i x_i,\sum_i x_i\right\rangle = \sum_{i}\langle x_i,x_i\rangle+\sum_{i\neq j} \langle x_i,x_j\rangle\leq 6\cdot 20+30\cdot\max_{i\neq j}\big(2A_{ij}-20\big). $$ This means there must be some $i\neq j$ with $2A_{ij}-20\geq -4$, or equivalently $A_{ij}\geq 8$. So there are $8$ friends who either visited Halfbrain both on $D_i$ and $D_j$, or neither on $D_i$ nor $D_j$.