Thursday, December 7, 2017

Constructing Portia's Caskets

In Shakespeare's The Merchant of Venice, Portia tested her suitors by asking them to discover which of three caskets concealed her portrait. Inscriptions on the caskets presented riddles that would challenge the virtue of her potential mates. In his classic What is the Name of this Book? logician Raymond Smullyan, imagined several generations of clever Portias, who presented potential suitors with caskets inscribed with logic puzzles that provided the key to finding her hidden portrait.

On this page I have set up interactive puzzle generators that correspond (roughly) to Smullyan’s first three generations of Portias. In this post I thought I would describe what I find interesting about the way the puzzles are solved and  how they are generated. The code that generates and presents these puzzles is found here.

Here's the first Portia's Caskets puzzle in "What is the Name of this Book?":


One way to solve problems like this is to work backwards. For each casket, imagine that the portrait is concealed within that casket, then count how many statements would be true. When you find the portrait placement that matches the requirement that "at most one is true" you have your solution.

Building our first 348 Portia Puzzles

Working backwards also gives us a way to generate puzzles like this one. To generate these puzzles, consider all possible statements on the caskets. Each set of statements gives you three possible puzzles: a puzzle where the portrait is in the gold casket, a puzzle where the portrait is in the silver casket, and a puzzle where it is in the lead casket. To find out if any (or all) of these are valid solvable puzzles, check to see if the portrait placement gives you a 'truth count' that unique within that group of potential puzzles.

But what about generating 'all possible statements'? What are the statements that can be included? The statements on the caskets can be thought of as pointers to caskets, pointers that are either positive ("the portrait is in the silver casket") or negative ("the portrait is not in the gold casket"), and that may be directed at the current casket itself ("the portrait is in this casket").

For three caskets, this can be represented as an array of three integers. For example the statements for the puzzle above would be represented as [1, -2, -1], the 1 in the first position is saying that the first casket is pointing positively to itself ("the portrait is in this casket"). The -2 in the second position is saying  that the second casket is pointing negatively to itself ("the portrait is not in this casket"), and the -1 in the third position is saying that the third casket is pointing negatively at the first casket ("the portrait is not in the gold casket"). We can analyse this puzzle using a chart like the one below:


For the puzzle that says "there is at most one true statement," this means that the portrait is in casket 2 (silver), the only placement which gives at most one true statement. The chart also tells us that we cannot use this statement arrangement to make up other puzzles like "there are no true statements" or "there are exactly two true statements," as the other casket positions (p=1, p=3) both make two statements true.

So, generating this sort of Portia Casket problem is easy: first generate all lists of length three (for the three caskets) made up of the values -1, -2, -3, 1, 2, 3 (for positive and negative statements about the three caskets). Each of these lists gives a family of three possible puzzles - one for the portrait being in each casket. Check each possible solution to see how many statements become true with that solution. Any solution that gives a truth count that is unique in that family corresponds to a valid puzzle.

For three caskets, following this method of generating puzzles, we get a total of 348 puzzles. Some of these are trivially easy, as in the case where the clue is "all statements are true" and one of the caskets says "the portrait is in here."

Smullyan's first Portia puzzle, puzzle 67a, corresponds to the puzzle with identifier portia1-44 in our Portia I generator. Smullyan presents another puzzle by the first generation of Portias, puzzle 67b. This puzzle has statements [-2, -2, 3], and corresponds to portia1-271 in the Portia I generator.

All the Portia I puzzles are listed in this json file. Here is an example of one from the page:


Hopefully, you can see that we would represent the statements as [-1, -2, 2] and that the solution to this puzzle would have to be casket 1.


Finding 16152 more!

In "What is the Name of this Book?" a second generation Portia makes more difficult puzzles by putting two statements on each casket. Our Portia II generator is based on Smullyan's puzzle 68b.



It seems clear that these puzzles are very similar to the Portia I puzzles except: (1) there are two lists of statements, and (2) instead of giving a total count of the true statements, we describe the distribution ("on one lid both statements are true, on another both statements were false, and on a third one statement was true and one false").

If we model the statements as two lists of integers, such as [-1, -1, -3], [2 ,3, 1] for the above, and then for each pair of lists include puzzles where a portrait position generates a unique distribution, we can create puzzles like this one. It makes sense to exclude statement lists where the second set of statements is the same as the first, and to consider puzzles the same if we just exchange the first list of statements with the second list.

