# OpenLab #7: Proof Journal

Your assignment for the next week is to try to prove the conjecture that your group created in class on Tuesday, 10/22/15.  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 idea that discussed way back in OpenLab #2).  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, 10/29/15):  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 or other work you did along the way.

## 11 thoughts on “OpenLab #7: Proof Journal”

1. Justin J Meyer says:

I am proving Samuel Wong’s conjecture. I will slightly change his conjecture and sate it as, “If any shape with an even amount of edges is solvable and we insert interior edges connecting two opposing vertices, that shape is solvable only if the amount of inserted edges are odd. It is not solvable if the amount of inserted edges are even.”

I began experimenting with this conjecture by trying out some examples. I will attempt to display these below. I will use letters to represent the vertices.

1) Let us imagine a circle, two curved edges connected by two vertices. Next, let us imagine the same circle with one interior edge connecting the two vertices.
Here, both of these are solvable and follow the conjecture.
2) Let us imagine a square with four edges and four vertices: a, b, c, d. Now, let us imagine a square with one edge connecting opposing vertices. Finally, let us imagine a square with one interior edges connecting each set of opposing vertices two edges in total.
Here the first two scenarios are solvable and the third is not, following our conjecture
3) Now, let us imagine a hexagon with edges a, b, c, d, e, f. If we have one interior edge connecting one set of opposing vertices, such as an edge connecting a->f, b->e, or c->d, we have a solution. If we have two of these edges present, there is still a solution. If we have three of them present, there is no solution. This disproves our conjecture since we have a solution with an even amount of interior edges and no solution with an odd amount of interior edges.

While I was working on this conjecture, originally I thought it was true. As I started with my examples I was rather pleased. Once I reached a hexagon and discovered the conjecture was false I remained in a good mood. The conjecture was interesting, since it was relatively simple but did not seem obviously true or false.
While working on these problems I have tried both simple and complex conjectures. And while solving these diagrams are relatively easy, developing theorems for them is proving quite difficult, yet still entertaining. I enjoy the challenge and am looking forward to continuing this project.

2. Ryan says:

I will be trying to prove that my groups conjecture is true. My group is number 4 as posted on the webwork page. The conjecture we came up with is if we have three or more vertices connected at the center then no walking tour can be made. First I would like to point out at the time I did not notice but the conjecture was worded in a way that does not clearly state how the center of the shape should look. Part of my time in proving this conjecture to be false or true was spent reviewing the definitions we had in class. What I noticed was if you have people with different ideas of what is meant by 3 or more vertices connected in the center you will have different drawings and walking tours. Two of the ways I thought someone would come up with is by thinking the statement actually meant that you have one vertex in the center but has a degree of 3 or more. The other way is where you have 3 vertex( vertices) connected creating a triangle in the center of the entire shape/ walking tour. I personally did not remember which idea we had at the time so I just decided to solve the conjecture worded differently for both ideas. For the first one I placed one vertex with a degree of 3 in the center of of a triangle each of the three vertices on the triangle are connected to one of the three edges from the vertex of degree three in the center. I tried to solve this with no success. It is possible to do so if you add an half circle but I then I thought that the vertex may now not be considered to be in the center anymore. So to balance it back I added 2 more half circles to the other outside edges of the triangle this resulted in me not being able to solve the problem with a vertex of degree three in the center. I continued to try various other shapes with no luck. Finally I tried to do the second option of our conjecture where you have three vertices in the center connected this formed a triangle in the middle connected to a larger triangle. This I also could not make a walking tour.

3. Josiel says:

Theorem: It is impossible to solve a graph that has 3 or more vertices with degree 1 and if you were to start from the inside.

