Wednesday, December 19, 2018

Tweedledee and Tweedledum

Illustration by John Tenniel

Here is another logic puzzle by Raymond Smullyan, this time from his book Alice in Puzzle-Land:
Just then Alice practically stumbled on Tweedledum and
Tweedledee, who were grinning under a tree right by their house.
Alice looked carefully at their collars to see which was marked
"Dum" and which was marked "Dee," but neither collar was
"I'm afraid I can't very well tell you apart without your embroidered
collars," remarked Alice. 
"You'll have to use logic," said one of the brothers, giving the
other an affectionate hug. "We were expecting you to come around
these parts, and we have prepared some nice logic games for you.
Would you like to play?" 
"As you see, this is a red card. Now, a red card signifies that the
one carrying it is telling the truth, whereas a black card signifies that
the speaker is telling a lie. Now, my brother there [he pointed to the
other one] is also carrying either a red card or a black card in his
pocket. He is about to make a statement. If his card is red, he will
make a true statement, but if his card is black, he will make a false
statement. Then your job is to figure out whether he is Tweedledee
or Tweedledum." 
"Oh, that sounds like fun!" said Alice. "I'd like to play!"  
...Well, Tweedledee [and Tweedledum] went into the house, and both
brothers came out shortly after. They look more alike than ever! thought
Alice. Well, one of them—call him the first one—stood to Alice's left,
and the other—call him the second one—stood to Alice's right. They
then made the following statements:  
FIRST ONE: My brother is Tweedledee, and he is carrying a black card. 
SECOND ONE: My brother is Tweedledum, and he is carrying a red card.  
Which one is which?

If you think you may have a solution, you can try it out against the online version here.

After solving a puzzle (or reading the solution) in one of Smullyan's books, I am often left wishing there were more like it. Why not try generating some more?

Let's say there are 8 simple statements each brother could make.
  • My name is [Tweedledee|Tweedledum]. 
  • I am carrying a [red|black] card.
  • My brother's name is [Tweedledee|Tweedledum].
  • My brother is carrying a [red|black] card.
And 16 more compound statements:
  • My name is [Tweedledee|Tweedledum] [and|or] I am carrying a [red|black] card.
  • My brother's name is [Tweedledee|Tweedledum] [and|or] he is carrying a [red|black] card.
This gives us 24 possible statements each brother could make, so a total of 24^2 = 576 possible puzzles.

But some of these puzzles will lead to contradictions. For example, if either brother makes the statement "I am carrying a black card." We end up with the liars paradox: the brother must be lying, but if he is, he is telling the truth (and vice versa). Some of these also lead to multiple solutions.

A good puzzle must have a unique solution, and running these through a logic-puzzle solver yields 168 good puzzles (you can check out a Python notebook that generates and verifies the puzzles here). Really, only half of these puzzles are unique, as having the anonymous brothers "first one" and "second one" switch statements gives us essentially the same puzzle. So, ignoring the order of the statements/brothers there are 168/2 = 84 unique puzzles based on these statements.

The distribution of names and cards is uniform in these 84 puzzles (the brothers are as likely to be telling the truth as they are to be lying). In the graphs below the brothers are referred to as bro0 and bro1, and the counts are based on the set of 168 puzzles where the 'reverse' of each puzzle is also included.

cards held by both brothers

cards held by each brother

Try your puzzle solving skills against the brothers here. Other Smullyan-inspired puzzles can be found on the puzzle page of this blog.

Thursday, November 29, 2018

algorithms for drawing celtic knots

The images above are the same celtic knot pattern (other examples here) shown in three slightly different styles. You can try creating your own knots and seeing how they look in the different styles using this online editor. All the examples above are based on the same grid:

The grid has primary points (shown in grey) and secondary points (shown in black). Breaks in the pattern are created by connecting secondary points following a few rules. The ribbon pattern is then drawn on the grid. The three styles shown are the result of three different approaches to drawing the ribbon once the grid is established.

  • The top image is created by filling in the spaces between the "ribbon" of the pattern.
  • The middle image is created by following rules that create sections of ribbon around the secondary grid points.
  • The bottom image is created by following some rules to create sections of the ribbon around the primary grid points.

All three use the idea of primary and secondary grid points, and creating the structure that defines the  patterns by joining up the secondary grid points. So the first steps of all three approaches involves setting up this basic structure. Here are those steps, adapted from this earlier post.

Setting up the grid and pattern structure

1) define primary grid points
A knot pattern is laid out on a square coordinate system using a set of "primary" points that are set at one unit distances in the horizontal and vertical directions. We'll say that (0,0) is the top left corner of the grid, and the positive x direction is towards the right and positive y direction is down.  The dimensions of the primary grid must be odd (there must be a total odd number of dots in both the x and y directions). Because we are starting with (0,0) in the top left, the top right point (x, 0) must have x even (4 in the example below), and the bottom left point (0,y) must have y even (6 in the example below).

the primary grid

2) identify secondary grid points
Some of the points on the grid are special - these form a secondary grid. The special secondary grid points are those where both x and y values are even, or both are odd.

