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

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.
