No Goblins Allowed http://862838.jrbdt8wd.asia/ |
|
The Reconstruction Game http://862838.jrbdt8wd.asia/viewtopic.php?f=44&t=8094 |
Page 1 of 2 |
Author: | Dr_Demento [ Wed Feb 04, 2015 5:01 am ] |
Post subject: | The Reconstruction Game |
The Reconstruction Theorem is an open problem in Mathematics from the field of Graph Theory. First a few basic definitions. Graph: A set of points and lines connecting them. Isomorphic: Two graphs are isomorphic is you can rearrange the points and lines so that they match up exactly, but you cannot disconnect any lines or add any lines.
These are all Isomorphic
The Reconstruction Theorem states that every graph up to isomorphism (with three or more verticies) has a unique deck of sub-graphs, each one being the same as the original graph except one vertex and all lines connected to it is deleted. Now, that is a pretty abstract concept, and the theorem has never been proven, but no one has come up with a counter-example yet, which means you can use it to play a fun game (at least, I think it is fun). First you take a simple picture, which you turn into a graph. Then you break down that graph into its set of subgraphs, and really mix the subgraphs up, and then you give the subgraphs to a friend and see if they can reconstruct the original picture. Below is an example of such a process.
Original Graph
Deck of Subgraphs
Scrambled Subgraphs
As you can see, that last step adds a significant degree of difficulty to the process, I haven't even rearranged the order of the subgraphs, they correspond one to one with the unscrambled deck. Note that when trying to solve for the original graph, you do not just do these steps in reverse, first find some graph that could make all the subgraphs, and then you can poke and prod that thing into a coherent picture. So anyways, the game is pretty simple, one person makes a deck, everyone else tries to figure out what the original graph is, it could be they can just say what it is (It is a stick guy), or maybe they could draw it themselves. I don't feel like there should be any restriction on when new decks can be posted, multiple problems could be open without previous ones needing to be solved, mostly due to the effort involved in making a deck. For similar reasons, the answer should probably sblocked. To get things started, here is a simple deck without a solution.
Deck 1
Good luck! I hope other people enjoying do this and I'm not just a crazed, lonely mathematician. |
Author: | razorborne [ Wed Feb 04, 2015 6:11 am ] |
Post subject: | Re: The Reconstruction Game |
sure, I'll give this a shot. so I think the first place to look is the number of lines from each vertex in each subgraph. starting in the upper left and going clockwise... A: 2, 3, 1, 2 B: 2, 2, 2, 2 C: 1, 2, 2, 1 D: 1, 2, 2, 1 E: 2, 1, 2, 3 labeling the four vertices with lower case letters a-d, what do we know? A, B, and E have 8 connections each, while C and D have 6. this means that, in the final form, the missing dots in C and D (call those e) have more lines connected to them than the other three which likely remain constant. if Ae, Be, and Ee each have 2 lines coming out of them and Ce and De have 3, that would account for what we see. there's not all that many ways to arrange those, so we can probably brute force from here. let's say Ce and De don't connect. that gives us: Ae: Ce, De Be: Ce, De Ce: Ae, Be, Ee De: Ae, Be, Ee Ee: Ce, De but does this match our data? no, if Ae is removed then we would see a flat 2 distribution. so Ce and De must connect. that frees up some space. B has a flat 2 distribution, so it likely connects to both Ce and De. that leaves one to connect to each of the others, which also connect to each other. Ae: Ce, Ee Be: Ce, De Ce: Ae, Be, De De: Be, Ce, Ee Ee: Ae, De so does that match? if we remove Ae, we're left with 2 on Be, 2 on Ce, 3 on De, and 1 on Ee. if we remove Be, we have 2 on Ae, 2 on Ce, 2 on De, and 2 on Ee. if we remove Ce, we have 1 on Ae, 1 on Be, 2 on De, and 2 on Ee. if we remove De, we get 2 on Ae, 1 on Be, 2 on Ce, and 1 on Ee. if we remove Ee, we get 1 on Ae, 2 on Be, 3 on Ce, and 2 on De. that matches our results. I don't know what it is supposed to be artistically speaking, but it's isomorphic to this: Attachment: in your face Dr. D.tiff [ 30.15 KiB | Viewed 15234 times ] |
Author: | Dr_Demento [ Wed Feb 04, 2015 6:32 am ] |
Post subject: | Re: The Reconstruction Game |
I have no idea what picture you are trying to link to, but the solution you provide is an accurate description of the solution.
Spoiler
Feel free to make a deck of your own, it is pretty fun to see how far away from the original design you can get with the cards. |
Author: | Lilan [ Wed Feb 04, 2015 6:37 am ] |
Post subject: | Re: The Reconstruction Game |
razorborne's kind of looked like if a bad 3D movie had a scene where a piece of paper aggressively floated towards the audience |
Author: | razorborne [ Wed Feb 04, 2015 6:43 am ] |
Post subject: | Re: The Reconstruction Game |
Lilan wrote: razorborne's kind of looked like if a bad 3D movie had a scene where a piece of paper aggressively floated towards the audience razor doesn't have a drawing program, so razor used the first one google spat out, then took a screenshot. |
Author: | Dr_Demento [ Wed Feb 04, 2015 6:46 am ] |
Post subject: | Re: The Reconstruction Game |
Did your operating system not come with one installed? You know, Paint? |
Author: | razorborne [ Wed Feb 04, 2015 6:58 am ] |
Post subject: | Re: The Reconstruction Game |
Dr_Demento wrote: Did your operating system not come with one installed? You know, Paint? I used Appleworks for a long time but then Apple decided to stop supporting that with the new updates so it broke. anyway I just downloaded paintbrush and made an easy one.
an easy one
|
Author: | LilyStorm [ Wed Feb 04, 2015 12:33 pm ] |
Post subject: | Re: The Reconstruction Game |
I already graduated school I don't want more homework. |
Author: | Dr_Demento [ Wed Feb 04, 2015 2:56 pm ] |
Post subject: | Re: The Reconstruction Game |
Razor Solution
Fun fact, disconnected graphs are easier to solve because when you remove a point in side, it shows you the complete picture of the other.
Deck 2
|
Author: | razorborne [ Wed Feb 04, 2015 5:33 pm ] |
Post subject: | Re: The Reconstruction Game |
Dr_Demento wrote: Fun fact, disconnected graphs are easier to solve because when you remove a point in side, it shows you the complete picture of the other. I know. that's why I said it was easy. but I wanted to write "HI" and cursive can suck it.
solving John Malkovich
|
Author: | Dr_Demento [ Wed Feb 04, 2015 5:36 pm ] |
Post subject: | Re: The Reconstruction Game |
Spoiler
|
Author: | Dr_Demento [ Thu Feb 05, 2015 3:29 am ] |
Post subject: | Re: The Reconstruction Game |
Ah heck, I enjoy making these too much.
Deck 3
The hardest part is making the regular polygon to fit all these into. Is that an actual requirement? No, but I'm unimaginative. |
Author: | razorborne [ Fri Feb 06, 2015 5:27 pm ] |
Post subject: | Re: The Reconstruction Game |
oh damn 10 points, you crazy let's do this
this, being done
so I think you may have made a mistake. could you double check that the deck is correct? |
Author: | Glasir [ Fri Feb 06, 2015 11:29 pm ] |
Post subject: | Re: The Reconstruction Game |
well, you're slightly wrong, in that you're missing a subgraph in your edge counts. but i agree that there appears to be an edge missing, assuming i'm mathing correctly: The original graph has 10 vertices and k edges. Each of the edges appears in all but two of the subgraphs (i.e., an edge appears iff neither of its two vertices is removed) So each edge shows up in 8 subgraphs. So the total number of edges in all subgraphs has to be divisible by 8. But there are 119 total edges in all subgraphs. |
Author: | Dr_Demento [ Sat Feb 07, 2015 2:56 am ] |
Post subject: | Re: The Reconstruction Game |
Found the issue and corrected it. |
Author: | razorborne [ Sat Feb 07, 2015 7:33 pm ] |
Post subject: | Re: The Reconstruction Game |
trying again
|
Author: | Dr_Demento [ Sat Feb 07, 2015 9:29 pm ] |
Post subject: | Re: The Reconstruction Game |
Wrong. |
Author: | razorborne [ Sat Feb 07, 2015 10:49 pm ] |
Post subject: | Re: The Reconstruction Game |
whoops, I see my error. the 2s are never touching the same 3s as each other.
solution maybe unless I screwed something else up
|
Author: | Lilan [ Sat Feb 07, 2015 10:54 pm ] |
Post subject: | Re: The Reconstruction Game |
can you rename this thread "razorborne and dr. d post lines at each other" |
Author: | Dr_Demento [ Sat Feb 07, 2015 11:07 pm ] |
Post subject: | Re: The Reconstruction Game |
Correct, although this is the cooler version (that I made it from).
Peter's Graph
|
Page 1 of 2 | All times are UTC - 6 hours [ DST ] |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |