Tuesday, September 25, 2018

what day is it, usually?

In the Forest of Forgetfulness, Alice is trying to find out what day it is, and the unreliable denizens of the forest are not helping much. The Lion lies on Monday, Tuesday, and Wednesday and the Unicorn Lies on Thursday, Friday, and Saturday. What's more, each of them only makes one statement, and from that Alice must make her deduction.

Illustration by John Tenniel (public domain)

You can try to solve some of these puzzles here, and read about how you might solve them here.

Inspired by the original puzzles in What is the Name of this Book? by Raymond Smullyan, the Lion and Unicorn will say things like: "I told truths yesterday," or "tomorrow is one of my lying days."

If we generate a bunch of puzzles where X says "Y tells lies|truths yesterday|today|tomorrow" we end up with each creature being able to make 12 statements (after fixing the grammar a bit for verb tense). Two of those statements "I will tell truths today" (which can be said on any day), and "I will tell lies today" (which can never be said), can be thrown out,  so we get 10 statements from each creature for a combined total of 100 possible puzzles. However, it turns out that only 43 of those combinations end up generating good puzzles (puzzles where the statements lead to a unique solution). What does the set of solutions look like? We know just from the number of solutions that the 7 days of the week are not equally represented. Here's what the frequencies look like:

The first of Lion's lying days (Monday) and the last of the Unicorn's (Saturday) only occur once in the solution set, the last of the Lion's lying days (Wednesday) and the first of the Unicorns (Thursday) show up 10 times each.  The most common day is the day where they are both honest, Sunday, with 21. In this forest, it is never Tuesday or Friday.

Why not Tuesday or Friday?
This suggests a meta-puzzle: Why can Tuesday or Friday never be one of the puzzle solutions? If we look at what these days permit the Lion and Unicorn to say, we can see why this happens. Let's take Tuesday - this is a lying day for the Lion, and it happens right in the middle of Lion's lying day sequence (on Tuesday, yesterday, today, and tomorrow are all lying days). So this means the Lion can make the following statements (all lies):

I told truths today
I will tell truths tomorrow
I told truths yesterday
Unicorn told lies today
Unicorn told lies yesterday
Unicorn will tell lies tomorrow

It is a truth-telling day for the Unicorn, who can say the following:

I told truths today
I will tell truths tomorrow
I told truths yesterday
Lion told lies today
Lion told lies yesterday
Lion will tell lies tomorrow

On Tuesday, the Lion and the Unicorn can all make exactly the same statements... and also make exactly the same statements on Friday. Consequently, there is no way to distinguish between Tuesday and Friday given any pair of these statements, or tell who is lying and who is telling the truth. So none of the 36 puzzles formed by these sets of statements (the ones that could possibly be about Tuesday or Friday) are well formed puzzles (that have a unique solution).

Why is it that Sunday is so well represented in the set of puzzle solutions? Very close to half of our puzzles have Sunday as the solution (21/43). Here's an example of one of those puzzles, and here is another.

We can see how Sunday gets 21 days by listing the possible statements that can be made on that day, and seeing how the statements interact with each other. In round brackets after each statement we list all the days on which it is possible for the statement to be made (Sunday, plus some other days in some cases)

Lion's Sunday statements (all true)
I will tell lies tomorrow (Sunday, Wednesday) [5]
I told truths yesterday (Sunday, Tuesday, Wednesday, Friday) [3]

Unicorn told truths today (Sunday) [5]
Unicorn told lies yesterday (Sunday, Monday, Tuesday, Wednesday, Friday, Saturday) [3]
Unicorn will tell truths tomorrow (Sunday, Wednesday) [5]

Unicorn's Sunday statements (also all true)
I will tell truths tomorrow (Sunday, Monday, Thursday, Friday)
I told lies yesterday (Sunday, Thursday)

Lion told truths today (Sunday)
Lion told the truth yesterday (Sunday, Thursday)
Lion will tell lies tomorrow (Sunday, Monday, Tuesday, Thursday, Saturday)

Next to the Lion's statements, in square brackets we list the number of Unicorn statements that share no common days except Sunday. To Lion's statement "I will tell lies tomorrow," which can only be said on Sunday and Wednesday, all five of the Unicorn's statements can be paired to form a puzzle who's only solution is Sunday (none of the Unicorn's Sunday statements can also be made on a Wednesday). Counting up all the pairings from the list above we get 5 + 3 + 5 + 3 + 5 = 21.

Filling in some gaps

We'd like to have more puzzles, have every day represented, and not have so many Sundays. For a start, we can get some more puzzles by allowing each creature to say simply "today is Monday" or one of the other days of the week. Adding these statements increases our valid puzzle count by 67 to 110 puzzles (out of a possible 17^2 = 289 statement combinations).

Sunday more than doubles its frequency, now at 47 occurrences, and Tuesday and Friday make it in with 6 occurrences each. Monday and Saturday get 10 more occurrences, and Wednesday and Thursday get 26.

What else could we have the Lion and Unicorn say? We want them to be able to make a statement that provides a set of days as candidates for today. One example is to allow them to say "today is a weekday" or "today is the weekend." You can try out one of these puzzles here (The Lion says it is the weekend, the Unicorn says it is Friday).

Adding these two statements extend the number of statement combinations to 19^2=361, and extends the number of valid puzzles to 132. Because the 'weekend' and 'weekday' sets do not line up with the Lion and Unicorn lying days (Unicorn lies on one of the weekend days), the solution distribution is no longer symmetrical.

Monday shows up 12 times, Tuesday 6, Wednesday 38, Thursday 42, Friday 10, Saturday 13, and Sunday 54 times (down to about 41% of the puzzles).

Can we think of more statements for the Lion and the Unicorn? Sure. But with 132 puzzles to solve, let's stop here for now. Other interesting ways to change the number of solutions and their distribution is to change which days the are "truthful" for our forest friends - what if they are honest more often, and what if their lying days overlap? You can play with those questions by modifying the notebook here.