Following this approach we get a large number (16152) of puzzles (all of them are here). These are generally quite a bit trickier to solve than Portia I puzzles, although the method for solving them is essentially the same. Puzzle 68b above corresponds to portia2-6854, although the Portia II algorithm we used swaps the first statement list for the second (it generates as  [2 ,3, 1],  [-1, -1, -3]).

Here's an example of a generated puzzle:


For this particular puzzle we don't have to work backwards, we can take a direct approach aided by the contradictory statements on casket 2: We know this must be the one casket with one true statement. Since the statements on casket 1 cannot both be true, we know that this must be the casket with no true statements. This implies that casket 3 is the casket with two true statements. One of the statements on casket 3 says the portrait is in casket 2... so that is where it must be.


Bellini and Cellini give us 3600 more puzzles

Instead of telling us how many of the caskets have true statements, or how true statements are distributed across the caskets, what if solving another riddle was the key to figuring out which statements are true and which are false?


When attempting to generate "Bellini and Cellini" puzzles, I decided on an approach that does not quite match up with any of the puzzles in "What is the Name of this Book," but is a combination of Portia I, Portia II, and the "Knights and Knaves" puzzles that Smullyan describes in an earlier chapter (see this post).

For Portia III, we imagine that the caskets have inscriptions similar to Portia I, but also have an extra inscription that says something about the provenance of the caskets. For example, casket 1 might have an inscription "casket 2 was made by Bellini." You might think "great, that means that whatever is written on casket 2 must be true." Well, that is correct only if casket 1 was also made by Bellini, if it was made by Cellini, then whatever is written on casket 2 is actually false.

So, our Portia III algorithm is actually a set of Portia I statements with a "three-islander Knights and Knaves puzzle" layered on top of it. You can learn more about these here. For simplicity, a specific kind of "three islander" problem was chosen: the three caskets (islanders) point at each other using 2 "accusation/affirmations" and one "similarity/difference" statement. These are always (pretty easily) solvable. Maybe a future Portia puzzle generator will involve different varieties of Bellini & Cellini statements.

All the Portia III puzzles that the current algorithm generates are listed in this json file. Let's try one:



Casket 2 includes the inscription "Fashioned by a different maker than 1." If casket 2 is made by Bellini, this means that casket 1 is made by Cellini, since we can trust casket  2 in this case. If on the other hand, casket 2 is made by Cellini, then we should disbelieve the statement, and conclude that casket 1 is made by the same maker (Cellini). Hence, regardless of who made casket 2, we know that casket 1 is made by Cellini, and its inscriptions will be false. Now casket 1 makes the (false) assertion that casket 3 is made by Cellini - so we know that actually casket 3 is made by Bellini and must contain only true inscriptions. Casket 3 says that the portrait is in casket 2, so we believe it:


Working backwards is not the approach to take with Portia III: these puzzles require you to first solve the Bellini/Cellini riddle and figure out which caskets are stating the truth, and which are lying. Next you can use this information to follow the true (or false) statements to the portrait.

When generating these puzzles, the method is to first generate all possible Portia I statements. For a given set of statements, each possible solution (casket 1, casket 2, or casket 3) makes each statement either true or false. To verify if the puzzle is solvable, we need to check whether the portrait can be discovered once the truth or falsehood of each statement is known. There is a simple rule for this: if p is the position of the portrait, then either we need a statement with value +/-p or we need a statement for each of the remaining caskets. An example of a puzzle that does not work would be [1, 1, 1] where p = 2. The three caskets would all be lying (they would all be saying the portrait was in casket 1), but there would not be enough information to tell us if the portrait was in casket 2 or 3. The same statement list, [1,1,1] is a valid puzzle if p = 1. Once we have a solvable puzzle, we can overlay a few different Bellini & Cellini riddles that would say which caskets are lying and which are stating truths.

So, all told, these three Portias have given us 20100 puzzles, enough to keep us busy for a while. I had a lot of fun digging into them, and I hope you have fun with them as well - please try them out: https://dmackinnon1.github.io/portia/ 


Portia:
Thus hath the candle singed the moth.
O, these deliberate fools! when they do choose,
They have the wisdom by their wit to lose. 
- Act II, Scene VII, The Merchant of Venice 


Saturday, November 18, 2017

the island of knights and knaves

There is classic type of logic problem where we are asked to imagine an island consisting of two types of people: those that always tell the truth (knights), and those that always tell lies (knaves). In puzzles based on this trope, the islanders make statements, and we have to figure out which islanders are knights and which islanders are knaves.

