Untitled Document

Goal: To model a problem using a vertex-edge graph and solving it using Euler paths and Hamilton circuit

Number of players: 2

 

Materials:

• Student Activity Sheet
• 20 small blue circles
• 20 small red circles
• 20 large blue circles
• 20 large red circles
• ------------------------------------per student
• 15 worksheets with large circle per sheet
• Pencil/pen
• ------------------------------------per pair of students

 

Set-up:

 

• Population 1:

• • Boys (small blue circles)
  • Girls (small red circles)

Setting 1: Kindergarten party table

 

• Population 2:

• • Gentlemen (big blue/red circles)
  • Ladies (small blue/red circles)

Setting 2: Wedding dinner tables

 

 

Instructions:

• Level 1: Kindergarten birthday party

• Divide the small circles between you and your partner so that one takes care of the kindergarten boys (small blue circles) and one takes care of the kindergarten girls (small red circles).
• The big circle on your worksheet represents the party table. Draw in 5 chairs around the table.
• Each partner takes turn in placing a kindergartener on a chair. Girls don’t like to sit next to boys and vice versa. So, avoid placing a girl next to a boy. The person who is unable to seat their kindergartener loses.

 

 

• Try this game using different number of chairs and fill in the table provided in the next page.

 

Example:

 

Trial #	# of chairs	Who made the first move?	Win/ Lose	Comments (Any special moves that you or your opponent made)?
1	8	me	Win	None; just guessed my move

 

While you are playing the games, here are some questions to think about:

Do you notice any patterns?

Can you identify any winning strategies?

 

 

 

Trial #	# of chairs	Who made the first move?	Win/ Lose	Comments (Any special moves that you or your opponent made)?

 

Concluding comments (Any patterns? Winning strategies? Winning moves?):

 

 

 

• Level 2          : Wedding party

• Divide the large circles between you and your partner so that one player has blue couples (large and small blue circles) and one player has red couples (large and small red circles).
• The big circle on you worksheet represents a wedding banquet table. Draw in 10 chairs around the table
• Each partner takes turn in placing a couple (i.e. blue couple, red couple) on the chairs. A blue couple doesn’t like sitting next to a red couple. So, avoid placing a blue couple next to a red couple. The person who is unable to seat their couple loses.

 

 

• Try this game using different number of chairs and fill in the table provided in the next page.

 

Example:

 

Trial #	# of chairs	# of coupled chairs	Who made the first move?	Win/ Lose	Comments (Any special moves that you or your opponent made)?
1	8	4	Win	Lose	Trying the strategy found in level 1

 

Think about these questions as you play:

Do you notice any patterns? If yes, are they the same patterns that you found in Level 1?

Can you identify any winning strategies?

 

 

Trial #	# of chairs	# of coupled chairs	Who made the first move?	Win/ Lose	Comments (Any special moves that you or your opponent made)?

 

Concluding comments (Any patterns? Winning strategies? Winning moves?):

 

 

 

 

 

 

• Level 3          : Wedding party

• The big circle on you worksheet represents a wedding banquet table. Draw in 20 chairs around the table
• Each partner takes turn in placing a couple (i.e. blue couple, red couple) on the chairs. Each individual takes up one seat and each couple has to sit together side by side. A gentleman doesn’t like his partner sitting next to another gentleman (i.e. blue gentleman doesn’t like his partner sitting next to either a red or another blue gentleman. Similarly, red gentleman doesn’t like his partner sitting next to either a blue or another red gentleman.); the gentleman will get jealous if another gentleman sits next to his partner. The person who is unable to seat their couple without a gentleman getting jealous loses.

 

 

 

• Try this game using different number of chairs and fill in the table provided in the next page.

 

Think about these questions as you play:

Do you notice any patterns? If yes, any same patterns as you found in Level 1 or 2? Can you identify any winning strategies?

 

 

Trial #	# of chairs	# of coupled chairs	Who made the first move?	Win/ Lose	Comments (Any special moves that you or your opponent made)?

 

Concluding comments (Any patterns? Winning strategies? Winning moves?):

 

 

 

 

 

 

 

Conclusions & Take home points:

(After teacher discussion)

 

Model used:

 

Goal of the model used:

 

 

 

Winning strategies:

• Level 1:

 

 

 

• Level 2:

 

 

 

• Level 3:

 

 

 

• Common winning strategy:

 

 

 

Take home points on the model used (i.e. What did you learn from this game?):

Can you model the game with a vertex-edge graph? What are your vertices and what are your edges? If yes, how do you use the vertex-edge graph in your model? In other words, what are you trying to do using the vertex-edge graph?

 

 

Teacher Lesson Plan for: Discrete Math—Euler Paths and Hamilton Circuit

Math Game: Kindergarten Cooties & Jealous Gentlemen

 

Game Lesson Length           : 1 hour

Game Type               : Devise Strategies

Grade Level(s)                      : 9-12 grade high school

 

Materials:

• Student Math Game Worksheets
• 20 small blue circles
• 20 small red circles
• 20 large blue circles
• 20 large red circles
• ---------------per student
• 15 worksheets with large circle per sheet
• Pencil/pen
• ---------------per pair of students

 

Learning goals:

• To model a problem using vertex-edge graphs, and solving the problem through

investigation and application of Euler Paths and Hamilton Circuits.

