Your assignment for the coming week+ is to try to prove the conjecture that your group created in class on Tuesday, 10/20 (10/20 working space (Google Doc) with group conjectures is here). You may need to refine/expand your conjecture first (let’s discuss this in class). You must spend at least 90 minutes working on this. Trying to prove something can consist of many different activities, such as the following (you do NOT have to do all of these things – you can choose how to spend your time – they are provided for inspiration only).
- coming up with ideas, and testing them out (for example, by creating puzzles and trying to solve them)
- trying to understand what the conjecture says
- trying to solve puzzles that other people created
- trying to create puzzles (and solve them yourself)
- communicating with other members of your group (talking, emailing, etc.)
- trying to write down a proof
- other stuff…
As you work, keep track of what you are doing, thinking, and feeling (this is metacognition – an important idea in education!). What did you do during the time you spent? Did you create any puzzles? Did you solve puzzles? Did you change your mind about whether the conjecture is true or false? Did you have any new ideas about how to prove the conjecture? Did you have any ideas that you gave up on? How did you feel as you worked – were you frustrated/confused/happy/depressed? Why? Did your mood change along the way?
Assignment (Due Thursday, 11/3): Submit a journal of your efforts in the comments below. Your response should be at least 300 words. Describe what you did during the 90 minutes you worked, and express in some way what you were thinking and feeling during the process. Your response can include puzzles (use sketchtoy.com) or other work you did along the way.
Extra Credit. Respond to a fellow student’s comment. Did you do similar things? Different things? Do you have any suggestions for them? Be kind.
When the “Seven Bridges of King’s Mountain Puzzle” was assigned, I recognized it from my previous experience as “The Bridges of Konigsberg” (a famously unsolvable riddle). I then progressed through the puzzles provided to us from the least complex to the most complex, bearing in mind that many of the puzzles may have no solution. At first, I solved the problems with ease or quickly knew by intuition that the puzzle could not be solved. However, I was puzzled by the three most intricate puzzles. I thought about these questions for several minutes and quickly grew frustrated, but I was also curious to find the solutions if they existed. I asked my husband and children to try to solve them, but I found that they too could not find the answer. My children tried various clever solutions by circumventing the rules, such as going over a path twice or creating a new path of their own.
My annoyance ultimately overwhelmed me. I knew from previous experience that there had to be a simple solution to these types of problems, so I researched the puzzle online. In my defense, this was before I knew that research subverted the intent of the assignment. Next, I read the wikipedia article on “The Bridges of Konigsberg” and discovered that the problem was created by the Swiss mathematician Leohard Euler, and helped launch a branch of mathematics called graph theory. While this was interesting, I had difficulty understanding how one could determine if a puzzle had a solution and how one could systematically solve it. I reviewed several YouTube videos and interpreted the following to be the general solution for an Euler graph:
Proposition: A Euler Graph has a solution if there exist zero or two odd-numbered nodes. A node is defined as the endpoint of an edge. An even node is defined as an endpoint of 2n edges where n is a non-negative integer. An odd node is defined as an endpoint of a 2m+1 edge for some non-negative integer m. An edge connects two vertices (nodes) and a path is the total route taken to solve a puzzle.
Furthermore, a puzzle with two odd nodes can only be solved if the path begins and ends at an odd-numbered node and a path with no even nodes must begin and end at the same node.
I then tested this solution on multiple puzzles to ensure that it was accurate and reliable. I discovered that this proposition was correct for all of the puzzles I found. Knowing that this solution worked, I began considering why it worked and after much consideration, I came to the following understanding:
The vast majority of nodes are entered only to be immediately exited. An even-numbered node provides for both entry and exit. However, there are two “special” nodes. These nodes are the nodes from which a path is started or finished. So, a puzzle with all even-numbered nodes can be solved provided the chosen path begins and ends at the same node. A puzzle with two odd nodes has a solution because one odd node can act as the beginning point, allowing an exit only, and the other odd node can act as the ending point allowing, for entry only. Any other number of odd nodes will not be solvable because one of the odd nodes would allow a path to enter but would provide no edge for the exit.
Allison, what is your secret for being able to intuit whether or not a puzzle will be solvable? Please tell me! You seem to have a good grasp of this material, I can certainly understand why you went to the internet in your frustration. I showed these puzzles to some people as well, including my father who is an engineer- he refused to give me the answer!
I really like your comment “My children tried various clever solutions by circumventing the rules, such as going over a path twice or creating a new path of their own.” — THIS IS AWESOME! I’m interested to know just how much power this gives you – if you are given the magical ability to add a single new edge to any puzzle, does this allow you to solve any puzzle? Or are there puzzles that still can’t be solved? Similar for being able to go over a path twice.
I really like your comment “My children tried various clever solutions by circumventing the rules, such as going over a path twice or creating a new path of their own.” — THIS IS AWESOME! I’m interested to know just how much power this gives you – if you are given the magical ability to add a single new edge to any puzzle, does this allow you to solve any puzzle? Or are there puzzles that still can’t be solved? Similar for being able to go over a path twice.
Working on this problem has been pretty challenging, to say the least. It didn’t take me long to disprove my group’s conjecture (if the number of edges on the inside of the shape is greater than one half times the number of edges along the perimeter, then the ‘walking tour’ is impossible). One of the first examples that we looked at in the original Bridges post quickly made it clear that the above statement would not hold true in all cases. That was a bit of a demoralizing start – I didn’t have a lot of confidence that our conjecture would be correct, but I also didn’t expect to prove myself wrong so quickly. I set the whole project aside for a day or two after that, finding myself deterred by the difficult task of seeking out a new conjecture. When I found the drive to get back into it (by drive I probably mean the motivating power of a deadline), I went back to the drawing board, literally. I spent a lot of time playing with the first graph we looked at, which was impossible to complete without modification. I picked up some steam when I realized something I had missed the first time I’d worked on that one — if you take away any of the edges in that graph (not just a particular edge), it becomes solvable. After that I started to look at more graphs that weren’t solvable, and compared them to slightly altered versions that were. I started to have an intuitive sense of whether or not a graph would be solvable judging by the way it looked. It continued to be a struggle though to put this intuition into words, let alone words with clear enough meanings as to be the grounds for a logical statement that I could prove. That drove me to begin applying more numerical observations to the graphs I had been looking at. For each graph I drew, next to each vertex, I wrote down the number of edges connected to that vertex. That made comparing the solvable/insolvable versions more quantifiable, but after I don’t know how long of searching for patterns in those numbers, I again came up empty handed. At that point I was so desperate for an answer that I decided to skim the response that Allison had already posted. Because of previous posts, I had a sense she already knew what made this thing tick. I didn’t want to completely take away my chance at figuring this out on my own though, so I tried to avoid any explicit spoilers and sort of read through my fingers, so to speak. I did however pick up on the idea of parity as being relevant to this problem. I hadn’t considered that at all before. I tried to understand why that might have an affect, and in the absence of a clear idea, I took those numerical observations I made earlier and wrote down how many odd and even vertices were in each graph that I drew. Now I’m looking for patterns there, and I feel like that intuitive sense I had earlier is starting to have a clearer, more discernible shape, but I still find myself at a loss to describe it. Feeling like I’d hit a wall again, I decided to set it aside until sharing findings with my group, which I’m hopeful will provide that spark that will shed more light on this problem than I’ve been able to create on my own.
I had to think a lot about this Openlab assignment. I had to take a break more than once so that I can figure out patterns with a fresh mind. I would like to know what graph your group works on. It sounds quite interesting.
Group Conjecture: “If one half times the number of edges on the outside (edges that are part of perimeter) of the shape is less than the number of edges on the inside, then the walking tour is impossible.”
According to our group’s Conjecture, : “If one half times the number of edges on the outside (edges that are part of perimeter) of the shape is less than the number of edges on the inside, then the walking tour is impossible.”
From the walking tours assignment 4 shapes were given.
For proof on the group’s conjecture I will use Shape G2 and shape G4.
Proof by Contradiction:
If one half times the number of edges on the outside (edges that are part of perimeter) of the shapes is less than the number of edges on the inside, then the walking tour is possible.
If the walking tour is possible, then the number of edges on the inside is less than one half times the number of edges along the perimeter.
According to my groups’ conjecture G4 and G2 both have 6 edges and which I will state as G2=6 and G4=6 and 2|6 which is equivalent to 6 x ½ according to the division theorem, then this would equal 3. Then this states that both shapes G2 and G4 have 3 edges. Before going further, both shapes contain the same amount of edges according to the conjecture respectively but with G4 it was not possible to create a walking tour crossing each bridge exactly once, which is a contradiction, because both shapes have the equal amount of edges when multiplied by ½. And in both instances there are less than the number of edges on the inside but the walking tour was possible with G2. Then the conjecture is false.
I am really hoping to be wrong here, but upon trying to prove the conjecture I could not. I was a bit unhappy to prove my group’s conjecture this way, but I gave up because trying to prove using a direct proof was killing me. This experience has helped me in reiterating why I like proofs by contradiction and contrapositive proofs. Simply put, what helps me to remember the p q part of the truth table is the following:
I always know that if the table has a F in it, this makes the statement false, because the statement cannot be True and False simultaneously which is a contradiction. Simply put you cannot be slim and fat simultaneously. This was my metacognition.
Interestingly, my conjecture and one of Luis’s conjectures were quite similar. So we changed it a bit to make the group’s conjecture. My group’s conjecture is ‘Not every point leads to the completion of the puzzle.’ I visited every single puzzle from my classmates on the Openlab. I tried to prove to see if every starting point has a solution. It turned out that my conjecture is right only if the points are at least four and at least one point should connect to at least three bridges. So I didn’t change my mind since my conjecture seems to be true.
I was solving puzzles by hand on the paper, but I found out that it is much easier if I use the iPad and draw over the puzzles. I think my math brain organized after I gave it some time to do so because I couldn’t solve it three weeks ago. I made a proposition ‘If the starting point has an even number of bridges, it won’t complete the puzzle from that point.’ But it wasn’t true. I tried to find some rules and I found one.
However, I found a rule for similar types of puzzles. Since my groups’ conjec
ture was to prove if every starting point can’t complete the puzzles, I started the starting point from the top of a triangle, and it sometimes worked and didn’t. I felt odd and tried to figure out why some worked but some don’t. So I drew some puzzles with a triangle top. You can see the puzzles on Sketchtoy website here, http://sketchtoy.com/69387017. Puzzle A, B, D, F can’t be completed if I start with the top point. But puzzle C, E can be complete from the starting point of the top point. So my conclusion of this type of puzzle is that the puzzle with an even number of triangles can be solved by starting from the top point. But my conjecture only applied to puzzles that are made of at least four triangles.
Hello Ihn,
Very interesting choice for your own proposition. I remember when we first started the bridges and walking tour, you made a puzzle for our group with triangles and rounded sides and for us to solve we had to start at a specific point on the triangles.
I also agree that using the iPad is definitely easier than the track or mouse on a computer. It makes the process so much smoother and much better to see.
I never thought about the initial point needing to connect to three bridges itself to form the puzzle. It makes me think how crucial those three points are to forming my so called Z shape i mentioned in my paper. Even with three connected points it still is necessary to choose which three points it should be connected to. Great observation Ihn.
This assignment truly challenged my intuition about spaces (and bridges). For me, it was incredibly hard to articulate a conjecture because I severely lack spatial reasoning skills, but hopefully doing more projects like this can improve that shortcoming. In the group conjecture, Allison and I worked together to come up with something that we thought would explain the phenomena, her answer just happens to be the actual correct one (discounting some possible rare unknown edge cases or something like that) because of some prior experience- but I think my conjecture has something to say as well, it was something I noticed when doing the original bridges and walking tours problem. I had a hard time articulating what was going on, and an even harder time drawing, but I did notice one difference between the three bridges that could be drawn and the one that could not. At first I thought it might have been that they need to be ended with a triangle, but that was not the case. Then I thought it might have something to do with the triangle acting as an endpoint- and that is not exactly true, but when you compare the three bridges that worked to the one that did not there is only one highly specific difference. That difference is that the one that does not work has all of its endpoints connected by 3 lines. this is significant because it means that you have to “revisit” each point, as opposed to having any points (like the triangle endpoints) where you can just go “in” one side and “out” the other. To prove or disprove this I tried coming up with an assortment of different puzzles with different numbers of endpoints, and the result was always the same, if I didn’t have at least one connection with only two end points the puzzle simply would not work. Originally this was quite frustrating, because I had a very hard time actually drawing out the puzzles, but I was happy to see that the idea I had come up with held at least for the puzzles I was creating. I do not think that it is the whole story to this concept of “one way walkability” at all, but I do think there is something there, and that I am working in the right direction. I don’t believe my conjecture is the true answer but I do believe it is a part of it.
During the time I spent to work on this assignment, I tried to prove my conjecture and the group conjecture. In fact, it was not that difficult to prove my conjecture since it was a strategy of how to trace the walking tour in order not to cross the bridges twice. However, the group conjecture was particularly challenging to prove.
As a matter of fact, I tried to keep track of my thoughts by writing down every step or everything that I worked on. For example, I created several puzzles and attempted to solve them by applying the group conjecture. The tricky part is that for some of the puzzles that I created, the group conjecture works because when I tried the walking tour using my conjecture, I found the tour was possible. However, for some other puzzles that are similar the group conjecture does show that the walking tour will be possible. But, when I used my conjecture to do the walking tour, I found it not possible. Therefore, to me the group conjecture does not work.
After analyzing the difficulties that make the group conjecture not to be true; I modified it by adding some ideas to make it easy to prove. When I used the modified conjecture, I found the same thing, which is not true. So, I gave it some time and I came back to it hours later because I did not want to give up on it. I adjusted some of the puzzles that I had created and used them to prove the modified conjecture. A couple of tests revealed it true but after trying it in a two-connected-loops with a triangle shape; the modified conjecture was again false.
I was not confused or frustrated with it maybe because I did not spend too much time working on it at once. Even though I did not prove the group conjecture and the modified conjecture, I do believe the provable conjecture must related to the vertices and the bridges.
Unfortunately I missed the second meeting with my group due to an emergency. For my writing I am going based on what I read that Luis and Ihn discussed in my absence. The conjecture that Ihn put forward was ”Not every point to start can complete the puzzles”. This is one I can agree with although not proven. As Ihn conducted several tests of this I did the same. With results coming back to support this conjecture.
For a bit of practice I also did research with my own conjecture. “If a puzzle is symmetrical, the point opposite to a solution point will also be a solution”. Testing this conjecture with a few different puzzles it seems to hold true. I did a few different puzzles of different sizes with restrictions, having to be symmetrical and having to be solvable. Looking at some of the more advanced testing methods that some of my classmates have posted, makes it seem even more solidified as being true.
While I am no expert on this topic I am much more knowledgeable now than before. When we first began this group work of bridges and walking tours I will say I was a tad bit lost when it came to creating my own puzzle. I was in a group with Ihn and Luis, both of which had interesting puzzles and all I had was an improperly done puzzle. Both of them seemed confused when I sent my puzzle in the group, as mine was just a series of dots. I had the expectation that they were gonna solve it as I watched. Little did I know I had to solve it first and they would find my solutions and any others if possible. Luckily Ihn and Luis were understanding, as they sat there solving each other’s and finding alternate routes I quickly polished mine and gave them a quick challenge.
http://sketchtoy.com/69388263
Does every point of the puzzle work when completing the puzzle?This was my conjecture along with my group member Ihn and Chris. Based on observations there are many starting positions to the puzzle of the five point pentagon puzzle. In this case we have points a-e. After trying a few examples i noticed that the starting positions labeled a,d and c, d but never e. Discovered here is that starting positions on the puzzle may work depending on the diagonal points used. Also not all diagonal points work. Take for example the positions of c or b. If one begins the puzzle this way it falls short of completion. B is a point that can connect to another line segment horizontally or vertically but why doesn’t it work? I believe that the starting position must meet a vertical or horizontal point . The puzzle has two forms of completion the Z shape position and the house position. The house position is simply the exterior shape of the puzzle. I tested every point to determine if these two shapes work as well as the already mentioned working points a , d and c,d to determine if it is true. I realized after doing this that either the exterior or interior points must be completed before moving on to the other shape. The Z shape must be completed then the exterior house comes next.
My conjecture was to determine if any other points would work and they dont meet the requirements such as the point (e). This is a unique point part of the exterior of the puzzle. What characteristics does the point (e) have? It is on the exterior portoin that (e) begins and only has the option of connecting to points diagonally. This does meet one piece of the requirements but notice (e) after connecting to the diagonal (a) or (b) can no longer connect a line on the opposite side of (a) or (b). Also one notices that there are two missing connections of points. (E) will miss these points regardless which side of the diagonal you begin (a) or( b). Even though (e)meets a diagonal and then a horizontal the pattern does not connect a diagonal and another vertical. It cannot complete the puzzle the exterior or interior of the puzzle and will not work. One would think that because (e) is a center point that you can begin and end here. Due to the fact that one shape must be completed as mentioned this will not work as well. Thus the only way to complete this puzzle .
What I did to complete the assignment was try to draw different puzzles trying to derive a basis for the proof but that really didn’t go anywhere. It takes me longer than I would like to notice the connections so I looked into Euler. I wanted to see if there was any specific theorem or just a definition that might help me figure out how to approach this assignment after some searching I did find something. It seemed like an algorithm of sorts to figure out how to tell if a bridge puzzle had a solution. It honestly felt like a gigantic cheat code when I did find out about Euler’s paths; this is also what helped with the bridges and walking tours assignment. The conjecture and definition are down below
The conjecture that my group came up with was “A shape with n (natural number n) sides where n is greater or equal to 3 it is possible to make a pathway.” This is based on Euler paths which states the number of to enter and leave each vertex(except for the beginning and end point) should be the same. It means that the number of bridges passing through each vertex except the beginning and points of the path should be even because each bridge is used only once. The number of vertices with an odd number of bridges can be only zero or two. In this example (see below) there two vertices with three bridges connecting them to the other vertices and four vertices even number of bridges
I. My Conjecture
1. “A shape with natural number n sides where n ≥ 3 it is possible to make a pathway.”
2. Thought Process Behind My Conjecture
a. The purpose of the Bridges and Walking Tours Assignment was to determine “a walking tour that [crossed] each bridge exactly once.” (Bridges refers to vertices A, B, C and D.) In other words, we had to figure out a way to trace out all the edges without lifting up our pencil from the sheet and without retracing and edges. It turns out that the reason these pathways were so difficult to draw was that some vertices had broken off into multiple directions. So, it was like, from A do I go to B, E or D? (See figure below.) Would it make a difference which vertex I go to first?
Afterward, I realized that if there exists a shape with natural number n sides such that n ≥ 3, then there definitely exists a pathway such that each bridge is crossed exactly once.
3. Post-Thoughts
a. Well, it turns out that my conjecture is entirely false since it was vaguely written.
Note: Proof Journal Link
https://www.dropbox.com/s/fuo0ciybvf6mshn/JaredCruz-Proof%20Journal.pdf?dl=0
In my journal, I go through a step by step thought process of how I derived my conjecture, why I believed it was FALSE, how I modified my conjecture, and finally proving my conjecture. Also, I included sketches to guide readers in the point I was trying to make.
this conjecture assignment is a real-world related problem, but we can transfer to math notification and math expression. the graph of this conjecture have been posted as our teammate Jared Cruz mentioned as a polygon. there are three elements in this conjecture that we should pay attention to : vertex, edges, paths. I will use these 3 elements to make sets to clarify the regulation of this conjecture. for example as our teammate raised a simple example:
a triangle with point A,B,C added 1 point D in the hypotenuse and added a path from this point to the opposite point. so there are sets for each point with path number which will be evaluated with notation”1” or “ 2” : (the notation could be others that make you the sense like “0”and “1” , “red” and “blue” , that is on your choices.)
point A: 1,2,1
Point B: 2,1
point D: 1,2,1
point C: 2,1
we can count there are 6 pieces 1 and 4 pieces 2 , pare the 1 and 2 , we find out there is 2 pieces 1 remained. that is mean remain even number of path, that is mean all the points could be travelled but there is one path not needed. so after paired , if there is odd remained paths, it is workable, if it is even remained paths. seems reasonable, now we are back to the original problem to use this kind of sets:
point C: 1,2,1,2,1
point A: 2,1,2
point D: 1,2,1
Point B: 2,1,2
1 and 2 are pared without remainders. It means we could not travel all points once. we need 1 more path to return circuit or make it a loop tank.