Brainteaser Analysis

This will be my first in what I hope will be an ongoing themes of posts explaining the math behind some neat brainteasers. Warning: the content of the posts will be much more enjoyable if you first attempt the brainteaser for a few minutes before reading the detailed solution.

Fill the grid below with the numbers 1 – 8 making sure that adjacent numbers do not touch (for example, 5 cannot touch 4 or 6).  In this game, if the squares are diagonal from each other, they are still considered to be touching.

Blank grid

Give up? Or did you solve it with some trial and error? If you did, congratulations! Either way you should stick around so you can see how to solve it systematically.

We need to introduce the basics of Graph Theory to attempt this problem. According to Wikipedia “A graph is a collection of vertices and a collection of edges that connect pairs of vertices”. A “vertex” is another name for a point and an “edge” is another name for a line that connects two points. So if you had a “graph” of a country, the cities would be vertices and the roads would be edges. Graphs are useful for solving real world problems and fun to play around with. For example, say you have one friend you know from work and one friend you know from school, but they do not know each other. Below is a graph of your relationships.

friends

This graph reveals some things that we know intuitively. First, friend 1 and friend 2 do not know each other since there is no edge connecting them. Second, since there are 2 edges touching “you” we know you have 2 relationships. These concepts are extendable to other environments.

Time to draw a graph for the brainteaser! We will represent each square as a vertex and draw it as a small circle.  If 2 squares are touching we will connect them with an edge.

graph

Just like the relationship graph, we can glean some helpful insights from this graph.  It is clear that some vertices connect to more vertices than others do. For example, the 2 outside vertices (highlighted in blue) only have 3 edges touching them. We call this the degree of the vertex. Thus, the 2 outside vertices each have degree 3 (this is similar to our previous example where “you” had 2 relationships or degree 2). Further, we can see that the 2 most inner vertices (highlighted in red) have degree 6. We can see that the top 2 vertices (highlighted in green) have degree 4. As you would expect, the bottom 2 vertices (highlighted in yellow) also have degree 4. Now for some quick number crunching!

We will assign each of our 8 numbers a number “P” which will stand for the number of possible other numbers it is permitted to touch in our game (a bit confusing, I know, but stay with me). For example, since the number 3 is permitted to touch 1, 5, 6, 7 and 8, but not 2 and 4, its p-value is 5. The number 4 is permitted to touch 1, 2, 6, 7, and 8. Therefore, it also has a P-value of 5.  Below is a table of all of our 8 numbers and their associated P-values.

Number

P-value

1

6

2

5

3

5

4

5

5

5

6

5

7

5

8

6

The 2 red vertices have the highest degree, 6 (since there are 6 lines touching each red point), so we will focus on them. If the degree of one of the red vertices is 6 then any number that could go there must also have a P-value of at least 6 as well. If the number had a P-value of 5, then when trying to place the surrounding numbers we would “run out” of candidates. Give it a try!  Now refer to the diagram below where we attempt to place the number “4”, which has a P-value of 5, in the red dot space.

fail graph

We have used up all the numbers available to the 4 and there is nothing left to place in the left- most blue space (since 3 and 5 are illegal).

So the only candidates for the red vertices are 1 and 8. I have placed them in the boxes below.

graph1

This also forces the placement of the 2 since it cannot touch the 1. Similarly for the 7, there is only one square not touching the 8.

graph 2

The 3 now only has two spots available since it cannot touch the 2, so we can place it in either one. Similarly, the 6 only has two spots available since the 7 is touching two of the remaining four spots. We will slot the 3 in the bottom spot for now. (After we solve it with the 3 and the 6 in the places I put them, you can try to see what happens if you put the 3 in the top spot and then the 6 in the bottom spot.)

graph 3

The 5 cannot go next to the 6 so its place is fixed and the 4 cannot go next to the 3 so it is fixed as well.

graph 4

And there we have it, a solved brain teaser. Just like in a game of Sudoku, once you can get a couple numbers figured out the rest fall into place quite easily. The trick was using a “graph”.

Advertisements

1 Comment

Filed under Uncategorized

One response to “Brainteaser Analysis

  1. Pingback: Handshakes | the Math behind the Magic

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s