• • Formulating a rule
  • Searching for a pattern
  • Making a hypothesis and testing it

 

NCTM Standards Correlation:

This game satisfies the NCTM Standards for Communication by enabling grades 9-12 students to:

• Organize and consolidate their mathematical thinking through communication.
• Communicate their mathematical thinking coherently and clearly to peers and

teachers.

• Analyze and evaluate the mathematical thinking and strategies of others.

This game satisfies the NCTM Standards for Discrete Mathematics by enabling grades 9-12 students to:

• Understand and apply vertex-edge graph topics including Euler paths, Hamilton

paths, critical paths.

• Understand, analyze, and apply vertex-edge graphs to model and solve problems

related to paths, circuits, networks, and relationships among a finite number of

elements in real-world and abstract settings.

 

Preparation:

• Cut out small and large circles on red and blue construction paper using a dime and a quarter to trace the circles (20 for each student x  #of students).
• Print out 15 worksheets with 1 large circle per page (x  # of student pairs).
• Practice the math game with another person to familiarize yourself with the

concepts before using the game lesson in class.

 

Directions:

• Distribute student worksheets and cut out circles
• Place students in pairs
• Give each pair 15 sheets with circles pre-drawn on them. (5 min for steps 1-3)
• Read over the instructions for Level 1 together (5 min).
• Have students try Level 1 game and walk around to see how they are doing;

ask them questions (15 min).

• Have students move onto Level 2 game (15 min)
• Have students move onto Level 3 game (10 min)
• Distribution “Conclusions & Take home points” sheet and come together to explain

the Euler paths and Hamilton Circuits (10 min)

• Assess the students’ understanding by looking over their “Conclusions & Take home   points” sheet.

 

Discussion and Problem Solution:

This game could be represented as a vertex-edge graph. The vertices represent the seats and the edges connecting two vertices represent the degree of freedom of the opponent’s moves. There are two goals of each move: (1) To connect all possible vertices (2) To minimize the degree of freedom (DOF) of the opponent’s moves. An edge can only be drawn to connect two of the same-colored circles. For example: Level 1 game: Let blue make the first move and red make the second move,

 

 

 

Thus, we want to know what the consequences are if we seat a kindergartener in one of the vertices that is part of our aim, i.e. seat #2, #3, #4, #8, #9, #10, #11. If we seat a blue kindergartener in seat #2 then, there are 6 possible seats for our opponent, player #2, to seat a red kindergartener given the constraints; this means that the DOF of the opponent’s moves is 6. Repeating the same logic to seat #3, #4, #8, #9, #10, #11, it is found that the minimum DOF of the opponent’s moves is 4. Thus, the best move would be to seat a kindergartener in seat #8 or #9. Similarly, player #2 will follow the same technique and find that seating a kindergartener in seat #3 will minimize player #1’s moves.

 

Again, follow the same logic finding the opponent’s minimum DOF. In this game, each path is determined by finding the opponent’s minimum DOF. You can picture each value of DOF as the cost of traveling the Euler path.

After several repetitions, you can find that there is first-move advantage for odd number of chairs and second-move advantage for even number of chairs. The same strategy could be use to tackle level 2 and level 3 of this game. However, it is important for the students to be able to recognize that a couple can be represented as a single individual with a certain constraints (e.g. the constraint for Level 2 game is that there has to be 2 chairs next to each of the red circle.)

Facilitating questions during game time encourages students to think deeper and develop new strategies:

• Level 1:

Do you notice any patterns?

Can you identify any winning strategies?

Can you model the game with a vertex-edge graph? If yes, how do you use the vertex-edge graph in your model? What are your vertices and what are your edges? In other words, what are you trying to do using the vertex-edge graph?

• Level 2 and 3:

Do you notice any patterns? If yes, any same patterns as you found in level 1? Can you identify any winning strategies?

Can you model the game with the same vertex-edge graph that you used for level 1?

If yes, how do you use the vertex-edge graph for this level? What are your vertices and what are your edges?

If not, what modification did you make to your vertex-edge graph? Did you use a completely different vertex-edge graph?

 

Wrapping up the game:

• Possible questions to ask at the end of the game:
  • What is the common winning strategy?
  • What model did you use?
  • What is your goal by using that model?
  • What did you learn from this game about that model?
  • Do you think you can use the same model for any other application? If yes, give an example!

 

 

Use the “Discussion and Problem Solution” and Examples of answers to the Student Activity Sheet (below) to assess student understanding:

Model used: Vertex-edge graph

Goal of the model used         :

(1) To connect all possible vertices

(2) To minimize the DOF of the opponent’s moves.

Winning strategies:

• Level 1, 2, and 3        common winning strategies:
  • Odd number of chairs: Make the first move to win! (Reason: you basically have more choices to choose from by taking the first move)
  • Even number of chairs: Make the second move to win! (Reason: since you have even number of chairs, there is equal number of choices for both players; thus, seeing your opponent’s move will give you advantage to adjust your strategy.)
  • Minimize the opponent’s DOF.

Take home points on the model used (i.e. What did you learn from this game?):

Vertex-edge graph can be used to model a real situation. In this case, the opponent’s DOF to sit a person in a table under certain constraints can be pictured as the cost to travel through the Euler’s path.

 

This lessons is written by students at Massachusetts Institute of Technology (M.I.T.), as part of their coursework for 11.124, Introduction to Teaching and Learning Science and Math.