Prove Every Room w/ Odd Doors in House Has a TV Set - H for American Buyer

  • Context: MHB 
  • Thread starter Thread starter Chris11
  • Start date Start date
  • Tags Tags
    Fun Puzzle
Click For Summary
SUMMARY

The discussion centers on proving that in a house with only one entrance and rooms connected by doors, at least one room with an odd number of doors contains a TV set. The solution utilizes the Handshaking lemma, which states that in a finite graph, the sum of the degrees of all vertices must be even. Since the garden (the entrance) has an odd degree, at least one room must also have an odd degree, ensuring the presence of a TV set in that room. Thus, the American buyer will find a TV set upon evaluation.

PREREQUISITES
  • Understanding of graph theory concepts, specifically vertices and edges.
  • Familiarity with the Handshaking lemma in graph theory.
  • Basic knowledge of finite graphs and their properties.
  • Concept of degree of a vertex in graph theory.
NEXT STEPS
  • Study the Handshaking lemma in detail to understand its applications in graph theory.
  • Explore properties of finite graphs and their implications in real-world scenarios.
  • Learn about Eulerian paths and circuits in graph theory.
  • Investigate other proofs involving odd and even degrees in graph structures.
USEFUL FOR

This discussion is beneficial for mathematicians, computer scientists, and anyone interested in graph theory, particularly those exploring proofs and properties related to vertices and edges in finite graphs.

Chris11
Messages
26
Reaction score
0
Let H be a house with only one entrence. Assume that between any two rooms in the house there can only be at most one door. The owner's of this house, keen on selling to an American buyer, decide to place a TV set in every room with an odd number of doors.

Prove that the the American will be able to find a TV set when he comes to evaluate the house.
 
Mathematics news on Phys.org
Chris11 said:
Let H be a house with only one entrence. Assume that between any two rooms in the house there can only be at most one door. The owner's of this house, keen on selling to an American buyer, decide to place a TV set in every room with an odd number of doors.

Prove that the the American will be able to find a TV set when he comes to evaluate the house.

Hi Chris11, :)

I think we can use the Handshaking lemma to solve this problem. Suppose every room in the house has even number of doors. Represent rooms by vertices and doors by edges and we get a finite graph (since the number of rooms should be finite). We shall consider the garden (outside) also as a vertex. The "garden vertex" has degree 1 (only one entrance), and all the other vertices have even degrees. According to the Handshaking lemma this cannot happen. Therefore there should be at least one vertex (a room) except the "garden vertex" with odd degree (odd number of doors). This room contains a TV and if the buyer walks into each room he should find this.

Kind Regards,
Sudharaka.
 
Yep! That was my solution.
 

Similar threads

Schrödinger's Cat: A Thought Experiment on Quantum Mechanics
  • · Replies 6 ·
Replies
6
Views
3K
At a crossroads (drop out? chase a dream? time out?)
  • · Replies 13 ·
Replies
13
Views
5K
Mathematica This Week's Finds in Mathematical Physics (Week 230)
  • · Replies 1 ·
Replies
1
Views
3K
Mathematica This Week's Finds in Mathematical Physics (Week 230)
  • · Replies 1 ·
Replies
1
Views
4K