This page will generate knight and knave puzzles of varying difficulty. Here’s an example:

An "easy" puzzle from https://dmackinnon1.github.io/knaves/

The grandfather of all these puzzles is an actual islander who referenced an actual island  - around 600 BCE, the Cretan Epimenides is credited with the statement “All Cretans are liars.” The fun has not stopped since.

The authoritative source for island puzzles is “What is the Name of this Book?” by Raymond M. Smullyan, which builds these seemingly simple puzzles from humble beginnings (knights and knaves alone on islands) to much more complicated ones that include normals (they sometimes lie, and sometimes tell the truth), the insane (they think lies are truths, and vice versa), monkeys, clubs of knights and knaves, vampires, werewolves and other characters. Using this motley crew, the book slyly leads us to a puzzle-based statement of Godel’s incompleteness theorem.

We will stick to the first type of puzzles: knights and knaves alone on an island. How do we solve the puzzle above? Here's one way to reason it out:

 
A sample solution for a puzzle generated
at https://dmackinnon1.github.io/knaves/

The puzzle generation page mentioned above limits itself to knights and knaves making three kinds of statements:

Accusations and Affirmations
In an accusation, an islander A says something like "B is a knave" or an equivalent statement like "B always lies." In an affirmation, islander A says something like "B is a knight" or "B always tells the truth."

Unfortunately, we don't know if A is telling the truth or not, so how can we know if what they are saying about B is true or not? Even without knowing the type of A, we can learn something very helpful about A and B from these statements. If A and B are linked by an accusation, they must be of different types: either A is a knave and B is a knight, or vice versa. If A and B are linked by an affirmation, they must be of the same type: either both are knights, or both are knaves. See if you can reason out why this must be so.

One approach to use when solving puzzles that feature several accusations and affirmations is to draw a diagram (as described in an old post).

Knave Conjunctions
An example of a knave conjunction, is when A says "B is a knight, or I am a knave," or  "C is a knave and I am a knave."

These are very helpful statements, as they always tell us the type of both the speaker and the spoken-of. Any islander who says "or I am a knave" will be making a statement that must be, overall, truthful and is therefore a knight, while any islander who says "and I am a knave" will by lying, and must be knave. Try and convince yourself of that.

An interesting thing about "knave conjunctions" is that their usefulness comes from how close they are to the liar paradox. The liar paradox is a more self-directed refinement of that original statement of Epimenides, where we imagine that someone says: "I am lying" and wonder if they are telling the truth or not.

An islander cannot make the statement "I am lying," or any equivalent statement such as "I am a knave." If such a statement is true, then the speaker is lying, making the statement also false; and if it is false, the speaker is lying, making the statement also true. So such a statement is contradictory - neither false or true, and our islanders are restricted to statements that are either true or false.

Islanders, however, can get close to generating the liar paradox by including its statement as a clause along with another statement. To see how they can do this, you have to be clear on how statements that include "and" and "or" work. If someone on the island says "X or Y" then only X or Y has to be true in order for the whole statement to be true. So a knight can say "X or Y" when only one of the statements is true. However, if a knave says "X or Y" then both X and Y must be false (if one was true, the whole statement would be true, and a knave cannot make a true statement). If an islander says "X and Y" then both X and Y have to be true in order for the statement to be true, and only one needs to be false for the statement to be false. So a knave can say "X and Y" when only one of the statements is false.

Similarity and Difference Statements
Sometimes an islander A might say "B is my type" or maybe "C is not my type." We might not know if A is a knight or knave, but we can infer the type of B and C right away. No matter whether A is lying or telling the truth, if A claims "B is my type," then B must be a knight. On the other hand, if A claims that "C is not my type" we know that C is a knave. Do you agree?

It is interesting to compare these statements with our first type of statements, the "accusations/affirmations," these two types of statements are reciprocal in a way. When an islander directly says what type another islander is (an accusation or affirmation), all we learn is that the source and target of the statement are similar or different, without learning the actual type. However, when an islander makes a statement about similarity or difference, we learn exactly what type the target is, without learning if this is similar or different than the source.

There are many more interesting things that islanders could say, but once you have reasoned out how these three kinds of statements work, you can beat any puzzle on the page.

Friday, November 10, 2017

trihexagonal & rhombille tilings


The image above is the superposition of two tessellations. The dark bold lines show a tiling of the plane that is made up of regular hexagons and triangles (the  trihexagonal tiling).

