Tell me more about Alice and Bob

A while back my parents were in town on a weekend when I was scheduled to give a talk to HS students who had done well on the Maryland math competition. Logistics dictated that my parents goto the talk. (They were both English majors and wouldn't like me using the word `goto' since its not a word. Fortunately they don't read this blog and see what else I do to the English Lang.)
I gave a talk on Communication Complexity (slides are here) where I did the following:

1. I stated the problem: Alice has x, Bob has y, both strings of length n. They want to know if x=y without too much communication.
   
2. I noted that they can easily solve this with n+1 bits of communication and raised the question of Can They Do Better?
   
3. We discussed this. Someone mentioned average case (informally), which helped me clarify the problem. Someone else suggested sending the number-of-1's and if it didn't match they weren't equal, but also noted that if they did--- weren't sure. Most thought that one COULD do better or else I wouldn't be talking about it.
   
4. I tell them that NO you can't do better (I do not prove this).
   
5. I told them about mod arithmetic and how in mod p, p a prime, poly of degree d have at most d roots.
   
6. I presented the O(log n), error 1/n, randomized protocol for equality that uses polynomials mod p.
   
7. I briefly talked about comm complexity in general.
   

The talk went well. It is a good topic for good HS students, and if you want to borrow my slides you can (you may need to update the political reference). Having not understood ANY of the talk Mom had the following question:
MOM: Alice and Bob-- are they married?
BILL: Oh. I'll say no.
MOM: If they are not married then how come they have such a hard time communicating?
DAD: (he didn't say anything but I could tell he agreed).