The first thing I did was actually write out the theorem so that I can analyze it. I, of course wanted to believe this to be true so I drew about 5 quick graphs that met the requirements, has 3 or more vertices with degree 1. On each graph I started from the inside but I could never complete it there would always be 2 or more lines left over. But I did notice that starting from the outside meant there were more lines being covered. But I started thinking, to be considered the inside, it had to be a point that is not on the edge, so essentially I could start at any point not on the outside edge. It still wasn’t solvable. I then considered to try and actually write down a proof. The trouble was that there isn’t a direct way to write down a proof so I decided to write a proof by contradiction. But it’s just so hard to explain the ‘then’ after the suppose part of a proof. Aside from writing down an actual proof, actually drawing it out (a graph with 3 or more vertices with degree 1) the conjecture is totally true and it’s very difficult to explain in words.

4. abdelmajid says:

First, lets describe our conjecture. the conjecture consists of series of triangles and circles inside each other about 3 circles and 2 triangles ( please look at the picture above group 3).

conjecture : Giving the edge ( radius of the small circle ), is it possible to start from the vertex o ( origin of the small circle) and get to the vertex B (point B in the big circle) by following a path and not repeating any edges.

theorem we are trying to prove is as follow : If the conjecture proved to be true then it s true for adding infinite number of circles and triangles in another word we can add as many circles and triangles we want and will be able to found a path that solves it .

working on the conjecture in class turned out to be no solution to the conjecture, my partners and I agreed to to change the radius (edge) of the small circle and instead draw a diameter( diameter =2 radius), its basically adding another edge witch is twice the old one and has 2 vertices instead of 1 but that didn’t help.

spending time working on the conjecture, I tried doing it the way around meaning how bout if we started from the vertex B and try to get to the vertex 0 and I confronted same problem, witch make sense because if it has a solution ( path ) it will be the same path no matter where you started because the conjecture has only 2 vertices connected with path

another idea I came up with is that anytime you starts from a vertex( origin) any time you cross a circle or a triangle and you move on to the next shape ( triangle or a circle) you have to leave an edge so I thought maybe if we erase an edge will come up with a solution, I tried to figure out witch one so I erased one by one and tried to find a path, at the end that didn’t work also.

working on this conjecture and thinking about the last thing we did in class reminds me of the subway system
local stops are vertices with degree 2 because any local stop connects trains with another stop that is going downtown and another stop s that is going uptown.
express stops are vertices with degree 3 and it could be more depends on the number of trains that meet at that stop.

5. sanaya1 says:

Conjecture: It is impossible to solve a puzzle that has 3 or more vertices with degree 1 and if you were to start from the inside.

I started off by recalling that originally we came up with two conjectures, both of which seemed correct no matter which puzzles we made. One of peers decided to combine the two conjectures but I noticed when the two conjectures were combined, the overall conjecture was no longer true as I was able to prove it to be false. So another one of my peers adjusted the wording but I remember still being uncertain about what the conjecture was saying when we gave it in.

After reading it again at the beginning of the assignment my confusion remained so I decided to start off being trying to figure out what our conjecture was saying. Most of my confusion was really stemming from the second part of our conjecture. I created several puzzles with a maximum of 2 vertices with degree 1 that were solvable. But as soon as I added 1 or more vertices with degree 1 one to these same solvable puzzles, they became unsolvable(so the puzzle now has 3+ vertices with degree 1). So saying the reasoning behind adding the “and if you were to start from the inside” part seemed irrelevant to me. This led me to believe that the two parts of this conjecture was not intended to be related to one another. I think we just combined the two conjectures because they both seemed correct and Professor told us to submit one but we couldn’t decide on which would be better to submit. So I went ahead to analyze the second part of the conjecture separately.

I first asked myself what was meant by “the inside.” Does it mean the middle? Or does it mean vertex that is not located in a corner? If “inside” was intended to mean middle, then I agree that puzzles cannot be solve if you start from the middle. The many puzzles that I did that I had already known to be solvable was impossible to solve when starting from the middle. I always ended up having to cross a path more than once. But if “inside” was intended to mean a vertex that is not located on the corner as I heard mentioned once in our discussion then I do not agree that its impossible to solve. I solved a few solvable puzzles from vertices other than the ones in the corner.

So i think the new conjecture should be:
It is impossible to solve a puzzle that has 3 or more vertices with degree 1 and it is impossible to solve a puzzle if you start from the middle.

6. Mei Zhu says:

