OpenLab #4: Bridges and Walking Tours

The assignment below is due BEFORE CLASS on Thursday, October 11th (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 Thursday 10/11 (beginning of class)

Warm up (This Warm Up is just for practice – you do NOT need to submit your answers – see below for the three-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!Euler Paths G1-G4

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 third 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.  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

 

28 Comments

  1. Donald Young

    G1)  START AT: ED, DC, CB, BA, AI, IB, BH, HI, IC, CH, HG, GD, DF, FG, GE, EF

    G2)  START AT: CB, BA, AF, FC, CD, DE, EB, BF, FE

    G3)  START AT:  ED, DC, CB, BA, AJ, JB, BI, IJ, JC, CI, IH, HD, DG, GH, HE, EF, FG, GE

    G4) START AT:  EF, FA, AB, BF, FC, CB, BE, ED, DA

  2. Donald Young

    file:///var/folders/33/7lkfp88d62b34zzgmt1khwsh0000gn/T/IMG_0195%202.jpg

  3. Donald Young

    The fact that no bridge could not be “walked over” twice is directly connected to what we did in class. I thought it was fun, and strangely addictive. Once you get started, you want to keep on trying. Very cool.

  4. Junior

    Part one

    1) FG, GD, DF, FE, EG, GH, HB, BI, IC, CH,HI, IA, AB, BC, CD, DE

    2) EF, FB, BE,ED,DC, CF, FA, AB, BC

    3)GH, HD, DG, GE, EH, HI, IB, BJ, JC, CI, IJ, JA, AB, BC, CD, DE, EF, FG

    4)I don’t think it is possible to get a solution for the fourth image. I’ve tried but my problem is i cant fit in the line segment through the middle.

    Part3)http://sketchtoy.com/68770532

    Part 4)
    I Enjoyed this assignment a lot. The assignment felt like a game and I love games. I think this assignment is meant to show us that starting at a specific point is important. we need to choose where we start because it can affect the outcome. That relates to proving theorems i think? o.o

    • Jaroslav

      Junior, label the points of your puzzle!

    • Junior

      http://sketchtoy.com/68770662

      I forgot to put in vertices so I redid it. I did not label the vertices by letter but color instead because it seemed easier

    • Junior

      http://sketchtoy.com/68770874

      Solution to Danping Zhong’s puzzle. CA, AD, DB, BE, EC, CB, BA, AE, ED, DC

  5. Jaroslav

    Part one

    1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.

    2) E->D->C->B->A->F->E->B->F->C.

    3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.

    4) The last puzzle has NO solution.

    • Jaroslav E Sykora

      Part one
      1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.
      2) E->D->C->B->A->F->E->B->F->C.
      3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.
      4) The last puzzle has NO solution.

      Part two
      http://sketchtoy.com/68771881
      http://sketchtoy.com/68771892

      Part three
      Concerning Dunping’s solution of https://sketchtoy.com/68770874
      A->B->D->E->C->A->E->B->C->D->A

      Part four
      1. To sharpen our brains
      2. To interact with peers
      3. To love the subject even more

  6. Franklin Ajisogun

    Part One

    G2) CB,BA,AF,FE,EB,BF,FE,CD,DE

  7. Danping Zhong

    PART 1.
    1) E,F.D,E,G,D,C,H,B,C,I,B,A,I,H,G,F
    2) C,F,E,D,C,B,A,F,B,E
    3) E,G.D,E,H,D,C,I,B,C,J,B,A,J,I,H,G,F,E
    4)I think there is no solution.

    PART 2.
    http://sketchtoy.com/68770874
    http://sketchtoy.com/68770877

    PART 3.
    http://sketchtoy.com/68770662
    Junior’s puzzle solution: red, purple, blue, yellow, green, orange, red, yellow, purple, orange, yellow

    PART 4.
    I enjoyed this assignment. Because this puzzle is challenged but also interesting. I had this game in my phone before, but I didn’t know the theory behind it. I think we can figure it out how many possible path by what we learned in class, and I believe there are some logic behind it.

  8. Rachel

    Part 1:

    G1: E,F,G,E,D,C,I,A,B,A,I,H,B,C,H,G,D,F
    G2: C,D,E,F,A,B,C,F,B,E
    G3: A,B,C,J,B,I,C,D,H,E,D,G,F,E,G,H,I,J,A
    G4: I couldn’t find a solution to this puzzle.

    Part 2:

    1. https://sketchtoy.com/68770750
    2. https://sketchtoy.com/68770754

    Part 3:

    Here’s my solution to Junior’s puzzle: yellow, green, orange, red, yellow, orange, pink, yellow, blue, pink

    Part 4:

    I enjoyed this assignment because I’ve always loved solving puzzles. This assignment reminded me of completing a maze, which I loved doing as a kid. This exercise can be connected back to our discussion of lists, where order matters. To cross over all the bridges we had to make a list of all of the edges of the maps without repetition. Everyone’s list will surely be different, even though they contain the same elements.

    • Franklin Ajisogun

      Part 3:

      2)Solution to Richel puzzle #2: J,A,BJ,I,B,C,I,H,,C,D,H,G,D,E,G,F,E

    • Danping Zhong

      Is there any solution for your puzzle? I couldn’t find any.

  9. yvan gohourou

    part1
    G1:E,F,G,E,D,C,I,A,B,A,I,H,B,C,H,G,D,F
    G2:C,F,E,D,C,B,A,F,B,E
    G3:G,F,E,D,C,B,A,J,C,I,B,J,I,H,E,G,H,D,G
    G4:I don’t think there is a solution for that one.
    part2
    1.https://sketchtoy.com/68771796
    part3:
    Here’s my solution to rachel’s puzzle #2:
    J,I,H,G,F,E,D,C,B,AJ,B,I,C,H,D,G,E
    Part4:
    I did not enjoy this exercise because i failed to find the solutions of some of the puzzles. It is challenging to find a solution to one of this puzzles and the frustration that come when you think you finally find something which is not is killing me. I’m not saying that i want easy puzzle, i just don’t like not be able to complete that problem.

  10. jesstopal

    PART 1.
    G1) E, G, D, C, B, A, I, B, H, I, C, H, G, F, D, E, F

    G2) E, B, F, C, D, E, F, A, B, C

    G3) I, J, A, B, J, C, B, I, C, D, E, F, G, E, H, D, G, H, I

    G4) I worked extra hard to figure out to solve this puzzle, but I couldn’t find any solution. I think this puzzle has no answer.

    PART2.
    1)https://sketchtoy.com/68771851
    2)https://sketchtoy.com/68771859

    PART3.
    Here’s my solution to Danping’s puzzles #1 and 2:
    1) C, A, D, B, E, C, B, A, E, D, C
    2) C, A, E, C, B, D, F, B, A, F, E, D, C

    PART4.
    Yes! I definitely enjoyed this assignment because solving a puzzle makes me relaxed and helps me to get rid of negative and stressful thoughts. When solving a puzzle, we try to make a picture come together, but we work extra hard to figure out where those pieces go. I think this assignment gave us an idea of how to figure out how to solve a puzzle without a picture and it would help us to figure out how to write a proof and understand the “list of functions and symbols.”

    • Franklin Ajisogun

      PART 2:

      1) Solution to Jesstopal puzzle #1: D,F,C,E,B,D,E,A,C,D

  11. Jaroslav E Sykora

    Part one
    1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.
    2) E->D->C->B->A->F->E->B->F->C.
    3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.
    4) The last puzzle has NO solution.

    Part two
    http://sketchtoy.com/68771881
    http://sketchtoy.com/68771892

    Part three
    Concerning Dunping’s solution of https://sketchtoy.com/68770874
    A->B->D->E->C->A->E->B->C->D->A

    Part four
    1. To sharpen our brains
    2. To interact with peers
    3. To love the subject even more

  12. Samantha.C

    Part 1:
    G1: Start: F, E,G,D,C,H,B,I,A,B
    G2: Start: F,A,B,E,D,C,F
    G3: Start: G,F,E,H,D,C,I,B,J,A,B
    G4: Start: A,D,E,B,F,C

    Part 2:
    http://sketchtoy.com/68772158
    http://sketchtoy.com/68772161

    Part 3:
    My solution to Danping http://sketchtoy.com/68770874
    Start: B,A,C,E,D,B,E

    Part 4:
    I enjoy the exercise, I feel the the puzzles where a little challenging. This app I have on my phone called Peak – Brain Training, they have puzzle just like this on there and other games. There are many different ways to have solutions to the puzzles which makes it more interesting.

  13. jesstopal

    PART3.
    Here’s my solution to Danping’s puzzles #1 and 2:
    1)http://sketchtoy.com/68770874
    C, A, D, B, E, C, B, A, E, D, C
    2) http://sketchtoy.com/68770877
    C, A, E, C, B, D, F, B, A, F, E, D, C

  14. Aleks

    Part 1
    G1 E,F.D,E,G,D,C,H,B,C,I,B,A,I,H,G,F
    G2 C,F,E,D,C,B,A,F,B,E
    G3 E,G.D,E,H,D,C,I,B,C,J,B,A,J,I,H,G,F,E
    G4 no solution

    Part 2
    http://sketchtoy.com/68772198
    http://sketchtoy.com/68772199

    Part 3
    Danping solution: A,C,E,B,D,E,A,B,C,D

    Part 4
    I somewhat enjoyed the assignment because I am not into puzzles. I imagine this is connected to class work because we are doing proofs which follows a certain path.

  15. Silvana

    Part #1
    G1) ED, DC, CB, BA, AI, IB, BH, HI, IC, CH, HG, GD, DF, FG, GE, EF
    G2) CF, FE, ED, DC, CB, BA, AF, FB, BE
    G3) GF, FE, ED, DC, CB, BA, AJ, JC, CI, IB, BJ, JI, IH, HE, EG, GH, HD, DG
    G4) No Solution
    Part #2
    http://sketchtoy.com/68772191
    http://sketchtoy.com/68772196
    Part #3
    Solution to Yvan puzzle
    BF, FE, EA, AB, BC, CD, DE, EC
    Part #4
    I enjoyed this assignment because it felt more like a game than an assignment. It was fun finding different ways of connecting the points. By not being allowed to cross a bridge twice, it makes it more challenging. It is important to choose a correct point to begin with for the puzzle to work out. This game can relate to what we talked about it class.

  16. Samantha.C

    can anyone see my post?

  17. Jonas Reitz

    Now we can!

  18. Samantha.C

    G4. No solution. lol

Leave a Reply to Franklin Ajisogun Cancel reply

Your email address will not be published. Required fields are marked *