the secondary grid

The secondary grid points where both x and y are even will be referred to as even nodes, and those that have both x and y odd will be referred to as odd nodes. The requirement to have the primary grid have odd dimensions (step 1) was needed to ensure that the corners of the pattern are all secondary points.

3) place boundaries
To create an edge-boundary for the pattern, and to create more interesting twists and turns, we follow some rules for drawing boundaries on the grid.

boundary rule 1: A boundary can connect any two non-diagonally adjacent secondary points, as long as rule 2 is not violated. The midpoint of a boundary segment will be a primary point.

boundary rule 2: A primary point cannot have more than one boundary going through it.

The example below shows boundaries drawn along the edge of the image, as well as some internal boundaries.
legal boundary examples, showing
primary and secondary points 

Three ways to draw the "knot"
Now that the grid is drawn with primary and secondary points, there are different approaches to actually creating the celtic knot pattern from the grid.

method 1: Negative space around the secondary points
To create an intertwined ribbon we can fill in the spaces around the ribbon - in addition to the boundaries already drawn, the secondary grid points are built up into polygons, and the "weaving effect" is created by drawing filaments that extend out of the secondary grid polygons, in one direction for even secondary points, the opposite for odd secondary points. 

If an adjacent primary point has a boundary through it, the line extending from the secondary point in the direction of that primary point is simply not drawn, and the corner of the polygon without a line extending from it is truncated.

A square is drawn around each secondary point, and
where there is no barrier, lines are extended based on the
even-odd rules.

Squares with missing lines can be
truncated into polygons to improve
the ribbon effect.

(Note: This post offers a slightly different description of method 1.)

method 2: Ribbon sections around the secondary points
Let's forget about the method above, and go back to the grid. Instead of filling in the spaces between the ribbon, we can draw the ribbon itself by drawing sections of the ribbon around the secondary points. Again, there is an even/odd rule in order to allow for the ribbons to pass over each other. For the node in the center, the following patterns are followed:

Adding partial paths around a secondary
node following even-odd rules

When these are joined together, the ribbon fragments form a set of continuous paths, and weave over and under each other:

portions of ribbon either join
together or appear to pass over and under

If one of the primary points surrounding the secondary point has a boundary through it, the fragments are bent and joined:

An even secondary point with a
boundary through its bottom primary neighbour.

Connecting all the lines and erasing the points and boundaries, we get something like the image below.

method 3: Ribbon sections around primary points
One final time, let's go back to the blank grid and re-draw the ribbon in a different way.

For this method, we look only at primary points that are not part of the secondary grid. This includes primary points that have (x,y) values where x is even and y is odd, or where x is odd and y is even (remember, secondary points have both x and y values even or both x and y values odd).

Like method 2, ribbon fragments are drawn, but this time the focus is on the primary nodes. again, what is drawn is different based on an "even vs odd" rule:

Lines across the primary points are drawn
using even vs odd rules

Dealing with boundaries is easier with this method, there are only two cases to consider - a vertical boundary or a horizontal boundary.

There are two cases for handling boundaries
with this method.

Any ribbon fragment that would lie outside the boundary of the grid is not drawn. Connecting all the lines and erasing the points and boundaries, we get something like the image below.

These three methods are pretty equivalent - small style alterations in any one of them can make the resulting knot look identical to one drawn using another method. When drawing knots by hand, I find that something along the lines of method 1 is easiest to use; however, from implementing each of the above in simple programs, I found that method 3 was the simplest to code.

Other Knotty Things

Other posts: 

Saturday, October 27, 2018

The unreliable guards

Here is a new puzzle variety inspired by the Forgetful Forest, Tigers and Treasure, and others by Raymond Smullyan.

Here is the setup of the puzzle:

Two guards are standing outside the entrance to a cave, guarding the treasure within. The treasure is one of copper, silver, gold, platinum, diamonds, or rubies.  
Guard 1 lies when guarding copper, silver, or gold and tells the truth when guarding other treasure. Guard 2, on the other hand, lies when guarding platinum, diamonds, or rubies, but tells the truth when guarding other treasure. 
In this land, copper is worth less than silver, which is worth less than gold, which is worth less than platinum, which is worth less than diamonds, which is worth less than rubies.

This is very similar to the Forgetful Forest, where the Lion and Unicorn each lie on particular days of the week, or in Tigers and Treasure where the inscriptions on the doors will be true only when leading to particular contents.

Just as with those puzzles, you are given clues, something like:
You meet the guards at the entrance to the treasure cave, and they make these statements: 
Guard 1 says: The treasure is more valuable than copper.
Guard 2 says: The treasure is either diamonds or rubies. 
If you determine the contents of the cave, the guards will let you pass and you can claim the treasure.
If you think you can solve this particular puzzle, try it now right here. The interactive page for this puzzle type will set you up with 838 puzzles of this variety. It presents you with a list of the treasure types, and you can select the one you think is the correct answer.