For our group #3, our goal is to find a walking tour that works for the graph shown in the activity. There is a circle inside a triangle, and then a circle around the triangle continuously. In addition to the circle at the center, there is a little segment (radius) connects the origin to the circle. We need to come up with a possible way to start from the origin and to pass every edge of the triangles and around the circle.
During the time I am working on the conjecture, I tries as many ways as possible to see if it is possible to find a walking tour that works in this problem. It is very hard to try by hands if we do not have any prior knowledge. I tried to divide the conjecture into many possible parts. For example, I made it into a circle with a radius inside. I found that it is possible to start from the origin and then walk around the circle once. Even after I added a triangle around the circle, it worked too. When I added a circle around the triangle, it became impossible to do anything because there will be a little segment that covered twice. Then, it violates the rule of walking tour. I could solve the first two puzzles; however, I found it hard to do anything after I added more conditions to the conjecture. When the graph becomes more complicated, it is going to be hard to get a solution.
When I first glanced at the picture created by my partner, I was thinking if it is possible to find a consistent way to do this type of problem. When I knew that it just came from my partner’s mind, the first thing I thought was it must be impossible to do this. I did change my mind because at the beginning each of us were confident about the project and believed that we could make it. After a few attempts, I gave up work on any trying for the problem.
However, I do like to try some conclusions or analysis why the conjecture does not work at the end. I found that when we add a triangle or a circle, the vertices of the graph changed. I also tries to count the even or odd of the vertices and see anything I may miss, but it seems a little challenging to do this because I cannot find a regular pattern.
As I worked through the conjecture, I felt not bad because I know it is not a bad thing if I tried. At the beginning I went through the conjecture, I was kind of confidence and thought I could at least find a pattern. At the end, I was still nor able to have anything. It was a little upset because since this type of question existed long time and there must be a pattern I should have found. Since I tried, I do believe that I will understand it more when we go through the conjectures in the class.

7. Rahat Javed says:

I have taken the re-worded conjecture of our group by Justin and it is as follows, “If any shape with an even amount of edges is solvable and we insert interior edges connecting two opposing vertices, that shape is solvable only if the amount of inserted edges are odd. It is not solvable if the amount of inserted edges are even.”

First and for most I agree with this conjecture, but only to a certain extent. The conjecture is saying is that, if one is confronted with a shape that has edges, and there are an even amount of “bridges” or lines with in that shape then that puzzle or shape is solvable. I believe that the shape is solvable, but with odd number of interior bridges, maximum of 3.

Like said, I have established that this only works in very specific cases. For example I drew a square and lined the insides of the square with one diagonal line connecting to vertices. After that I took my pen and attempted to solve the puzzle, and to my wonder, it worked. Then I did the same thing again I just added another diagonal line intersecting the previous one and once again attempted to solve it. It did not work. I could not go over all the lines once. Furthermore I decided to add another line, but this time a vertical line in the top triangle (created by the diagonals), with in the square. Despite the conjectures belief it did not work. But here is where I became a little creative. I once again, drew the same box, but this time I made a triangle splitting the interior of square into a “Y”. This gave me a odd amount of bridges, so I attempted to solve it and it turned out true. Now if I were to go back to the old pattern drawing diagonals, it doesn’t work. No matter how lines I draw cutting up the triangles created by the diagonals. So thus, I do not believe that the conjecture is completely false or completely true. It does work!, but only in some specific cases. Hence, the placement of the interior lines have to be quite strategically placed for the conjecture to work.

8. Irania says:

