The assignment below is due BEFORE CLASS on Tuesday, October 12th (it is essential that you complete it before class, as we will be doing a class activity building on the assignment).
We are going to play a game creating walking tours of cities with bridges. We begin in the city of King’s Mountain, which is built on four land masses – both shores of a river and two islands in midstream – connected by a total of seven bridges (shown in green).
EXAMPLE 1: Can you create a walking tour of the city that crosses every bridge exactly once? You can begin anywhere you like, and end anywhere you like, as long as you cross each bridge just once.
Background – Graph Theory
We can simplify the picture of King’s Mountain to make it easier to deal with:
The key elements of the map are the four land masses (let’s label them A, B, C, and D) and the seven bridges (p,q,r,s,t,u and v) (thanks to mathisfun.com for the images):
For the purposes of our problem, we can simply think about each land mass as a point (A, B, C, and D), and the bridges as lines connecting the points (p,q,r,s,t,u and v) – like this:
We call this kind of picture a graph – the points are called vertices and the the lines are called edges. Our goal of finding “a walking tour that crosses each bridge once” is now matter of tracing out all the edges without lifting our pencil (and without repeating any edge).
Assignment, Due Tuesday 10/12 (beginning of class)
Warm up (This Warm Up is just for practice – you do NOT need to submit your answers – see below for the four-part Assignment to be submitted). The following examples build on the example above.
EXAMPLE 2: If you are given the freedom to build one new bridge in King’s Mountain (“make one new edge in the graph”), can you do it in such a way the walking tour becomes possible? Do it!
EXAMPLE 3: If you are given the freedom to destroy one bridge (“erase one edge”), can you do it in such a way that the walking tour becomes possible? Do it!
EXAMPLE 4: Construct walking tours for each of the following graphs (or decide if it is impossible).
Assignment. Your assignment has 4 parts.
PART 1. For each of the four graphs below (G1 – G4), decide whether it is possible to create a walking tour crossing each bridge exactly once. Post your solutions here (TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER). If it is not possible to create a create a solution, say so!
PART 2. Challenge your friends: Now it’s up to you to build your own graph, and challenge your classmates to construct a walking tour (or to determine if it is impossible). It can consist of as many points as you wish, and as many bridges (edges) connecting them. You MUST label your points “A, B, C…” etc. When you’re finished, decide for yourself if a walking tour crossing each bridge exactly once is possible. Remember, the most challenging puzzles are the ones where the answer is difficult to determine. Post two puzzles in the comments. See the note “POSTING YOUR PUZZLE ONLINE” below for instructions on how to draw and share graphs online.
PART 3. Solve a friend’s puzzle. Leave a response to a friend’s posted puzzle, giving a solution. TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER.
Example:
Here is a puzzle: http://sketchtoy.com/67467551
Here is a solution: (start at A) – A, B, D, A, E, B, C, E
PART 4. The last part of your assignment is to write a short paragraph (at least 3 sentences) responding to the following prompt. Be sure to respond to each part:
Writing Prompt: Did you enjoy this assignment? Why or why not? Describe a connection between this assignment and our work in the class. (If you don’t believe there is a connection, try to imagine why we are doing this). Leave your response in the comments.
POSTING YOUR PUZZLE ONLINE. I recommend the site sketchtoy.com – it allows you to draw something, then click “SAVE” and get a link to your drawing. If you have another (free) solution that you’d like to use, that’s fine! You can post the link in a comment, and we’ll be able to click on it and view your drawing. Don’t worry if it’s not pretty! For example, here is a graph that I drew (can you find a walking tour that crosses all edges?): http://sketchtoy.com/67467556
Part 1.
G1: F –> G –> H –>B –>I–> A –>B–>C –>I –>H –>C –>D –>G–>E –>F –>D –>E
G2: E –> F –> C –> D –> E –> B –>F –> A –> B –>C
G3: J –> I –> B –> J –> A –> B –> C –> D –> H –> E –> F –> G –> E –> D –> G –> H –> I
–> I –> C –> J
G4: E –> B –> F –> C –> B –>A –> D –> E –> F –> A
Part 2.
http://sketchtoy.com/70193302
http://sketchtoy.com/70193330
Part 3. To do
Part 4. I enjoyed this assignment for the most part because it was like solving a puzzle. However with a traditional floor-type puzzle, I know each piece connects to another. I wish I knew if there really weren’t a solution to G1 and G4. It was fun because it was like trying to get through a maze, or find a solution to something that you are fairly confident there is an answer to. Like our work in class, and the idea that some sets require us to only use one element once to create a list, this assignment connects to it by only allowing us to cross a bridge only once. It seems easier with sets because we can see our choices easier – all lists are written linearly or horizontally – whereas the bridge problems or even with part 1 they are more complex in the design. Conceptually it is challenging to remember the pattern traversed with the bridge problems whereas at least with the sets/classwork we can more clearly retrace our “steps”. I wonder if I would find it easier if we were asked to write our lists in a different pattern (vertically, or even if we were used to reading another language that is read right to left).
I worked on your first sketch. and found there would be a solution if I were able to count the point at the middle bottom base of where triangle ABC intersects the other two triangles.
PART 1.
G1- E,G,D,F,E,D,C,I,B,H,C,B,A,I,H,G,F
G2- C,F,B,C,D,E,B,A,F,E
G3- E,H,D,G,E,D,C,J,B,I,C,B,A,J,I,H,G,F,E
G4- NO SOLUTION
PART 2. ONE OF THESE DOESN’T HAVE A SOLUTION
http://sketchtoy.com/70194491
http://sketchtoy.com/69357854
PART 3.
COMMENT ON CLASSMATE’S PUZZLE
PART 4.
I enjoyed this assignment. I like problem solving, patterns & puzzles which I could see presented in this activity. It relates in that each patterns, solution, or lack thereof followed a sequential pattern . In coming up with a puzzle you had to problem solve and decide if it had a solution or not.
I tried the first one! B, A, F, B, A, D, E, C, D, E, F, C, B, E.
for the first one
D-A-B-F-A-B-E-F-C-B-E-D-C
for the first one
D-A-B-F-A-B-E-F-C-B-E-D-C
Part 1:
G1) E > G > D > F > E > D > C > B > X > C > H > X > I > B > A > I > H > G > F
G2) C > F > B > E > F > A > B > C > D > E
G3) G > F > E > H > D > G > E > D > C > B > X > C > I > X > J > B > A > J > I > H > G
G4) can’t be solved
Part 2: I’ll post in a second post since I have the link’s saved on my phone
Part 2:
http://sketchtoy.com/70196174
http://sketchtoy.com/70196202
Part 3: Figuring out how to do this
Part 4: I really enjoyed this assignment because it made me think of the realm of solutions to a given problem in a way that I have never thought about before. In this class, we learn how to solve problems through logical connections of different pieces and this exercise was a great visual to show the applications aside from just letters and numbers.
Part 1:
G1)
G2)E>D>C>F>B>E>F>A>B>C
G3)C>D>G>F>E>H>G>E>D>H>I>J>A>B>I>C>J>B>G
G4) No solution
Part 2:
https://sketchtoy.com/70196413
Part 3: Setsandstripes puzzle had a simple puzzle where point A was connected to point B
Part 4: I really enjoyed this assignment because it really made me think. There were a few moments where I had brain farts but it just made me think harder. This assignment has a connection to proofs and logic because we are the ones whom decide whether the puzzle had a solution or not and had to have a reasoning behind it (ex. Has one path or does not have one path). Also, the puzzles made us think outside the box and greater our memory which i think is important.
http://sketchtoy.com/70196434
Part 3:
PART 1:
G1: E-G-D-F-E-D-C-I-B-H-C-B-A-I-H-G-F
G2: C-F-B-C-D-E-B-A-F
G3: E-H-D-G-E-D-C-J-B-I-C-B-A-J-I-H-G-F-E
G4: no solution
PART2:
http://sketchtoy.com/70196520
http://sketchtoy.com/70196528
PART 3:
I tried Nina’s puzzle. And it was nice.
PART4:
I liked to solve the puzzle/s. The class seems to me to be quite multifarious which I appreciate.
PART 1.
G1- E-G-D-E-F-D-C-H-G-D-C-I-H-B-I-A-B
G2- A-F-B-C-F-E-B-C-D-E
G3- G-F-E-G-H-D-G-E-D-E-H-I-C-D-h-I-J-B-I-C-J-A-B
G4- A-F-B-E-F-C-D-E-D-A
part 2
http://sketchtoy.com/70198917
part 3
nina http://sketchtoy.com/70194491
D-A-B-F-A-B-E-F-C-B-E-D-C
part 4
I did enjoy this assignment where you allow me to be more creative. For this assignment, the same problem can have so many different solutions based on your cognitive thinking depth. This assignment helps me realize that in order to prove something in this class I should take step by step approach. However, the same theory can be proved in multiple different ways just like these puzzles can have so many different unique patterns.