Six days of illness (Part 1)

Question

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 1

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

Answer 2

OF COURSE HE IS RIGHT, HE IS A PROFESSOR.

---

We will prove the problem for 8 friends instead of 5 and see that this is the optimal bound.

Proof.

Let us imagine that each of the professor's friends has a twin who visits him on the days when the sibling does not. Then we have $40$ people in total and every day exactly $20$ of them visit the professor. Now if we prove that there exist days $D_1, D_2$ and $8$ people who have visited the professor on both days $D_1$ and $D_2$, then the problem will be solved. Indeed, it is impossible that we choose both twins of a pair in these $8$ people, because at most one of them can visit the professor on both days. If some of these $8$ people are not the professor's friends, just exchange them with their twins and we are done.

Next, let us label the friends and their twins with #1, #2, ... , #40 such that #j is the twin of #(j+20).

For each $i\leq 6$, denote with $x_i$ the $40$-dimensional vector

$$x_i=(\delta_{i,1}, \delta_{i,2}, ... \delta_{i,40}),$$ where $\delta_{i,j}$ is $1$ if person #j visited the professor on day i and $0$ otherwise. If we assume that no $8$ people visited the professor on the same 2 days, we have $\langle x_k, x_l\rangle \leq 7$ for all pairs $(k,l)$, where $\langle \cdot, \cdot \rangle$ is the regular scalar product.

Now we have $$\langle V, V\rangle=\langle \sum_{i\leq 6} x_i, \sum_{i\leq 6} x_i \rangle = \sum_{i \leq 6} \langle x_i,x_i\rangle + \sum_{i\neq j} \langle x_i, x_j \rangle \leq 6.20+30.7=330.$$

Let $V=(V_1, V_2,...,V_{40})$. For every $j\leq 20$ we have $V_j + V_{j+20}=6$ and therefore $V_j^2+V_{j+20}^2\geq 18$. Therefore

$$\langle V, V \rangle = \sum_{j\leq 40}V_j^2 \geq 20.18=360,$$

which gives us a contradiction.

In order to see that $8$ friends is optimal, just consider the following example courtesy of @The Dark Truth (may want to upvote him as well for this):

1111 1111 1100 0000 0000

1111 0000 0011 1111 0000

1000 1110 0011 1000 1110

0100 1001 1010 0110 1101

0010 0101 0101 0101 1011

0001 0010 1100 1011 0111

Answer 3

Professor Erasmus is wrong

Proof by Example:

|  D   Friends--------------->
|  a
|  y
\/ s

1111 1111 1100 0000 0000
1111 0000 0011 1111 0000
1000 1110 0011 1000 1110
0100 1001 1010 0110 1101
0010 0101 0101 0101 1011
0001 0010 1100 1011 0111

I did this by stating all 20 permutations of exactly 3 visits on 6 days.
You will find no 2 days with either more than 4 Friends visiting or more than 4 friends not visiting.

Answer 4

The professor is right!

The Dark Truth has a very nice grid, so we'll start with that:

1111 1111 1100 0000 0000
1111 0000 0011 1111 0000
1000 1110 0011 1000 1110
0100 1001 1010 0110 1101
0010 0101 0101 0101 1011
0001 0010 1100 1011 0111

Since we can take the visits each day as a binary value, we can do bit mappings across days to get repeat visitors.

Now, let's take a 2 day period and assume there are 0 repeats. A third day would have a total of 20 repeats split between the first two days.

0101 0101 0101 0101 0101
1010 1010 1010 1010 1010
xxxx xxxx xxxx xxxx xxxx

Let's take another 2 day period and assume there are 4 repeats. A third day could not have the 4 repeats, but instead would have a total of 16 repeats split between the first two days.

0000 0101 0101 0101 0101
0000 1010 1010 1010 1010
1111 xxxx xxxx xxxx xxxx

So, if anything, the professor was being too conservative with how many repeat showings/not showings there were.