# If Bob and Alice never met in class, at least one of them missed at least half of the classes

Alice opened her grade report and exclaimed, "I can't believe Professor Jones flunked me in Probability." "You were in that course?" said Bob. "That's funny, i was in it too, and i don't remember ever seeing you there." "Well," admitted Alice sheepishly, "I guess i did skip class a lot." "Yeah, me too" said Bob. Prove that either Alice or Bob missed at least half of the classes.

Proof:

Let $A$ be the set of lectures Alice attended and missed, let's assume she attended them in no particular order, similarly for Bob $B$ is the set of all lectures Bob attended and missed in random order. Let $f$ be one-to-one and onto, we define $f:A\to B$ to be the mapping that matches the lectures Alice attended to the lectures that Bob missed and the lectures that Alice missed to the ones that Bob attended. If we consolidate the contiguous entries in the sets $A$ and $B$ into two groups, the group of lectures that Alice attended and the group of lectures she didn't attend and similarly for $B$ then the function $f$ can only be one-to-one and onto if both Alice and Bob attended the same number of lectures they missed.

I understand i've shown that Bob and Alice missed half the classes, how do i show that they could've missed more with this method??

-
Why do you finish with "one-to-on and onto"? –  Hagen von Eitzen Dec 27 '13 at 10:37
That's why i want verification for my proof?? –  pkjag Dec 27 '13 at 10:50
@pkaj: I apologize to ask but what is the name and publisher of the text book from which you got this question? –  Nick Dec 27 '13 at 12:39
The all famous Intro to proofs: How to prove it by Daniel J. Velleman published by Cambridge University Press –  pkjag Dec 27 '13 at 12:43

I'm not sure if this is what you're looking for, but why not use the pigeonhole principle?

Let $L_n$ represent the $n$th lecture. During $L_1$, either Bob or Alice attended, or neither attended. During $L_2$, either Bob or Alice attended, or neither attended. This is true for every lecture up to $L_n$.

Now, we know every lecture had to have been missed, by either Bob or Alice or both. Then there are at least $n$ non-attendances/objects that need to be distributed amongst two "bins", let's label them Bob and Alice. Just for clarity, if both Bob and Alice miss, let's say that counts as two non-attendences.

If the number of total absences is odd, then we have at least $n$ (where $n$ is the total days in the class) non-attendences to distribute into two boxes, since the most optimistic case assumes either Alice or Bob attends class every day. Since the number of total absences is odd, the absences cannot be distributed into the two boxes evenly and someone must have missed more than half the class.

If the number of total absences is even, then we have at least $n$ non-attendences to distribute into two boxes. Since the number of total absences is even, they can be evenly distributed between two boxes. However, they do not need to be distributed this way. One box could very well have more than the other, so long as they add up to the total number of absences.

Therefore, one person must have missed at least half of the lectures.

-
How come you assume that every lecture was attended by either Alice or Bob when we clearly know that both of them skipped class alot? –  pkjag Dec 27 '13 at 12:10
I addressed that in the last paragraph. It doesn't matter if they collectively attended all the lectures or not. The argument still holds. I'll reformulate my argument a bit. –  Josh Infiesto Dec 27 '13 at 12:13

Suppose, to the contrary, that neither Alice nor Bob missed at least half of the classes. Hence, both must have attended more than half of the classes.

Then clearly, out of the $n \geq 1$ classes total, it cannot be the case that Alice and Bob were never in the same class.

Why? More than half of the classes were attended by Alice. Hence, in order for Bob to have never attended a class that Alice has attended, he can at most have attended less than half of classes. But this in contradiction to the assumption that Bob has attended more than half of the classes.

-
Nicely done. I think this is prettier than mine. –  Josh Infiesto Dec 27 '13 at 12:27
Yeah its short but i wanted a proof without contradiction –  pkjag Dec 27 '13 at 12:31

Let $n$ be the total number of lectures, $n_{Ab}$ the number of lectures Alice attended and Bob didn't, $n_{aB}$ the number of lectures Bob attended and Alice didn't, $n_{AB}$ the number they both attended and $n_{ab}$ neither of thenm attended. Then $n=n_{ab}+n_{aB}+n_{Ab}+n_{AB}$ and Alice missed $n_{ab}+n_{aB}$, Bob missed $n_{ab}+n_{Ab}$. If we assume $n_{ab}+n_{aB}<\frac n2$ and $n_{ab}+n_{Ab}<\frac n2$, then $$n_{ab}-n_{AB}=(n_{ab}+n_{Ab})+(n_{ab}+n_{aB})-(n_{ab}+n_{aB}+n_{Ab}+n_{AB})<0.$$ This is only possible if $n_{AB}>0$, but they say they never met.

-
If $n_{AB}\gt n_{ab}$ how do you show that they missed each other when the classes they both attended are more than the ones they missed –  pkjag Dec 27 '13 at 11:57

Let $n$ be number all lectures.

Let $k$ be number of the lectures that Bob missed. if $k<n/2$ then $-k>-n/2$

Let $m$ be number of the lectures that Alice missed.Then $m>=n-k>n/2$

-
How can $n-k$ be the number of lectures Bob and Alice missed when you've already defined $n$ to represent that?? –  pkjag Dec 27 '13 at 10:49
I made ​​a mistake. I righted –  nadia-liza Dec 27 '13 at 10:53
I don't think this is right. I don't think you're counting the lectures correctly. Bob and Alice could both be missing from the lectures. If you subtract the number of lectures missed by Bob, you're also subtracting the number of lectures missed mutually by Bob and Alice. Even then, doesn't this just show that of the missed lectures someone had to have missed at least half of the missed lectures? –  Josh Infiesto Dec 27 '13 at 11:27
Your answer assumes that the attendance of lectures by Bob and Alice is mutually exclusive –  pkjag Dec 27 '13 at 12:14

Let $C$ be the finite set of lectures.
Let $A\subseteq C$ be the set of lectures attended by Alice.
Let $B \subseteq C$ be the set of lectures attended by Bob.
The intersection of $A$ and $B$ is empty since Alice and Bob never meet in a lecture. We want to show that $|A|+|B| \le |C|$

Proof:
By Problem 8 (b) (pg 313 of Velleman's book), $A$ and $B$ are both finite.
Then, $|A| + |B| = |A \cup B|$ by Theorem 7.1.7 (Velleman).
And, $|A \cup B| \leq |C|$ by Problem 8 (b) (Velleman).

-
I just edited your question to make use of MathJax. However, I don't quite follow how $|A|+|B|\leq |C|$ implies the answer to the question. How is this? –  apnorton Sep 11 '14 at 22:35
We want to show |A|=<|C|/2 or |B|=<|C|/2 i.e., either Alice or Bob or both attended at most half the lectures. Assume that this is not the case, then |A|>|C|/2 and |B|>|C|/2, and |A|+|B|>|C|/2+|C|/2 = |C|. But we proved the opposite above. Hence, |A|=<|C|/2 or |B|=<|C|/2. BTW, sorry for the poor formatting. I need to figure out how to use MathJax. –  Alex Sep 14 '14 at 22:31
Ah - thanks for the explanation. –  apnorton Sep 15 '14 at 14:00