The light lines show portions of the reciprocal (or dual) of the dark-lined tessellation.

To create a reciprocal tessellation, for every two adjacent tiles in the original tessellation, join the centers of the two tiles by a line segment perpendicular to their shared side. This line segment becomes the edge of one of the tiles in the reciprocal tessellation.

The reciprocal of trihexagonal tiling is made up entirely of rhombs, the rhombille tiling.

Monday, October 23, 2017

Diophantine Desmos

It may happen that you have a real valued function, but only want to find those points where both the input and output are integers.

For example, consider y = sqrt(x). Suppose you had a graph of sqrt(x) and wanted to show which values of x give an integer result for y, i.e. which values of x are perfect squares:


y = sqrt(x) with only integer solutions shown

I recently learned how you can find and display integer solutions for certain types of equations in Desmos, and thought I would write a post about how to do this. 

When we care only about the integer solutions of an equation, we refer to it as a Diophantine equation. In general, Diophantine equations can take many forms - the technique described here can be used in a limited class of problems where you can express your Diophantine equation as a function k = f(n), where f takes integers n as inputs and want to know which outputs k are also integers (k > 0).

step 1 - define your real valued function
Let's see how to apply this method using sqrt(x). First, plotting the real-valued f(x) = sqrt(x) function, and creating a list of points by evaluating it for a range of integers, shows there are many points on the graph where we put in an integer, and get out a non-integer.


What we do next is to use some of the functions built into Desmos to create an integer detector function, that we can apply to the outputs of f(x).

step 2 - create the integer detector function
We'd like to build a function that can tell if a given input is an integer or not, and then use this to find out when we have an integer value for f(n). 

We would like to create an indicator function for integers that behaves like this:


To do this, we can make use of some built in functions in Desmos - the ceiling and floor functions. 

The function ceil rounds a decimal value up to the nearest integer, and floor rounds it down to the nearest integer.  Consequently, floor(x) <= ceil(x), with equality only if  x is an integer. Note also that for x > 0,  ceil(x) != 0, and floor(x)/ceil(x) <= 1, with equality only if x is an integer. The function floor(x)/ceil(x) is almost what we want - it is equal to 1 only when x is an integer. To get a function that is zero when x is not an integer, we take the floor again:


By composing t and f, we obtain a function tf which tells us when the values of f are integers. Plotting t(f(x)) for a range of integer inputs shows us which values of f give integer results.

points in red show values for (x, tf(x)), ponts
in blue show values for (x, f(x)). 

The final step is to integrate tf into our graph so that we can plot the integer solutions to y=f(x).

step 3 - taking advantage of undefined
Desmos handles undefined points gracefully - it just will not plot them. Consequently, if we create a function g, which is identical to f where f takes on integer solutions, but is undefined when it does not, we can get Desmos to plot exactly the points we want and no others.


To create g, we can combine f with our indicator function t:


Plotting points using this new function shows only those which correspond to integer solutions for f(x).

integer solutions to y = sqrt(x), graph here


Another example - Pythagorean triples
We encounter another example of Diophantine equations when trying to find Pythagorean triples. A Pythagorean triple is an integer solution to the equation a^2 + b^2 = c^2.

At first it might look like we can’t apply the method developed above to the problem of finding Pythagorean triples - there seem to be too many variables in play. However, we can explore the problem within certain ranges by taking advantage of other features that Desmos provides.

We can first define our function as a two variable function, and then use partial evaluation to obtain a new single variable function, parameterized by a slider p.


This allows us to explore Pythagorean triples where one of the legs of the triangle is fixed (determined by the value p). Using the method described above, we can find triples involving p as one of the legs.

some triples found by Desmos, 
where p=24 (graph here)

For example, with p = 24, Desmos finds the triples (24, 7, 25), (24, 18, 30), and others shown in the image above.



Some older Desmos-related posts:
- Brain and Propeller Fractals in Desmos
- Polygonal Number Diagrams using Desmos
- Spirals in Desmos
- Spirolaterals in Desmos


Tuesday, October 3, 2017

a Truchet puzzle mystery

I thought it would be fun to create a page of Truchet puzzles, and while doing this I noticed something that surprised me: even though they were randomly generated, all puzzles of the same size had the exact same level of complexity.

a single puzzle piece
that can be rotated into 4 positions

In these puzzles, Truchet tiles like the one above are used to create a specific pattern. All the pieces are the same - it is just a question of rotating them correctly to make the pattern you are aiming for.

