Question on proofs for a CS related class

  • Thread starter Thread starter Bensky
  • Start date Start date
  • Tags Tags
    Class Cs Proofs
Click For Summary

Discussion Overview

The discussion revolves around a homework problem related to proofs in a computer science course, specifically focusing on a scenario involving six people in a room and the relationships among them. The participants explore how to apply the pigeonhole principle to prove that either there are three people who know each other or three who are strangers to each other.

Discussion Character

  • Homework-related
  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • The original poster expresses a lack of experience with proofs and seeks guidance on how to approach the problem, particularly in understanding mathematical rigor.
  • One participant suggests focusing on one person (A) and analyzing their relationships with the other five people to find a group of three who either know each other or do not know each other.
  • Another participant questions the assumption that A knows at least three of the five people, suggesting that it is possible A does not know any of them and asks for clarification on the hint provided.
  • A participant clarifies that the intention is to analyze three people in relation to A, using visual aids like solid or dashed lines to represent known and unknown relationships.
  • Another hint is provided emphasizing the mutual nature of knowing someone, stating that if one person knows another, then the reverse is also true.

Areas of Agreement / Disagreement

Participants express uncertainty about the initial assumptions regarding the relationships among the six people. There is no consensus on how to interpret the hints provided, and the discussion remains exploratory with multiple viewpoints on the problem.

Contextual Notes

The original poster's understanding of mathematical rigor and the pigeonhole principle is limited, which may affect their ability to engage with the problem effectively. The hints provided are based on assumptions that may not be universally accepted by all participants.

Bensky
Messages
82
Reaction score
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



?
 
Physics news on Phys.org
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.
 
LCKurtz said:
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?"
 
Bensky said:
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.
 
Here's a hint:

If you know someone, then they know you.
 
i'll go with NOUSE post
 

Similar threads

Calculus What Is the Best Calculus Book for Self-Learners?
  • · Replies 17 ·
Replies
17
Views
12K
Graduate Question about existence of path-lifting property
  • · Replies 8 ·
Replies
8
Views
3K
Programs At a crossroads between MS in CS or EE
  • · Replies 6 ·
Replies
6
Views
2K
  • Sticky
Math Proof Training Camp and Practice Guidelines
  • · Replies 0 ·
Replies
0
Views
3K
Effects of LLMs on math learning, self taught or otherwise
  • · Replies 10 ·
Replies
10
Views
1K
Book on how to define ideas rigorously
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Need help with a proof involving points on a quadratic
  • · Replies 4 ·
Replies
4
Views
2K
Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
10K
Programs Math classes to supplement CS degree
  • · Replies 2 ·
Replies
2
Views
3K
Algebra Book on how to write proper proofs in Group Theory
  • · Replies 1 ·
Replies
1
Views
2K