Creating Puzzles – Creativity in Mathematics

Beguiling Games III: Splotch!

In this installment of Beguiling Games, we’ll learn how to play Splotch!

Day119Splotch1

But first, I’ll start off by giving you the solution to the last puzzle I presented in the last installment. The statement of the puzzle is too long to repeat, so you can refresh your memory at Beguiling Games II.

First, it is important to note that Lucas’s statement actually provides no information! Suppose Ophelia’s card was Truthteller. Then she would have told the truth in Round 1, passed her card to Lucas, and he would truthfully have stated that she told the truth in Round 1.

But what if Ophelia’s card was Liar? Then her statement “I am a Truthteller” in Round 1 would in fact have been a lie. Now she passes her card to Lucas. He lies and says she told the truth in Round 1! What this means is Lucas could have made his statement in Round 2 regardless of what card Ophelia passed him.

Note that the same logic applies to Mordecai’s statement. He could have said “Lucas also told the truth in the first round” regardless of whether Lucas passed him a Truthteller or a Liar card.

Now let’s examine Nancy’s statement in some detail. She said that there is at least one liar at the table. Could she have lied?

Well, if the fact that the there is at least one liar at the table is false, that means everyone is a Truthteller. But there is no way Nancy could have known this, since the only two cards she saw were hers and the card passed to her by Mordecai.

That means Nancy must have told the truth in Round 2, and Mordecai must have passed her a Truthteller card. But in order for her to have sufficient information to say there is at least one Liar at the table, she must have been holding a Liar card in Round 1.

Now this information could be deduced by anyone at the table. In other words, anyone would know that Nancy held a Liar card in Round 1, and Mordecai held a Truthteller card. That leaves Lucas’s and Ophelia’s cards in Round 1.

The only person who could know both these cards would be Lucas — he knew his own card in Round 1, and he knew Ophelia’s card because she passed it to him in Round 2. So he had enough information to declare after Nancy’s statement.

It is important to point out that there is no way to know what Lucas’s and Ophelia’s cards actually were. All we need to know is that Lucas knew what both of them were.

Did you figure it out? It takes a little bit of reasoning, but all the facts were there.

Now as I mentioned in the last installment, this time I’d give you a geometrical two-player game to work out. I call it Splotch!

In the game of Splotch!, players alternate coloring in squares on a 4 x 4 grid. The goal is to create a target shape, called a splotch. A player wins when he or she colors in a square which completes a splotch, and then announces the win.

So if a player completes a splotch but doesn’t notice it and doesn’t announce the win, then play continues until someone completes another splotch. You can only call Splotch! on your turn, so you cannot win by calling it if your opponent fails to. It is also important to remember that the square you color in on your turn must be part of a splotch you announce.

In the version of Splotch! I’m sharing with you this week, the target splotch is:

Day119Splotch1

Just so you know how it works, let’s look at a sample game, shown below.

Day119Splotch2

There are two players, A and B. A goes first, and plays in the lower left corner (labelled with A1). B colors in a square in the top row (B1). Then A’s second move is in the second row. B wins on the next play by completing — and announcing! — a splotch. The splotch may be rotated (as in this example), reflected, or even both! So you’ve got to watch carefully.

Now admittedly, A was not a very clever player in this round of Splotch! In fact, B could also have won by playing as follows:

Day119Splotch3

But here is the question: In this version of Splotch!, which player can force a win every time? Remember: you must be able to provide a response to every move by your opponent! I’ll reveal which player can force a win in my next installment of Beguiling Games, and I’ll share my particular strategy for winning.

One final remark — a bit of a tangent, but related to puzzles and games. If you’ve been following my blog for a long while, you might remember my (fiendishly diabolical) number searches. (These were posted well over a year ago.)

Day031Fig1

Here, the numbers in the right are in base 10, but you have to convert them to another base to find them in the grid! You can read more about these puzzles here and here.

I submitted these puzzles to MAA Focus, the newsmagazine of the Mathematical Association of America. I am happy to report that they will be featured on the Puzzle Page in the December 2017/January 2018 issue!

Now I will admit that this doesn’t exactly make me famous, given the number of people who subscribe to MAA Focus. But I composed these puzzles specifically for my blog — so if I hadn’t decided to write a blog, these puzzles might never have been created. Perhaps another reason to write a blog!

Stay tuned for the next round of Beguiling Games, where you’ll learn (if you didn’t already figure it out for yourself) who has a winning strategy in the game of Splotch!

Geometrical Dissections III: Octagons and Dodecagons

It has been quite a while since I’ve written about geometrical dissections. For a brief refresher, you might want to look at my first post on dissections.

But recently my interest has been rekindled — to the point that I started writing a paper a few weeks ago! I often like to share mathematics I’m working on as it’s happening to give you some idea of the process of doing mathematics. The paper has quite a bit more mathematics in it than I’ll include in this post, but I’ll try to give you the gist of what’s involved.

Recall (again, see my first post for a more thorough discussion) that I’m interested in finding dissections that you can draw on graph paper — I find these more enjoyable as well as being accessible to a wider audience. So all the dissections I’ll talk about will be based on a grid.

The first example is a dissection of two octagons to one, such as shown below.

Day118Dissection2

