Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Q28

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

share|improve this question
    
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
add comment

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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