a Truchet puzzle: can you make this pattern
using only Truchet tiles?

We can make these Truchet puzzles a bit more interesting if we have a specific starting arrangement, and add the restriction of using the smallest number of moves (clockwise rotations of individual tiles) to get from the starting arrangement to the target arrangement.

how many clockwise rotations of tiles will it take to transform
the square on the left to the one on the right?

On this page, you can try out some puzzles like this. Because you are only allowed to rotate pieces clockwise, you may have to rotate a given tile 0, 1, 2 or 3 times in order to get it into the desired position.

Please give it a try: https://dmackinnon1.github.io/truchet/match.html

When setting up this puzzle page, I used a restricted set of arrangements for both the starting and target arrangements. For the starting arrangement, I have all the Truchet tiles in the same position. Let's call this  type of arrangement a uniform Truchet square. There will be 4 different uniform Truchet squares of a given size; here is one for n = 6:

a uniform Truchet square: all tiles
are in the same position

Because I like the way they look, I chose the target arrangements to always have 4-fold rotational symmetry. An important choice as it turns out. These Truchet squares have sides of even length, and can be divided up into 4 quadrants - as we move around the quadrants in a clockwise direction, the pattern in each quadrant is a 90 degree rotation of the pattern in the preceding quadrant.

you can make Truchet squares with 4-fold rotational
symmetry - they tend to look nice.

With these restrictions, I found that:
  • All 2x2 puzzles are solvable in 6 moves.
  • All 4x4 puzzles are solvable in 24 moves.
  • All 6x6 puzzles are solvable in 54 moves.
Mysteriously, no matter what pattern was chosen for the target, all puzzles of the same size required the same number of moves to solve. 

symmetric puzzles of the same size always
have the same number of required moves

In general, it turns out that for any Truchet square T with side length n and 4-fold rotational symmetry, T will always be 6*(n/2)^2 rotations away from any uniform Truchet square.

This was more puzzling than the original puzzles: how could my randomly generated puzzles all require the same number of moves to solve?

To understand why this is the case, we can find a way to count all the rotations required to transform a uniform Truchet square into one that has four-fold rotational symmetry, and see that this does not depend on a particular choice of either the starting arrangement or the target. This turns out to be easier than you might expect.
Let U be a uniform Truchet square of side length n, and T be a Truchet square with 4-fold rotational symmetry, also of side length n. We'll count how many rotations it takes to transform U into T
Let t1 be a tile in the first quadrant of U. If we consider its image under rotation into the other quadrants, we have a set of 4 tiles, t1, t2, t3, and t4. One of these will be aligned with the corresponding tile in T (since the tiles in T that lie in the same positions as t1, t2, t3, and t4 are rotated through all 4 positions, while the tiles of U are all in the same position). It will require 0 moves for this tile be put into the same position as the corresponding tile of T. As we move around the quadrants to the other images of our selected tile, they will all be in the same position (U is uniform), but the corresponding tiles of T will be rotated. The corresponding tiles of T will be 1, 2, and 3 rotations ahead from the tiles of U. So each tile in the first quadrant will, along with its images under rotation, contribute 0+1+2+3 = 6 rotations to the overall number of rotations required to transform U into T. There are (n/2)^2 tiles in the first quadrant, hence the total number of rotations required to transform U into T will be 6*(n/2)^2.
for a given n, it always takes the same number of moves
 to transform a uniform Truchet square U into another
one, T, if T has 4-fold rotational symmetry

The reason for all the puzzles requiring the same number of moves is the 4-fold symmetry of the target (and the uniformity of the starting arrangement). If we allowed non-symmetrical target arrangements, or varied the starting arrangements used, the number of rotations required to transform our starting arrangement into the target arrangement could lie anywhere between 0 and 3n^2.

a 24 x 24 Truchet square with 4-fold rotational
symmetry - starting from a uniform square, how
many moves would be required to re-create it? 

Why do the Truchet squares with rotational symmetry seem particularly nice? The human brain loves symmetry, but in the case of Truchet squares, it seems particularly appropriate to be drawn to arrangements like these. Individual Truchet tiles lack rotational symmetry - this lack of symmetry is what gives them their expressive power. By arranging them into a square pattern that does have rotational symmetry, we are overcoming the asymmetry of the original tile, appealing maybe to our need to unify opposites, or to express a sense of dialectical tension.

Some earlier posts on Truchet tiles:
truchet en plus
truchet tiles