Math 160 Mathematical Problems and Games, Fall 2002
Problem Set 4: hand in one problem Tuesday, October 15.

Instructions:  Think about all four problems, and come up with some ideas about how to solve them. Then choose one of the problems and write up a careful solution. Your solution should be written so that it would convince a skeptical classmate.

1.  Below is the floor plan of an apartment with two doors to the outside.  Is it possible to enter through the front door, go through each room exactly once, then exit through the back door?


2.   Two people are playing a game on a 3 by 3 board.  They each start with two counters in the corners on their own side of the board.


They take turns moving one counter at a time.  On each move, if the counter is in a corner it can move to either of the opposite edges, and if it is on an edge it can move to either of the opposite corners.


Is there a way that they can end up in the following configurations?


3.  Below is a picture of the town of Konigsberg, Prussia (now Kaliningrad, Russia).  There are seven bridges connecting the two islands in the middle of the river and the sides of the river.  The Swiss mathematician Leonhard Euler (1707-1783) travelled there and wondered if it would be possible for a person to walk around the city and cross each of the seven bridges exactly once.

    
a)  Is this possible?  b) Suppose that the top left bridge in the picture is closed.  Now is it possible?

4.  In a graph, the degree of a vertex is the number of edges that connect to that vertex.  Draw some graphs, and compare these two numbers:  a)  the sum of the degrees of all of the vertices of the graph; b) the number of edges in the graph.  Come up with a rule relating these, and explain why it is true.