In this case, if Guard 1 says "the treasure is more valuable than copper" we can narrow down the list of possible treasures by considering two cases. In the first case, Guard 1 is telling the truth - so we know the treasure cannot be copper, silver or gold (their lying treasures); this leaves platinum, diamonds, or rubies, all of which are more valuable than copper, so the treasure could be any one of them. In the second case, Guard 1 is lying, so the treasure could be copper, silver, or gold; however, if the treasure was silver or gold, then Guard 1's statement would be true, contradicting the fact that Guard 1 is lying. So, if Guard 1 is lying, the treasure is copper, and if Guard 1 is telling the truth, the treasure is platinum, diamonds, or rubies.

Guard 1's statements provide us with a list of possible treasures: copper, platinum, diamonds, or rubies. Guard 2's statement, "the treasure is either diamonds or rubies," should narrow things down. If Guard 2 is lying then the treasure must be platinum, diamonds, or rubies (their lying treasures). However, if they are lying their statement "the treasure is either diamonds or rubies" cannot be true, so the treasure must be platinum. Looking at Guard 2's statement, there is no way it can be true because both diamonds and rubies are on Guard 2's "lying list." So Guard 2 is lying, and the only option for the treasure is platinum.

We could have solved the puzzle looking at Guard 2's statement alone: the treasure must be platinum. Because platinum is also in Guard 1's list, we can be confident that the puzzle is well-formed and that the clues are not contradicting each other.

The set of puzzles that were generated has a 'solution space' that looks like this:

The distribution shape is due to the ordering of the value of treasure types, and that we included clues that had the phrases "more valuable than" and "less valuable than" - this gave us more treasure that sat in the middle of the value range, while the ones at the ends happened less frequently. Gold and platinum satisfy the phrases "more/less valuable than x" with a greater frequency than rubies or copper.

Give these puzzles a try here. There is a Jupyter notebook here that shows how the puzzles were generated, full source for the puzzle page is here.

Illustration from Sarah Amelia Scull,
"Greek Mythology Systematized" (1880).

Thursday, September 27, 2018

some knots and not knots

Here are some knot patterns made using the online tool mentioned a few posts back. For each knot, the 'grid pattern' used to create the knot in the editor is also shown. First up, the simple unknot.

not a knot

Solomon's Knot
Next to this, we have a nice motif that is not a knot at all: the Solomon Knot is the name given to this motif of interlocked chains.

solomon unknot

BTW, you can make pattern that looks like  a solomon knot using truchet tiles:

truchet solomon unknot

Trefoil Knot
The trefoil is the simplest actual knot we can draw, but there are several ways to draw visually different but essentially equivalent trefoils, the first is considered the 'foundational' celtic knot:

trefoil 1

Here's another rendition:

trefoil 2

And one that is less recognisable:

trefoil 3

The Josephine Knot
Another non-knot (but very decorative), the Josephine consists of two interlaced links, and seems to be a favourite among crafters (who use it in belts, bracelets and macrame):

josephine link

Figure Eight Knot
The Trefoil is the only mathematically distinct prime knot with 3 crossings in a minimal planar diagram, and the figure 8 is the only one with 4. This version illustrates its name nicely:

figure eight 1

And here it is, a little lopsided:

figure eight 2

The Three-Twist
One of only two prime knots with five crossings, the three-twist (or 5_2) looks a lot like the figure 8. You can see how removing one of the lines in the grid pattern of the figure 8 allows for the additional twist that forms this knot.

the three-twist

The eight-eighteen
I don't know of a common name for the 8_18, but it's a nice looking knot, so it should have one. Here are two presentations of it:

eight-eighteen 1

eight-eighteen 2

Experiment with these and others here.

Wednesday, September 26, 2018

polynomial division practice page

I've added a new polynomial division page that generates random questions and asks you to fill in the answer, one step at a time. The page is here, along with its partners - a polynomial division calculator and example generator.

The page presents you with a randomly generated question, like this:

An initial grid is set up, with the divisor written down in the first column on the left. Everything else is unknown.

This is a grid for polynomial multiplication, but we only have one polynomial - we don't know what to put along the top for the other multiplicand. If we think of the division question as N/D = Q (numerator divided by denominator gives the quotient), the corresponding multiplication problem is DxQ = N, we have D (the denominator or divisor) and we want to find the Q to put along the top so that the contents of the grid give us N (the numerator or dividend). 

We start with the term with the highest degree in N. The page provides this prompt:

In terms of the grid, you are being asked for the coefficient for the term that will go in the leftmost empty cell in the top row.

The correct entry is -2. This allows another column of the grid to be filled in:

Now we look at the next term in N, following this prompt:

It turns out that no degree 1 term is needed in the solution since we already have all we need in the grid. When doing these by hand, you can just move on to the constant term, but on this page you actually need to put a 0 in the degree 1 column.

Moving on to the next term in N, we get this prompt:

Since there are no degree 2 terms in the table, the coefficient required is 4.

... and it turns out that the linear term also works out, as there is no remainder in this case. 

Try out the polynomial division practice page here, and visit this page for links to other posts and resources on the topic.