1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question on proofs for a CS related class

  1. Apr 5, 2010 #1
    1. The problem statement, all variables and given/known data
    As a background to this...I have no experience with proofs at all. I did not take a formal geometry class in high school (took a shortened summer course that gave a VERY brief overview of proofs) and have not gotten to discrete math in university, so I really do not know how to approach/write proofs.

    At the top of my homework, it says: "For each problem solution, attempt to adhere to mathematical rigor. Proofs and arguments should be detailed and complete." I've never heard of mathematical rigor and after looking it up I still don't really know how to "conform" to it. Seems like it's some kind of standard for proofs.

    Here is one of the questions for my HW:
    "Six people enter a room. Either there are three people who know each other or there are three people who are strangers to each other.

    Prove the above statement. Where does a variant of the pigeonhole principle come in?"

    I don't quite know where to start - I looked up the pidgeonhole principle and didn't really understand how it applies to this problem. Maybe someone can point me in the right direction as to how to write a proof for this problem?

    This HW is due Thursday at 11:59 PM EST, help before then is very appreciated.

    2. Relevant equations
    None that I know of.

    3. The attempt at a solution

  2. jcsd
  3. Apr 6, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hint: Think of the 6 people sitting around a table. Focus on one of them, call him A. Since he sees 5 people, there must be three he either knows or doesn't know. (There coudn't be just two of each). Examine that situation a little further.
  4. Apr 6, 2010 #3
    I'm still not quite understanding - isn't it possible that he doesn't know all 5 of them and is simply in the same room with random people? Do you mean "AT LEAST 3 he either knows or 3 he doesn't know?"
  5. Apr 7, 2010 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes that's what I mean. So you can pick 3 to go with A. Analyze them; try drawing solid or dashed lines for know, don't know and see what happens.
  6. Apr 7, 2010 #5
    Here's a hint:

    If you know someone, then they know you.
  7. Apr 7, 2010 #6
    i'll go with NOUSE post
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook