Problem of the Week-4: Spies and Acquaintances

A government agent gives you the following information, then he has a question for you. The information he gives is this:

"We have captured several people whom we suspect are part of a spy ring. For security reasons I will identify them as A,B,C,D,E,F and G. We have interrogated all 7. A admits to having met the other 6. B admits to having met 5, C to having met 4, D to having met 3, E having to met 2, F having met 2, and G to having met 1. None of them would identify whom they knew, but at least we got the numbers out of them. No spy would claim to have met more people than he has actually met, since the interrogation would then be very hard on him if he could not come up with critical information. Our lie detectors are hard for most people to fool, so normally we would think they are all telling the truth".

Question: Could they be all telling the truth? Explain.

Submit your answers (by e-mail or hard copy) before 4 pm on 10/22/04 to Noah Aydin.

Mathematics Dept.