OpenLab #4: Bridges and Walking Tours

The assignment below is due BEFORE CLASS on Thursday, September 29th (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 9/27 (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 EXAMPLE 1 above.

WARM-UP 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!

WARM-UP 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!

WARM-UP 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.  Leave a comment responding to EXAMPLE 4 (above), telling us for each one of the 8 graphs whether a walking tour is possible or not.  You only have to state whether it is possible or impossible for each one.

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

 

39 Comments

  1. Sonam

    PART 1.

    graph # 1 – possible graph# 5 – impossible
    graph# 2 – possible graph# 6 – possible
    graph#3 – impossible graph# 7 – impossible
    graph#4 – possible graph #8 – possible

    PART 2.
    Here is my graph:
    http://sketchtoy.com/67492869

    • Armando

      Part 3:
      I believe your puzzle is A-D-G-A-E-H-K-G-I-K-J-F-I-D-F-C-B-F-A

  2. Hanan

    HI Sonam
    I really love your graph something intresteing and I will come back to solve it

  3. Hanan

    HI Snoam , Iagree with you about all the possible soultion you post it I got the same result exact hopefully we are having the right answer , I knew if we dont cross the bridage twice we ok .

  4. Hanan

    For part one I will say if we dont cross the bridage more than one time we are in the right track so I will say
    #1 possible
    #2 possible
    # 3 Impossible
    #4 possible
    #5 impossible
    #6 possible
    #7 impossible
    #8 impossible

  5. Hanan

    Sorry i made a mistake in #8 impossible we will cross the bridage twice

  6. Kevin Truong

    Part 1:
    1) Possible 5) Possible
    2) Possible 6) Possible
    3) Impossible 7) Possible
    4) Impossible 8) Possible

    Part 2:
    http://sketchtoy.com/67495551
    http://sketchtoy.com/67494869

    Part 4:
    SOON

  7. Gary

    For part 1 I will say that
    # 1 possible
    # 2 possible
    # 3 impossible
    # 4 possible
    # 5 impossible
    # 6 possible
    #7 impossible
    # 8 impossible

  8. Gary

    For part 1 I will say that
    # 1 possible
    # 2 possible
    # 3 impossible
    # 4 possible
    # 5 impossible
    # 6 possible
    #7 impossible
    # 8 impossible

  9. Violanda

    Part 1:
    #1 possible
    # 2 possible
    # 3 impossible
    # 4 impossible
    # 5 impossible
    # 6 possible
    #7 impossible
    # 8 possible

  10. Hanan

    I made a mistake on #8 I meant possible

  11. Violanda

    Part 2:
    http://sketchtoy.com/67497578

    • Gary

      Hi Violanda
      I think this is how you solve your puzzle
      (start at A)- A,G,E,A,C,D,B,A,F,D,F,H,E

    • Leonardo

      Hey Violanda,

      If I’m correct this is your solution to your drawing,

      Starting from A,B,D,F,H,E,A,F to D (the round side),C,A,G,E

    • Tyniqua

      Hey Violanda, you kind of did your puzzle in order so I think it wouldn’t be fare for me to put the solution up.

    • Ismail Akram

      PART 3:
      Response to Violanda’s Problem (although the animation gave it away)
      Solution: (Start at E): E, G, A, C, D, F, A, B, D, H, E (basically the animation backwards)

  12. Hanan

    Hi Snoam
    I really think and think to try to solve your puzzle I have feeling that I miss up or i dont understand the topic good . Any way i will try to solve it
    A-B-C-D-E-H-K-J-F-I-G

  13. Hanan

    Hi Snoam
    I really think and think to try to solve your puzzle I have feeling that I miss up or i dont understand the topic good . Any way i will try to solve it
    A-B-C-D-E-H-K-J-F-I-G

  14. Hanan

    Hi Violanda
    I have a big feeling i didnt under stand the question any way i will give it a try , I believe we learn from our mistakes
    i will say the solultion is
    D-C-A-G-E-A-B-D-T-H

  15. Gary

    Part 2:
    http://sketchtoy.com/67497754

    • Sonam

      Hi Gary, Here is my solution to your graph, do not correct me if I am wrong. thanks

      F->A->B->C->J->I->F->B->D->E->F->G->H->K->E->F

  16. Hanan

    Yes I enjoyed the assignment. The reason I enjoyed this assignment is because it allows to think more in depth and allows you to begin to understand more about a specific topic . Similarly, in our class, we use this same method, its not step by step simple process but more of understanding the topic it self.

  17. Hanan

    Yes I enjoyed the assignment. The reason I enjoyed this assignment is because it allows to think more in depth and allows you to begin to understand more about a specific topic . Similarly, in our class, we use this same method, its not step by step simple process but more of understanding the topic it self.

  18. Hanan

    Yes I enjoyed the assignment. The reason I enjoyed this assignment is because it allows to think more in depth and allows you to begin to understand more about a specific topic . Similarly, in our class, we use this same method, its not step by step simple process but more of understanding the topic it self.

  19. Tyniqua

    http://sketchtoy.com/67497774
    http://sketchtoy.com/67497753
    1. possible
    2. possible
    3. impossible
    4. impossible
    5. possible
    6. possible
    7. possible
    8. possible

    Yes I did enjoy this assignment, even though I had to stare at the King’s Mountain puzzle for a while before attempting to solve it. I believe the connection between this assignment and our classwork is the topic we did on non-repetitive lists. Like, the puzzle where you can not go over the same bridge twice, you can’t repeat a letter or an item twice in a non-repetitive list.

  20. Leonardo

    Part 1:

    1. Possible
    2. Possible
    3. Impossible
    4. Possible
    5. Impossible
    6. Impossible
    7. Impossible
    8. Possible

  21. Leonardo

    Part 2:

    http://sketchtoy.com/67497873

    • Violanda

      Hi Leonardo,
      I think the solution of your drawing is this,
      A-C-F-B-E-D-A-F-B-A-E-F

  22. Leonardo

    Part 4:

    I really enjoyed this assignment because it has to deal with the word “logic”. It takes us time to figure out what should the next point be in order to determine the solution. From what I see, we have started with Point “A”, meaning we can start right away to the next point without guessing what point should we do from the beginning.

  23. Sonam

    PART #4,
    I liked the assidnment because both creating and sloving the graph helps spatial reasoning and motor skills, also develop logical reasoning abilities. In addition, reasearch is finally demonstrating that our brains do better in long term if they are exposed to novel activities including brain teasers, brain games and logic puzzles.

  24. Armando

    Part 1
    1) Possible
    2) Possible
    3) Impossible
    4) Impossible
    5) Possible
    6) Possible
    7) Possible
    8) Possible

    Part 2
    http://sketchtoy.com/67498007
    http://sketchtoy.com/67498014

    Part 4
    I really loved this assignment, It makes me think a lot. When your in a place in college where most of your work leads to one answer with a given way to do it, its fun to have something make your think harder. In terms of this class, the only concept I can think of being related to this is the idea of being logically equivalent. We say two thinks are equivalent here as well when we depict a picture as a graph.

  25. Gary

    Part 4:
    I enjoyed this prompt because this prompt feels like an art class but is a math topic. This assignment is connected to the set of numbers that can be written repetitive or non-repetitive. Doing this assignment shows that when you cross the bridge more than once is like when numbers get repeated while only crossing the bridge only once is like not repeating the number over and over again in a set of numbers of n length.

  26. Jose De Leon

    Graph # 1: Possible
    Graph # 2: Possible
    Graph # 3: Possible
    Graph # 4: Possible
    Graph # 5: Possible
    Graph # 6: Possible
    Graph # 7: inpossible
    Graph # 8: inpossible

  27. Jose De Leon

    I’ve always been interested bridges in engineering and i never imaged using squares and triangles can be drawn in simple ways using vertices (points) that represents the mass of the Earth and the lines as bridges.This Puzzle expand my awareness to follow logical pattern to possible crossing in time.

  28. Ismail Akram

    PART 1:
    #1 Possible
    #2 Possible
    #3 Impossible
    #4 Impossible
    #5 Possible
    #6 Possible
    #7 Possible
    #8 Possible

    PART 2:
    http://sketchtoy.com/67498448
    http://sketchtoy.com/67498452

    PART 3:
    Response to Violanda’s Problem (although the animation gave it away)
    Solution: (Start at E): E, G, A, C, D, F, A, B, D, H, E (basically the animation backwards)

    PART 4:
    As for this assignment, it was interesting. To think of a connection between this assignment and what we did in class recently, I would say it’s to do with exploring multiple possibilities. We recently studied lists and combinations of possibilities. This graph task is an exercise to explore different routes or “walking bridges” in any given problems. Much like exploring multiple lists from a set of elements.

    PART EXTRA?
    As for the walking tour to think about, this is my proposal. Mind you, I did take some creative liberties with one of the lines I used but technically I did trace over every line once without lifting my pen. This works for the graph, but to translate this to the real life bride scenario would indicate I went out of bounds and came back. Thinking outside the box.
    http://sketchtoy.com/67498467

    Putting an additional bride in the far left should render the route impossible to travel.

  29. hanan abuhashish

    http://sketchtoy.com/67498531

  30. Violanda

    I really enjoyed this assignment,like I enjoyed all the assignments that we did before.It has to do a lot with math,and it makes you to think harder in order to get e solution.We need to you our logic,and try many times to solve the same thing in order to come with an right answer.Moreover,we challenge ourselves to solve also our classmates’puzzles!

  31. Jpitt

    1. Possible
    2. Possible
    3. Impossible
    4. Impossible
    5. Possible
    6. Possible
    7. Possible
    8. Possible

    http://sketchtoy.com/67502663
    http://sketchtoy.com/67502669

    The assignment was very fun since I was able to really build on my logics and reasoning. We had to continuously try and recreate ways to solve the different puzzles but we had to be able to be strategical with our thinking. The process took a bit of work but once you got use to it the thinking became a little bit easier. The truth is that the puzzles helped to enlighten us on our understanding of creating patterns.

Leave a Reply

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