In the beginning of attempting to prove the conjecture my group and I came up with, I made many attempts to try and draw different drawings were the puzzle might be possible. I also attempted to see if I could find a puzzle were there were 2 vertices with degree of one and the puzzle was not able to be solved if we started from one of the vertices with degree of one. It was not possible for me to solve puzzles when you stared on a place where the vertices did not have the degree greater than one.
I also attempted to put our conjecture into one of the proof formats that we have been working on in class. I attempted to solve the conjecture through using the contradiction proof but did not know exactly where to go from there. It was a little confusing on trying to figure out how to get from one thing to another. I also had a difficult time attempting to phrase vertices and other components of the conjecture into actual letters to be part of the proof I would be solving. I feel that this is probably something we may eventually learn but for now, I am stuck on how to prove this conjecture.
The concept that we had to fix in our conjecture was the part in which it talked about starting from the middle. What is considered the middle of a puzzle? The middle is a little ambiguous but we can probably say that the middle is anywhere where there is a vertex with a degree of two or more. The puzzle seems to be true after tackling with different examples of different puzzles I am not too sure on how to prove it in words.

9. Kenny says:

The conjecture that I am trying to prove is “If there are odd number of lines inside of a shape, then it is solvable. But if there are even number of lines inside of a shape, then it cannot be solved.” First thing I did was coming up with many shapes with only one line inside of the shape and tried to solve them. I realized that any shape that has one line inside can be solved. Then I moved on to shapes with two lines inside. This one was a bit more difficult. There are few examples of this, two lines that intersect (X, T), two lines that are separate (l l), and two lines connecting, (V). I found that only the lines that connect to each other can be solved, while the lines that intersect or separate cannot be solved. This clearly contradicts my conjecture, which even number of lines inside a shape cannot be solve. Therefore my conjecture is false. I also found that as long as the lines are connected, it doesn’t matter if it’s even or odd, it can still be solved. This is the same for separated lines, the parity does not make a difference, it still cannot be solved.

10. Fuzail Khan says:

Our group conjecture was, “If we three or more vertices connected at the center then no walking tour can be made.” But we changed it to, “If we have a shape of polygon that has a vertex in the center and it is connected with all other vertex then there is no walking tour.” We have changed our conjecture because our first conjecture does explain clearly what we tried to say.

I agree with this conjecture and it is not possible to solve the puzzle. Every time, when you make any kind of polygon like a triangle, square, pentagon, hexagon etc., and you put a vertex in the center of the shape, and connect the vertex with the other vertices. After that. when you try to make a walking tour, you will end up having missing side that you can not walk through. At first, when I tried to solve the problem, I started to walk on the edges of the shape. Then, I started to walk toward the center of the shape but I ended up seeing some sides that I was unable to walk through. For triangle I Coud not able to walk one side, for square it was two side, for pentagon it was three, four for the hexagon and so on and so forth. Moreover, the missing sides also increase if we start walking from the center. That leads us to add a little bit in our conjecture which is, “If we have a shape of polygon that has a vertex in the center and it is connected with all other vertex then there is no walking tour. Also, If you walk all the outside edges then go towards the center, the number of the missing sides will increase as the polygon increase. Additionally, when you start from the center, the number of the missing sides will increase as the polygon increase.” This proves that our conjecture is true and reasonable.

11. Samuel says:

My revised conjecture “Any polygon is solvable, and any polygon with one bisector going through it interior model till reach the edge of a polygon will be solvable as well”. I imagined any shape of polygon is solvable because we all know a plain circle or square is solvable from last open lab, and we prove it in class as well. So by adding more side to the square; it will become a pentagon, then it will still be solvable even if shape it make up of a lot of sides, this explain first part of my conjecture that any polygon is solvable including a circle. The next part of conjecture is “one bisector going through it interior model till reach the edge of a polygon will be solvable as well”. I was saying that it solvable if their one line or bisector going through the whole polygon till hit the edge of shape it solvable.
My thoughts if one bisector is solvable what would 2 bisector with polygon be yes, or no. I experimented around with simple drawing, and I discover it not solvable unless you make the 2 bisector in the polygon connect. If one square with two diagonal lines cut the polygon into 4 equal pieces, then what happen shift the two diagonal lines? So I make the two diagonal lines into v shape with lower half of v connect to the side of the figure. The picture being display the two lines in the polygon become connect by their end points, and become part of the side of polygon and 2 segment point become one for other sides. This solvable if a polygon has this unique v, then it solvable if it that unique v. I admit it very interesting activity to be doing to understand proof and logic, but sometime these puzzle make scream.