Welcome to our community

Be a part of something great, join today!

Simple, fun puzzle

Chris11

New member
Mar 20, 2012
3
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.
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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.
 

Chris11

New member
Mar 20, 2012
3
Yep! That was my solution.