5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Not sure if it's implied, but does every one of his 20 friends visit him at least one day? $\endgroup$ – Ivo Beckers Sep 30 '15 at 13:09
  • 2
    $\begingroup$ @IvoBeckers I don't think it matters. If someone doesn't visit on any days, it makes it easier to pick them as one of the $Fi$ values as they will not have visited on either $D1$ or $D2$ $\endgroup$ – Gordon K Sep 30 '15 at 13:21
  • $\begingroup$ @Ivo Beckers: Yes, you may assume that each of the 20 friends visit Halfbrain at least once. (But please check also the comment by Gordon K.) $\endgroup$ – Gamow Sep 30 '15 at 13:54
  • $\begingroup$ @Gamow, there is confusion about your intended interpretation of the problem. May want to check the discussion below The Dark Truth's solution and update the problem from 5 to 8 friends if I am correct? $\endgroup$ – Puzzle Prime Sep 30 '15 at 14:38
  • $\begingroup$ @Gamow, I totally agree with you, but still may be a good idea to explain to the others that {for every x, f(x)=0 or f(x)=1} is not the same as {f(x)=0 for all x or f(x)=1 for all x}? $\endgroup$ – Puzzle Prime Sep 30 '15 at 14:56
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This is essentially Artur Kirkoryan's argument, with some modifications. $\endgroup$ – Julian Rosen Sep 30 '15 at 15:55
  • 1
    $\begingroup$ Using -1 instead of adding the complement vectors makes it a bit shorter, nice. $\endgroup$ – Puzzle Prime Sep 30 '15 at 17:00
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Not only do you use 8 friends rather then 5, but why use 20 people + 20 twins, rather then 10 people + 10 twins to make the total of 20 friends? $\endgroup$ – Tim Couwelier Sep 30 '15 at 13:42
  • $\begingroup$ @TimCouwelier, not really, the days on which the twins visit the professor are strictly determined by the days on which the original friends visit him. I just use the twins in order to reflect on the fact that am allowed to choose a friend which does not visit the professor on both days. $\endgroup$ – Puzzle Prime Sep 30 '15 at 13:46
  • 1
    $\begingroup$ I chuckled at your suggestion that he is right because he is a professor - because of course, they are always right! But good answer. $\endgroup$ – JPhi1618 Sep 30 '15 at 16:02
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You are allowed to pick 5 friends such that every of them either visits him on both days or does not visit him on both days. For example friends 1, 2, 3, 4 visit the professor on both days 1 and 2, and friends 17, 18, 19, 20 do not visit the professor on both days 1 and 2. This makes 8 friends in total. $\endgroup$ – Puzzle Prime Sep 30 '15 at 14:00
  • $\begingroup$ Depends on what Gamow intended with his question $\endgroup$ – The Dark Truth Sep 30 '15 at 14:01
  • $\begingroup$ I'm pretty sure he meant the other version, but your example is nice since combined with my proof gives the exact bound of 8 friends. $\endgroup$ – Puzzle Prime Sep 30 '15 at 14:02
  • 3
    $\begingroup$ If @Gamow wanted to interpret it in your ways guys, he should have written "there exist 5 friends such that either each of them visited the professor on both days or neither of them visited the professor on both days". In the original variation first you pick a friend and then determine whether he visits on both days or on neither of them, not vice-versa. $\endgroup$ – Puzzle Prime Sep 30 '15 at 14:07
  • 1
    $\begingroup$ @ArturKirkoryan aah, I finally see what you mean. At first I didn't understand what your interpretation actual was, but now I do. I guess you made a valid point $\endgroup$ – Ivo Beckers Sep 30 '15 at 14:10
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.