In other words, you can take the pieces from the two smaller octagons, move them around, and build the larger octagon. If you look carefully, you’ll notice that the larger octagon is rotated 45° relative to the smaller octagons. Geometrically, this is because to get an octagon twice the area of a given octagon, you scale the side lengths by $\sqrt2.$ Imagine a square — a square with side length $S$ has area $S^2,$ while a square with side length $\sqrt2S$ has area $(\sqrt2S)^2=2S^2$ — which is double the area.

Now think of a segment of unit length. To get a segment of length $\sqrt2,$ you need to take a diagonal of a unit square, which rotates the segment by 45° as well as scales it by a factor of $\sqrt2.$ This is why the larger octagon is rotated with respect to the smaller ones.

But what makes this dissection interesting is that there is an infinite family of very similar dissections. By slightly varying the parameters, you get a dissection which looks like this:

Day118Dissection3

Here, you can clearly see the 45° rotation of the larger octagon. I always enjoy finding infinite families of dissections — it is very satisfying to discover that once you’ve found one dissection, you get infinitely many more for free!

The proof that this always works (which I will omit here!) involves using a geometrical argument — using arbitrary parameters — to show that the green triangles always have to be right isosceles triangles. This is the essential feature of the dissection which makes it “work” all the time.

The second example I’m including in the paper is a dissection on a triangular grid, like the one below.

Day118Dissection4

Note that the figure on the left is an irregular dodecagon; that is, it has twelve sides. Recall that the interior angles of a regular dodecagon have measure 150° — but so do the angles of this irregular dodecagon as it is drawn on a triangular grid.

If you look carefully, you’ll see how the sides in the pieces of the dissection on the right match up with sides of the same length from the other pieces. Also, looking at the dissection on the right, you’ll see that around all the interior vertices, there are two angles with measure 150° and one with measure 60°, adding up to 360° — as we would expect if the pieces fit exactly together.

And — as you might have guessed from the first example — this is also one of an infinite family of dissections. As long as the sides of the irregular dodecagon alternate and the vertices stay on the triangular lattice, there is a dissection to a rhombus. Below is another example, and there are infinitely many more….

Day118Dissection5

My third and final example involves irregular dodecagons, but this time on a square grid. And while I found the previous two dissections several years ago, I found this example just last week! What inspired me was one of my favorite dissections — from an irregular dodecagon to a square — also found many years ago.

Day118Dissection1

In the spirit of the first two examples, I asked myself if this dissection could be one of an infinite family. The difficulty here was that there were three parameters determining an irregular dodecagon, as shown below.

Day118Dodecagon

We do need $b>c$ so that the dodecagon is convex and actually has 12 sides; if $b=c,$ four pairs of sides are in perfect alignment and the figure becomes an octagon.

There is an additional constraint, however, which complicates things a bit. The area of this dodecagon must also be the area of some tilted square with vertices on the grid, as illustrated below. Note that the area of this square is just $d^2+e^2.$

Day118Square

It is not a difficult geometry exercise to show that the area of the dodecagon is $a^2+4(a+b)(c+b).$ So in order to create a dissection, we must find a solution to the equation

$a^2+4(a+b)(c+b)=d^2+e^2.$

Again, here is not the place to go into details. But it is possible to find an infinite family of solutions when $a=e.$ You get a dissection which looks like this:

Day118Dissection6

I was particularly pleased to have found this eight-piece dissection since most of my attempts until this point had ten pieces or more. And to give you a sense of this family of dissections, here is an example with different parameters within this family.

Day118Dissection7

You can definitely see the resemblance, but it is also clear that the dodecagon and square are not the same shape as those in the previous dissection.

So these are the three families of geometrical dissections I’ll be including in my paper. I hope these examples might inspire you to pick up a pencil and graph paper and try to find some infinite families of your own!

The One Four Conjecture

I can’t remember when I first heard of the “Four Fours” puzzle. The goal is to use four 4’s to create as many different integers as possible using basic arithmetic operations. For example,

$42=44-\dfrac4{\sqrt 4}.$

Which numbers are possible to obtain depends on the range of operations or functions allowed. Using a decimal point and a bar for a repeating decimal, for example, allows expressions such as

$103=\dfrac{44}{.\overline 4}+4.$

You can read more about this puzzle on this Wikipedia page, and look at the references there for even more information.

A few years ago, I wondered about what numbers are possible using just one 4. Of course there aren’t many if you restrict yourself to the basic arithmetic operations. But you can write $4!= 24,$ for example.

So the factorial was a way to make numbers larger, but then what about bringing those factorials back down? The square root function does that, but then you need to convert to an integer. So perhaps use the floor function, so that the second function you use is

$f(n)=\lfloor\sqrt n\rfloor.$

Now this is a bit trickier — even small numbers are not so easy to obtain. For example,

$5=\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor \sqrt{(4!)!}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor.$

That’s a lot of work just to get 5…. But as I kept on exploring using Mathematica, it seemed that eventually, you could get every positive integer this way!

At first, it was really hard to believe — but the more I worked, the more plausible it became. It soon became obvious that other numbers other than 4 were possible to begin with. You could start with 9, for example, since then you could get 4 by

$4=\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor \sqrt{9!}\right\rfloor}\right\rfloor}\right\rfloor,$

and then proceed from there.

Further, why use a square root? Could other roots work as well? More experimentation seemed to suggest that any root might also work. This led me to the following:

The One $n$ Conjecture: Suppose $n>2$ and $p>1$ are given. Then using the factorial function and the function

$f(n)=\lfloor n^{1/p}\rfloor,$

