• Support PF! Buy your school textbooks, materials and every day products Here!

Question on proofs for a CS related class

  • Thread starter Bensky
  • Start date
  • #1
82
0

Homework Statement


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.


Homework Equations


None that I know of.


The Attempt at a Solution



???
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751
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.
 
  • #3
82
0
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.
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?"
 
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751
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?"
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.
 
  • #5
9
0
Here's a hint:

If you know someone, then they know you.
 
  • #6
2
0
i'll go with NOUSE post
 

Related Threads on Question on proofs for a CS related class

  • Last Post
Replies
1
Views
1K
Replies
3
Views
1K
Replies
1
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
Top