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.

OneFour100.png

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 412 = 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….432 = 52619.  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 100G in the grid is the same as being off by 526L in the list is to say that

G2 = 5 L2 + 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

L2 – 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 24 . 7
373 prime
3181 prime
8533 7 . 23 . 53
11,665 5 . 2333
14,420 22 . 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 344 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:

  1. Dillon is wearing a yellow hat if and only if Elbyn is wearing a green one.
  2. Either Dillon is wearing a red hat, or Fenn is wearing a yellow hat.
  3. If Dillon is wearing  a red hat, then Cedric is wearing a blue one.
  4. Cedric’s hat is either red or yellow.
  5. 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?

  1. If Fenn bought a green hat, then Dillon bought a yellow hat.
  2. 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.
  3. If Cedric’s new hat was blue, then Elbyn’s new hat was green.
  4. Either Dillon or Fenn bought a new blue hat.
  5. If Dillon did not buy a hew red hat, then Elbyn did.
  6. 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?

  1. If I don’t have more choobles than bananas, then I have two more apples than bananas.
  2. If I have more choobles than bananas, I have three apples.
  3. If I have fewer than four apples, then I have the same number of bananas as choobles.
  4. 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, the first “X” is the multiplication symbol, and the second “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 lengthsDay014formulaand 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?Day014Puzzle1AThis seems like an easy puzzle to solve, as shown below.Day014Puzzle1BSo 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:Day014Puzzle1CThis 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.Day014Puzzle2It 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.)Day014Puzzle4I’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.

Day010CS1

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

Day010CS2

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.

Day010CS3

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).

Day010CS4

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.

Day010CS5

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.

Day010CS6

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.

Day010CS7

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.

Day010CS8

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!

Day010CS9