all positive integers may be obtained by some composition of these functions.

This seemed really difficult to prove. Suppose, for example — using the factorial and square root functions — it is impossible to obtain some particular integer no matter what input you start with. Of course it is always possible to obtain $n$ from $n^2,$ and $n^2$ from $n^4,$ and so on, but you’ve got to get larger first, and that requires some use of the factorial.

It turns out, however — in a particular sense (which you’ll see in a moment) — it is always possible, for any $p.$

The Possibility Lemma: Suppose $p>1$ is given. Then for any positive integer $k>1,$ there exist positive integers $q,m$ such that

$k=f(f(f\cdots f(m!)),$

where the function $f$ is composed $q$ times.

Let’s focus on the square root for now — that is, $p=2.$ The Possibility Lemma is only a starting point, since it turns out that most of the time, the smallest $m$ need to generate a particular $k$ is actually greater than $k$ — making an induction proof based on the Lemma impossible.

For example, for $k=42,$ the smallest $m$ is $218$ with $q=8,$ so that

$42=f(f(f(f(f(f(f(f(218!)))))))).$

But for $k=43,$ we get

$43=\left\lfloor\sqrt{\left\lfloor \sqrt{10!}\right\rfloor}\right\rfloor.$

It seemed that the least $m$ needed to generate a given $k$ exhibited rather erratic behavior. So my next step was to plot a graph of the least $m$ given $k.$

I won’t go into all the details here — but it took a little work to optimize the algorithms. As an example, the smallest $m$ needed to generate $k=48,\!500$ is $m=890,\!827,$ and computations with such large factorials take time. It turns out that the trick was to compute in advance the first 1,000,000 factorials as floating point numbers. A little accuracy is lost as result, but several checks suggested that even so, the correct value of $m$ is found each time.

So here is the plot of values for the least possible $m$ for $k$ from 1 to 5,000.

OneFour5000

And here’s the plot for values of $k$ from 1 to 40,000.

OneFour40000

Now here’s something interesting! You can’t help but think “fractal behavior” here. And why the thin bands? Not sure yet, but they somehow correspond to square roots of factorials. For example, the $m$ for 49,998 is 470,324, and the $m$ for 49,999 is 248,312, and the square root of 470,324! is not too far off from 248,312!.

But although it looks like there are thin bands, they are not uniformly generated. Here’s a closeup of the previous graph in the range 49,900 to 50,000.

There doesn’t seem to be a predictable pattern as to when the jumps are made.

And it does appear that the thin bands have an upward trend. Might it be possible that every positive integer is eventually the $m$ for some $k$ ? Not an easy question to answer.

And this is only a beginning! I just generated the graph up to 50,000 yesterday, so I haven’t had time to analyze it in any more detail. Using $p=3$ generates the following graph, so it seems that there may be similar behavior for various $p.$

OneFour5000p3

I plan to keep working on this little puzzle — although I think a proof of or counterexample to the One $n$ Conjecture is rather far off. When I do make more progress, I’ll give you an update. Despite the difficulty of the problem, this is a really fun puzzle to play with! I hope you might give it a try, too….

Number Searches II

This week I’ll talk about the solution to the final puzzle from last week — so if you haven’t tried it yet and want to, now’s the time!

For reference, here’s the puzzle:

Day031Fig4

The hints were that all circled numbers in the grid were four digits long, and that every number in the grid was used at least once. The object was to determine two bases: the base used to write the numbers in the list, and the base used for the circled numbers in the grid. Then the rest is easy!

To start, I chose the bases first. My first attempt was to use 41 and 19, although this didn’t quite work out (for reasons we’ll soon see). I didn’t want the numbers in the list to be too long, so I chose bases which weren’t too far apart. The bases happened to be prime numbers — but later on I saw that this information really doesn’t help the solver at all. No harm done, though.

Now the main issue was that I wanted the numbers both in the list and the grid to use only the digits 0–9. So next I used a brute-force loop to check all numbers up to 10,000,000 which only used the digits 0–9 in base 41. Of these, I checked which used only the digits 0–9 in base 19. There were only 2640 numbers — not very many, actually, out of 10,000,000. (I used Mathematica here, since using Python in the Sage platform would have been far too slow. Also, it is very easy in Mathematica to convert numbers from one base to another using the functions “IntegerDigits” and “FromDigits.”)

But what was I going to do with these numbers? I decided I wanted a solution strategy which didn’t use the ending 0 again — I had used this device twice already. I thought that if I looked for numbers which were off by just 100 in base 41 in the grid — and made sure the solver had enough clues to determine the corresponding numbers in the list — well, I’d be making progress.

Let’s look at the puzzle for a moment, so you see what’s at play here. Notice that the largest number is roughly three or four times the smallest (3 x 1 = 3 in any base larger than 3!). But there are two small numbers close to each other — 14940 and 14965 — they can’t begin with 0, naturally, and there is only one number you can circle in the grid beginning with a 1. So they must at least start with a 2. But they can’t start with a 3 or greater, or else the largest numbers would have to start with at least a 9 — and 7 is the largest number in the grid. Therefore the two smaller numbers must start with a 2, and the three largest must begin with a 7.

And you’ll notice that there are the two numbers 7034 and 7134 in the grid — off by 100. But here was my problem — when I looked at my list of numbers which used only the digits 0–9 in both bases 19 and 41, I couldn’t find any which were 100 apart in base 41.

Then I realized why. In base 41, 100 represents 41² = 1681. And the base 19 digits of 1681 are 4, 12, and 9. See the problem? There’s no way to be off by 12 in the base 19 list using only the digits 0–9!

So I needed to find a base whose square could be written in base 19 using single digits. It turns out that 41 wasn’t too far off….43² = 526₁₉. And if you notice, 45311 and 45837 are off by exactly 526. Recall that since these are the largest numbers, they must be the ones beginning with a 7. (Note that the other four-digit number in the grid, 7042, is between 7034 and 7134, and so must correspond to 45334.)

What does this mean algebraically? Let’s denote by L the base used in the number list, and let G be the base used in the grid. To say that being off by 100_G in the grid is the same as being off by 526_L in the list is to say that

G² = 5 L² + 2 L + 6.

So this is one relationship between G and L.

Now there are two ways to proceed. You might try to figure out another relationship between G and L using 7042 and 45334. Note that 7042 is in fact G – 2 more than 7034 (observe that a carry is involved), and 45334 is 23 more that 45311. This would mean that

G – 2 = 2 L + 3.

Alternatively, note that the smallest two numbers must be represented by 2154 and 2164 in the grid (2407 is too big, since the numbers are only 25 apart in base L). But 2154 and 2164 are just 10 apart in base G, so

G = 2 L + 5,

which you’ll note is equivalent to the previous equation.

But we now have two equations in two unknowns — just substitute for G into the quadratic, rearrange terms and simplify, and you’ll end up with the quadratic equation

L² – 18 L – 19 = 0.

It’s not hard to see (just factor!) that the only positive root of this equation is L = 19. This means that

G = 2 x 19 + 5 = 43.

So we’re just about done! I’ll leave it to you to do all the conversions from one base to the other. But once we know the bases, the rest is easy.

Of course there was no way I could have created this puzzle without a computer — finding numbers which can be written with the digits 0–9 in two different bases is just too difficult to do by hand (at least for me). But even when this was done, it was not a trivial task. I pored over the numbers, looking for ones with the “right” digits. Since I wanted the largest numbers to begin with 7, I avoided 8’s and 9’s in the corners. I thought the solver needed some entry point without having to go down too many dead ends.

And then, well, the numbers had to fit. Since the corners are common to so many entries, I had to look for numbers which started and ended with suitable digits. This took some creative juggling!

Finally, I wanted to make sure that there were numbers differing by 100 and 10 in the grid. Again, the solver needed an entry point into the puzzle. Just writing a computer program to look at every single possibility could be done — but then why spend all the effort making a puzzle which can, in large part, be solved by hand? Just randomly picking numbers and writing them in bases 19 and 43 would certainly have been possible, but far from interesting.

If you feel adventurous enough to create your own Number Search puzzle, please comment. I’d love to see what others might do with this idea!

Number Searches I

It’s been some time since there have been any puzzles to solve. I’ve created something new (well, as far as I know) just for my blog. I hope you enjoy it!

Many puzzle magazines have puzzles where you need to find words or numbers hidden in a grid. They may be placed in a straight line horizontally, vertically, or diagonally, and may be written either backwards or forwards. Here’s one for you — find the numbers at the right in the grid on the left.

Day031Fig1

Looks like there’s not enough room? Well, there’s a twist in this puzzle. The numbers are written in base 10 on the right, but in the grid, they’re represented in a different base, which you need to determine. Now this is a bit trickier, so I’ll give you two hints. First, the base is a prime number. And second, all the numbers in the grid are used in the completed puzzle. We’ll work out the solution next — so if you want to try to solve it on your own, now’s the time.

Impossible? Seems like it — until you notice where the 0’s are in the grid. Since numbers don’t begin with a 0, and since you’re given that every number in the grid must be used — that means that some numbers end in a 0, meaning they’re a multiple of the base. And since you’re given that the base is prime, that suggests looking at the prime factorizations of the numbers on the right.

You can look at some python code to find prime factorizations of numbers — both recursive and iterative versions.

112	2⁴ . 7
373	prime
3181	prime
8533	7 . 23 . 53
11,665	5 . 2333
14,420	2² . 5 . 7 . 103
1,354,097	29 . 53 . 881

This table shows the prime factorizations of the numbers to be found in the grid.

So what do you notice? Since at least two of the numbers end in 0 in the grid, at least two of the numbers must share a common prime factor. The only prime factors that any numbers have in common are 2, 5, 7, and 53.

But note that there are the digits 8 and 9 in the grid — which means that the base must be at least 10. This eliminates all possibilities except 53.

Alternatively, you can notice that any number on the right can be expressed using at most four digits in the “mystery” base. Since 34⁴ is only 1,336,336, the base must be at least 35. This would also eliminate all options except 53.

Once you know the base, the rest is fairly straightforward — once you know how to write numbers in base 53! Luckily, I’ve also written some python code to perform this task for you, as well. It’s the usual algorithm — find the highest power of 53 less than the number (using logarithms), find the corresponding digit, subtract, and repeat. You’re welcome to take out your pocket calculator, write your own code, or just use mine. But there’s no avoiding this task.

Whatever the method, you should have come up with the following results in base 53, listed in increasing order: 26, 72, 171, 320, 485, 574, and 9530. Below you’ll see the completed puzzle.

Day031Fig2

Where did this idea come from? It’s never possible to say exactly where an idea “comes from.” I was thinking about taking an ordinary puzzle and adding a new twist. The idea of using different bases popped into mind.

Then the challenge was to create a puzzle that had some interesting feature — like the 0’s. I knew that one way to solve the puzzle would be to write a computer program which would take all the numbers in the list, and write them in different bases starting (in this case) at 35. Then see which lists could be found in the grid. Not so very interesting.

But with the hint and two zeroes in the grid, well, I felt I was making some progress — and I hope you’ll agree….

Now I needed to come up with another puzzle or two — which were related to the example, but which didn’t simply require going through the same steps. Maybe only one zero instead of two? How was that much different? I pondered for a few minutes, and came up with the following.

In the following Number Search puzzle, find the numbers on the right in the grid on the left (written in some prime base). Fill in all the missing numbers (which are all single digits) in the grid, and find the missing number in the list on the right (which is in increasing order). You know that every number in the grid is used in the completed puzzle, and that the missing number on the right does not end in 0 when circled in the grid. Good luck!

Day031Fig3

Although likely a challenge if you’ve never done a puzzle like this before, I thought it must be possible to introduce still another level of difficulty for the truly dedicated solver. So here’s another.

In the following Number Search puzzle, find the numbers on the right in the grid on the left. The catch? The numbers on the right are not written in base 10 (although they are all written in the same base), and the numbers to circle in the grid are also not in base 10 (although, again, they are all in the same base). Your task to find both bases and solve the puzzle!

Day031Fig4

The bases are prime (but I don’t think that will actually help at all). A few other hints: as in a usual search puzzle, you can’t count “1011” and “1101” as two different numbers — once you circle a set of numbers, you can’t use it again in the reverse order. Of course no number in the grid begins with “0.” And finally, all circled numbers in the grid are four digits long, and every number is used at least once. As a further tease, you can find out the bases with just a few lines of algebra — you only need a computer/calculator to convert from one base to the other!

Next week, I’ll explain how I designed the puzzle (and in doing so, give the solution as well) — there were two big hurdles. First, the numbers had to use only the digits 0–9 in both bases. And second, I wanted to be sure there was some way to solve it without an exhaustive computer search. More next week. Happy solving!

Logic Puzzles I

Some of my favorite puzzles to create are logic puzzles. There are many reasons for this — you can often create humorous scenarios for your puzzles (like Trolls wearing hats). Also, there are typically multiple entry points into a solution — you can start with any clue you like!

I’ll let you do a review of simple logic; you should be familiar with truth tables, conjunctions, disjunctions, implications, and biconditionals, for example. In this week’s post, we’ll start by solving a simple puzzle — and in doing so, discuss several tricky points in working with mathematical logic.

We begin in the Land of Pergile, where four friendly trolls — Cedric, Dillon, Elbyn, and Fenn — are wearing four different but brightly colored hats of the red, blue, green, and yellow varieties. Here’s what you know:

Dillon is wearing a yellow hat if and only if Elbyn is wearing a green one.
Either Dillon is wearing a red hat, or Fenn is wearing a yellow hat.
If Dillon is wearing a red hat, then Cedric is wearing a blue one.
Cedric’s hat is either red or yellow.
If Cedric’s hat is blue, then Elbyn’s is green.

Where to begin? Let’s look at clues 3 and 4. Suppose Dillon’s hat is red. Then from clue 3, Cedric is wearing a blue hat. But clue 4 says his hat is either red or yellow — not blue. So our original assumption that Dillon’s had is red must be false. Therefore, we know that Dillon is not wearing a red hat.

Now since Cedric’s hat is either red or yellow, it can’t be blue. So from clue 5…well, nothing. Remember that if the antecedent of an implication is false, you can’t conclude anything about the consequent. In other words, since Cedric’s hat is not blue, you can’t conclude that Elbyn’s hat is green — but you can’t conclude that his hat is not green, either. So we really can’t learn any more information from clue 5.

Now let’s look at clue 2. Keep in mind that it is possible for both Dillon to be wearing a red hat and Fenn to be wearing a yellow hat. In general, a disjunction (that is, an “or” statement) is inclusive. (Although in clue 4, this is certainly not possible — but in general you have to consider that both clauses in a disjunction may be true.)

Now we’ve already established that Dillon is not wearing a red hat — so that means that Fenn must be wearing a yellow hat. At least one clause in a disjunction must be true. Then we use clue 4 to establish that Cedric must be wearing the red hat, since Fenn is wearing the yellow hat.

We haven’t used clue 1 yet. Recall that in a biconditional statement, both clauses have the same truth value — both are true, or both are false. In this case, they can’t both be true, since we already know that Fenn is wearing the yellow hat. So they must both be false.

Therefore Dillon is not wearing a yellow hat, which doesn’t really help us since that fact gives us no information about the color of hat he is wearing. But also, Elbyn is not wearing a green hat — and since the red and yellow hats are already accounted for, he must be wearing the blue hat. That leaves Dillon wearing the green hat.

Problem solved! Now if you know your way around logic problems, this might have seemed simple. But if you’re new to them, you realize you have to be very careful about the conclusions you make.

Of course maybe you just guessed the right answer and found no contradictory statements. But part of solving these problems is showing that you’ve found the only solution — and that means using the rules of logic to exclude all other possibilities.

And of course you might used the clues in a different order. You can eliminate any help from clue 5 by looking at clue 4 first, and then consider clue 3. Or you can take a completely different approach with clue 1. For example, if Dillon’s hat is yellow, then neither clause in clue 2 can be true — which yields a contradiction. So Dillon’s hat can’t be yellow. The point is that there is not just one way to solve any of these problems — which is part of the fun! But you’ve always got to make some tentative decision about where to begin.

Now here’s one for you to figure out. As it happens, the four friendly young Trolls decided to skip school one Afterday morning and go shopping for new hats! Excited — though not particularly adventurous — they each bought another hat which was either red, blue, green, or yellow. (It is possible that a Troll bought the same color hat as he was already wearing.) From the following clues, can you deduce what colors their new hats are?

If Fenn bought a green hat, then Dillon bought a yellow hat.
After all the new hats were purchased, either Cedric and Dillon did not share a hat of the same color, or Elbyn and Fenn did not share a hat of the same color.
If Cedric’s new hat was blue, then Elbyn’s new hat was green.
Either Dillon or Fenn bought a new blue hat.
If Dillon did not buy a hew red hat, then Elbyn did.
If Cedric bought a new yellow hat, then so did Fenn.

You can easily create logic puzzles of your own. I find it easiest to start with a solution, write clues which describe the solution, and then see if you have enough clues as well as check that the solution is unique. There’s a certain amount of back-and-forth work here — you don’t always get it right the first time…. The second problem took a little while to get the clues right — I wanted a variety of clues (sharing the same color hat, implications and disjunctions, etc.), and I wanted to make sure there was a clear solution path. Maybe you’ll find it…..

Finally, here’s another short puzzle to test your logical prowess. After their hat-buying excursion, Cedric decided to go to the local produce stand, where he bought a basket of his favorite fruits: apples, bananas, and choobles. In all, he bought ten pieces of fruit. Given the following true statements made by Cedric, how many pieces of each fruit did he have in his basket?

If I don’t have more choobles than bananas, then I have two more apples than bananas.
If I have more choobles than bananas, I have three apples.
If I have fewer than four apples, then I have the same number of bananas as choobles.
The number of pieces of one of the fruits is the same as the sum of the number of pieces of the other two fruits.

Happy solving!

Roman Numeral Puzzles

Today, I’ll talk about a set of puzzles I created just for this blog. The problems you’ve seen before — CrossNumber puzzles and Cryptarithms — I’ve been creating for many years. But in writing a blog about creativity in mathematics, I feel I should occasionally create something new….

I call these “Roman Numeral Puzzles” since they involve using Roman numerals in an interesting way. If you’re not familiar with how Roman numerals are written, just search online. (The internet knows everything.)

So here’s how the puzzles go. Fill in the following grid with the digits 0–9 and the letter X so that each row and column is either a number or a mathematically correct statment. The 1 may represent either the number 1 or an I in Roman numerals, and the X may represent either a multiplication symbol or an X in Roman numerals. For example, the second row may be XXX (the number 30 in Roman numerals), or 5X6 (since $5\times6=30$ ), or 3XX, where the first X represents multiplication, and the second X the number 10. What an I or X represents in a row may not the same as what it represents in the corresponding column. And as usual, no number can begin with a “0.” Happy solving!

Day018Grid1

Let’s work through the solution for this puzzle together. Then there will be two more for you to try on your own.

First, look at the second column. It can’t be 100, since there would be no way to write 12 in the third row with a 0 in the middle. So the second column is a multiplication, and the only way to write 100 using three symbols is XXX, which we interpret as $10\times10.$

In the third column, there is no way to write 40 as just a number, so it must be the result of a multiplication. So far, we have

Day018Grid2

Now think about how we can write 40. There are only four ways: 4XX, XX4, 5X8, and 8X5, where in the first two cases, one “X” is the multiplication symbol, and the other “X” represents the number 10. Since the first and third rows must be multiplications and 8 is not a factor of 20 or 12, that leaves 4XX or XX4. But 10 is a factor of 20 (and not 12), so we’ve got to use XX4. Once we have this, the rest is easy to fill in:

Day018Grid3

These puzzles aren’t difficult to make. You can begin with a grid, and simply fill it in with symbols and work out the values for the rows and columns. Try to think of using numbers which can be represented in different ways. For example, in the $4\times4$ puzzle below, I used 13 since it might either be written as a Roman numeral XIII, or a multiplication like 1X13. Having some entries end in 0 means a multiplication by 10, but that might be represented by 10 or X.

I can’t exactly remember what prompted me to bring in Roman numerals this way. You just let your mind wander — thinking about puzzles you are already familiar with, pushing the boundaries a bit — until your mind just “snaps” and you’ve got a concrete idea to try. Better minds than I have tried to pin down the creative process, so I won’t try to do that here. But I’m not really sure we’ll ever really undertand it….

Now the biggest challenge is solving your own puzzle and making sure it has a unique solution. Sure, you might say “find all solutions” — but as a puzzle maker, you really want just one solution. This is somehow more satisfying — if you create enough puzzles, I think you’ll see why. Good luck! And if you come up with any of your own puzzles, post them in a comment.

Here’s the $4\times4$ puzzle.

Day018Grid4

And for a real challenge, here is a $5\times5$ puzzle.

Day018Grid5

I hope you enjoy solving these puzzles. Let me know how it goes!

Geometrical Dissections I

Closely related to the problem of tiling the plane with polygons is that of dissecting one geometrical object into pieces that can be rearranged to form another. The classic example is the following dissection of an equilateral triangle to a square, attributed to Henry Dudeney, 1907.

Day014TriToSquare

Note that the pieces are exactly the same in both polygons. It’s not hard to appreciate the beauty and elegance of this “geometrical artwork.” And it’s not hard to imagine a puzzle based on this dissection — give the puzzler these four pieces with instructions to make both a triangle and a square from the same pieces.

This led me, once upon a time, to construct an Honors Geometry course centered around geometrical dissections using Greg Frederickson’s wonderful Dissections Plane & Fancy.

But even “simple” dissections — involving triangles and squares — weren’t so easy to create. For example, the pieces divide the base of the equilateral triangle into lengths Day014formula and these are some of the easier calculations! I won’t say more about that here — but you can read all about this dissection and many others in Greg’s book.

So I was fascinated by geometrical dissections — but I needed a way to make the idea accessible to my students. I thought — what could you create just by experimenting with dissections on ordinary graph paper?

Well, I have been answering this question for over 15 years now. I’ll start with some introductory ideas in this post, but this is definitely not the last word on dissections!

Let’s begin with the following puzzle. By cutting the rectangle along the grid lines, how many pieces are needed so you can also make the square with a corner missing? Day014Puzzle1A This seems like an easy puzzle to solve, as shown below. Day014Puzzle1B So yes, only two pieces are necessary — but one had to be rotated. Here is the question: can this puzzle be solved with just two pieces, but with neither piece rotated?

It turns out this is possible — but a solution requires a bit more creativity. Here is one way to do it: Day014Puzzle1C This is a solution technique commonly used in Dissections Plane & Fancy. Why bother? In the world of geometric dissections (and it is a growing universe, surely, as any internet search will show), finding a minimum number of pieces is the primary objective. But of all solutions with this minimum number of pieces, “nicer” solutions require rotating the fewest number of pieces. And rotating none at all is — in an aesthetic sense — “best.” It is also preferable not to turn pieces over, although sometimes this cannot be avoided for minimal solutions.

Another criterion for solutions might be whether they can be hinged or not, as Greg discusses extensively in Hinged Dissections: Swinging & Twisting. We won’t have time to explore this topic today.

Of course there is no reason you have to start with a rectangle, and also no reason why you need to restrict yourself to just one shape. The puzzle below shows how you can find a four-piece, rotation-invariant dissection from two smaller octagons to one larger octagon. Day014Puzzle2 It is important to note that the octagons here are not regular. A quick glance through Dissections Plane & Fancy will reveal that dissections involving regular polygons are generally rather difficult (as the initial triangle-to-square example amply shows).

Further, “two-to-one” dissections lend themselves nicely to a square grid, as the diagonal of a unit square has length square root of 2. Take a moment to study the octagon dissection again — paying particular attention to the side lengths — to see how this plays out. In the world of regular polygons, however, two-to-one dissections are in general quite difficult. Visit Gavin Theobald’s web page of two-to-one dissections to see some fascinating examples.

It is not hard to create dissection puzzles of your own — a pencil, eraser (!!!), and graph paper are all you need. What is difficult, however, is proving that you’ve found the fewest number of pieces. And when you have, proving that your dissection is unique. Uniqueness is virtually impossible to prove, but sometimes you can get a handle on minimality. For example, if the octagon dissection could be done in three pieces, one of the smaller octagons would have to be uncut. It’s not hard to see that there is no way of cutting the other smaller octagon into just two pieces to create the larger octagon.

What I enjoy about creating dissection puzzles is that there is not a single strategy you can use to solve them. You really need to use your imagination. Sometimes you might even surprise yourself by stumbling upon a really neat puzzle, like the one below.

Here, an 8 x 8 square with four holes (shown in black) can be dissected into three pieces to create a 6 x 10 rectangle, although one piece needs to be rotated. There is a simple elegance about this dissection which I find appealing. Day014Puzzle3

Another grid which lends itself to creating dissections is a grid of equilateral triangles. We won’t go into details here, but you can get the idea with the following dissection of an irregular dodecagon to an equilateral triangle in just five pieces. (The minimal dissection with regular polygons requires eight pieces.) Day014Puzzle4 I’ll leave you with two puzzles to think about. Of course, you can just make up your own. If you come with anything interesting, feel free to comment!

For this puzzle, my best solution is four pieces, without needing to rotate any pieces or turn any pieces over. (Black squares are holes.) Day014Puzzle5

For the last puzzle, my best solution is five pieces — but I had to turn over and rotate two of the pieces. Day014Puzzle6

A parting suggestion: when looking up dissections on the web, be sure to use the search words “geometrical dissections…..”

ColorSlide Puzzles

Part of the fun of writing a math blog is designing new puzzles. I wanted to come up with a puzzle which incorporated color and logic, so here’s the result!

In the grid below, slide the tiles either horizontally or vertically onto the grid so that each row and column contains exactly one each of green, cyan, magenta, and yellow dots. When two dots share the same square, they are combined, so that if a green and a red dot occupy the same square, the dot is yellow, while if a blue and a green dot occupy the same square, a cyan dot is produced. In other words, overlapping the tiles is like adding their RGB values. (If you aren’t familiar with RGB values, you can experiment in the “Continue reading” section by searching for Day002 in my blog.) Horizontal tiles may only overlap vertical tiles (and not other horizontal tiles), and vertical tiles may only overlap horizontal tiles.

Dots of the same color may never overlap — although this condition follows from the puzzle setup. Note that green, cyan, and yellow all require a green dot, so with four rows/columns, at least 12 green dots are necessary. Since there are exactly 12 green dots, no two green dots may overlap. Similar arguments show that no two red dots or two blue dots may overlap, either.

In the first part of the post, we’ll solve this puzzle so you see what’s involved. We’ll look at the design later.

Let’s start by looking at Column 1. Each row column needs three green dots, two red dots, and two blue dots — this follows from the fact the the RGB values of the four colors in the completed puzzle are (0,1,0), (0,1,1), (1,0,1), and (1,1,0). Since the vertical tiles in Column 1 already include three green dots, we know how to place the tiles in Row 2, since we need to avoid a fourth green dot in the first column. This results in

Now see that however the tiles are placed in Column 1, the dot at (2,1) — Row 2 and Column 1 — must be yellow. So (2,4) can’t be yellow, and therefore we know how to place the tiles in Column 4.

Note how the red and blue dots overlap to create magenta. Since there are no blue dots in the completed puzzle, we must place the tile in Row 3 so that the blue dot is covered by a green one (making a cyan dot).

Since green dots cannot overlap, we know how to place the tiles in Rows 1 and 4. Note the red and green dots overlapping in (4,4) to create yellow.

Since green dots cannot overlap, we know how to place the tile in Column 2. See how the overlapping dots create yellow, cyan, and magenta dots.

Now in Column 1, there can only one be yellow dot. So we know how to place the tiles in Column 1, and it is easy to slide the remaining tiles from Column 3.

That wasn’t so bad! Just a little knowledge of color theory and a bit of logic is all you need.

These puzzles are fun to create. However, there are a few issues to be aware of. The first arises since you want to avoid too many single dots — I used just one in the first puzzle, and I think that’s enough. It’s actually rather easy to create a grid with one of each color in each row and column — there are called Latin squares. The hard part is then creating an appropriate set of tiles. The difficulty lies with the fact that some squares are covered by just one tile, others by two.

In the following small grid, the numbers represent how many dots are needed to create a color in a certain location.

Suppose we wanted a vertical tile to cover a 1 and a 2 in column 3. Since (2,3) is covered by two tiles and vertical tiles cannot overlap, this means we must use a horizontal tile here. But then the only way to cover location (1,2) is with a horizontal tile and a vertical tile of height 1 (since the 1’s are already covered). But this is exactly what we want to avoid! Once I realized was happening, I first designed a grid with just 1’s and 2’s and a corresponding tile set, then added the colors later. In other words, I broke a harder design problem into two easier ones.

The other issue which arose was the question of uniqueness. It’s desirable to have a unique solution to puzzles like this — when you design a puzzle, you clearly have one solution, but can you be sure that there aren’t any others? This is not an insurmountable task, but for the larger puzzle below, it was more involved than I thought it would be.

So I leave you with a 6 x 6 puzzle to solve. Slide the tiles so that there is a red, green, blue, yellow, magenta, and cyan dot in each row and column. As mentioned above, the solution is unique. Feel free to post your own puzzles if you create them!

Cryptarithms

One of the goals of creating this blog was to show you some cool math stuff you might not have seen before. So I thought I’d create a puzzle about this:

Just replace each letter with a digit from 0–9 so that the sum is correct. No number begins with a 0. One more thing: M + T = A. Good luck!

Perhaps you’ve never seen puzzles like this before — they’re called cryptarithms. At first they look impossible to solve — almost any assignment of numbers to letters seems possible. But not really. You’re welcome to try on your own first — but feel free to read on for some helpful advice.

Look at the last column (the units). If L + H + G ends in H, then L + G must end in a 0. Since L and G are digits, then L + G = 10. This doesn’t completely determine L or G, but once you know one of the numbers, you know the other.

As a result, you also know there’s a carry over to the third column (tens). What does this mean? That 1 + O + T + O ends in C. Since O + O is an even number, this means that if T is even, then C is odd, and if T is odd, then C is even. We even know a bit more about T from looking at the sum: T is either 1 or 2, since adding three numbers less than 10,000 gives a sum less than 30,000.

What about the second column? O + A + L ends in A. We might be tempted to think that O + L must end in a 0, but that would mean that O + L is 10. This can’t be, since that would mean that G = O (remember that L + G = 10). Therefore there has to be a carry from the third column over to the second column, meaning O + L = 9. So O is one less than G.

Get the idea? There’s a lot of information you can figure out by looking at the structure of the letters in the sum. But it turns out that without the condition M + T = A, there are 12 solutions to this puzzle! Multiple solutions must occur here, for if you can solve this puzzle, you can also solve

The M and B occur just once, and at the beginning of numbers. This means if M = 7 and B = 9 in a solution, then putting M = 9 and B = 7 — with all other letters staying the same — will also produce a solution. In looking at all the solutions, I found that giving M + T = A results in a unique solution without giving values for specific letters.

That’s all the help you get! Sometimes you might just guess well and stumble onto a solution — but take the additional challenge and prove you’ve got the only solution to the cryptarithm.

How do you create a cryptarithm? There was a time I did so by hand — but those days are gone. Read more if you’d like to see how you can use programming to help you create these neat puzzles. (Of course there are online cryptarithm solvers, but that takes all the fun out of it!)

Continue reading Cryptarithms