The Puzzle Archives, I

In going through some folders in my office the other day, I came across some sets of mathematics puzzles I wrote for a conference of the International Group for Mathematical Creativity and Giftedness in 2014.  Teachers of mathematics of all levels attended, from elementary school to university.  The organizing committee (which included me) thought it might be fun to have some mathematical activity that conference attendees could participate in.

So I and my colleagues created three levels of contests — Beginning, Intermediate, and Advanced — since it seemed that it would be difficult to create a single contest that everyone could enjoy.  But I did include three problems that were the same at every level, so all participants could talk about some aspect of the contests with each other.

Participants had a few days to get as many answers as they could, and we even had books for prizes!  Many remarked how much they enjoyed working out these puzzles.

Now this conference took place before I started writing my blog.   I have written several similar contests over the years for various audiences, and so I thought it would be nice to share some of my favorite puzzles from the contests with you.  And so The Puzzle Archives are born!

First, I’ll share the three puzzles common to all three contests.  I needed to create some puzzles which were fun, and didn’t require any specialized mathematical knowledge.  As I’m a fan of cryptarithms and the conference took place in Denver, I created the following puzzle.  Here, no letter stands for the digit “0.”

Day133Puzzle1

For the next puzzle, all you need to do is complete the magic square using the even numbers from 2 to 32.  Each row, column, and diagonal should add up to the same number.  There are two solutions to this puzzle — and so you need to find them both!

Day133Puzzle2

And of course, I had to include one of my favorite types of puzzles, a CrossNumber puzzle.  Remember, no entry in a CrossNumber puzzle can begin with “0.”

Day133Puzzle3

I also included a few geometry problems, staples of any math contest.  For the first one, you need to find the area of the smallest circle you could fit the following figure into.  Both triangles are equilateral; the smaller has side length 1 and the larger has side length 2.

Day133Puzzle4

And for the second one, you need to find the radius of the larger circle.  You are given that the smaller circle has a diameter of 2 units, and the sides of the square are 2 units long.  Moreover, the smaller circle is tangent to the square at the midpoint of its top edge, and is also tangent to the larger circle.

Day133Puzzle6

The last two problems I’ll share from this contest are number puzzles.  The first is a word problem, which I’ll include verbatim from the contest itself.

Tom and Jerry each have a bag of marbles. Tom says, “Hey, Jerry. I have four different colors of marbles in my bag. And the number of each is a different perfect square!” Jerry says, “Wow, Tom! I have four different colors of marbles, too, but the number of each of mine is a different perfect cube!”

If Tom and Jerry have the same total number of marbles, what is the least number of marbles they can have?

And finally, another cryptarithm, but with a twist.  In the following multiplication problem, F, I, N, and D represent different digits, and the x‘s can represent any digit.  Your job is to find the number F I N D. (And yes, you have enough information to solve the puzzle!)

Day133Puzzle5

Happy solving!  You can read more to see the solutions; I didn’t want to just put them at the bottom in case you accidentally saw any answers.  I hope you enjoy this new thread!

(Note:  The FIND puzzle was from a collection of problems shared by a colleague.  The first geometry problem may have come from elsewhere, but after four years, I can’t quite remember….)
Continue reading The Puzzle Archives, I

More CrossNumber Puzzles

Last fall, I mentioned that while looking at the Puzzle Page of the FOCUS magazine published by the Mathematical Association of America, I thought to myself, “Hey, I write lots of puzzles.  Maybe some of mine can get published!”  So I submitted a few Number Search puzzles to the editor, and to my delight, she included them in the December/January issue.  Here’s the proof….

Day132Focus

Incidentally, these puzzles are the same ones I wrote about almost two years ago — hard to believe I’ve been blogging that long!  So if you want to try them, you can look at Number Searches I and Number Searches II.

Since I had success with one round of puzzles, I thought I’d try again.  This time, I wanted to try a few CrossNumber puzzles (which I wrote about on my third blog post).  But as my audience was professional mathematicians and mathematics teachers, I wanted to try to come up with something a little more interesting than the puzzles in that post.

To my delight again, my new trio of puzzles was also accepted for publication!  So I thought I’d share them with you.  (And for those wondering, the editor does know I’m also blogging about these puzzles; very few of my followers are members of the MAA….)

Here is the first puzzle.

Day132Puzzle1

Answers are entered in the usual way, with the first digit of the number in the corresponding square, then going across or down as indicated.  In the completed puzzle, every square must be filled.

I thought this was an interesting twist, since every answer is a different power of an integer.  I included this as the “warmup” puzzle.  It is not terribly difficult if you have some software (like Mathematica) where you can just print out all the different powers and see which ones fit.  There are very few options, for example, for 3 Down.

The next puzzle is rather more challenging!

Day132Puzzle2

All the answers in this puzzle are perfect cubes with either three or four digits, and there are no empty squares in the completed puzzle.  But you might be wondering — where are the Across and Down clues?  Well, there aren’t any….

In this puzzle, the number of the clue tells you where the first digit of the number goes — or maybe the last digit.  And there’s more — the number can be written either horizontally or vertically — that’s for you to decide!  So, for example, if the answer to Clue 5 were “216,” there would be six different ways you could put it in the grid:  the “2” can go in the square labelled 5, and the number can be written up, down, or to the left.  Or the “6” can go in the square labelled 5, again with the same three options.

This makes for a more challenging puzzle.  If you want to try it, here is some help.  Let me give you a list of all the three- and four-digit cubes, along with their digit sum in parentheses:  125(8), 216(9), 343(10), 512(8), 729(18), 1000(1), 1331(8), 1728(18), 2197(19), 2744(17), 3375(18), 4096(19), 4913(17), 5832(18), 6859(28), 8000(8), 9261(18).  And in case you’re wondering, a number which is a palindrome reads the same forwards and backwards, like 343 or 1331.

The third puzzle is a bit open-ended.

Day132Puzzle3

To solve it, you have to fill each square with a digit so that you can circle (word search style) as many two- and three-digit perfect squares as possible. In the example above, you would count both 144 and 441, but you would only count 49 once. You could also count the 25 as well as the 625.

I don’t actually know the solution to this puzzle.  The best I could do was fill in the grid so I could circle 24 out of the 28 eligible perfect squares between 16 and 961.  In my submission to MAA FOCUS, I ask if any solver can do better.  Can you fit more than 24 perfect squares in the five-by-five grid?  I’d like to know!

I’m very excited about my puzzles appearing in a magazine for mathematicians.  I’m hoping to become a regular contributor to the Puzzle Page.  It is fortunate that the editor likes the style of my puzzles — when the magazine gets a new editor, things may change.  But until then, I’ll need to sharpen my wits to keep coming up with new puzzles!

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!

CrossNumber Puzzles

This week, we’ll look at one of my favorite types of puzzles — CrossNumber Puzzles. These are like crossword puzzles, except that the clues describe numbers instead of words. The only rule is that no entry in a CrossNumber Puzzle can start with a “0.” You can try this one — but don’t worry if you get stuck. We’ll look at different ways you can go about solving it in just a moment.

Day003Puzzle1

How would you go about solving this puzzle? Try to look for the clues which give you the most information. For example, look at 1 Across and 3 Down. Now 1 Across is the cube of a two digit number, and its third digit is actually the first digit of the cube root. So we might want to print out a chart of all four-digit cubes of two-digit numbers:

10 1000 16 4096
11 1331 17 4913
12 1728 18 5832
13 2197 19 6859
14 2744 20 8000
15 3375 21 9261

You can see that the only possibility is that 1 Across is 4913 and 3 Down is 17.

Looking at 5 Across doesn’t help much, since there are too many possibilities.

But looking at 5 Down is a good next choice. Note that 9 Across has to start with 1 or 3 in order to fit four odd digits in the grid, but no perfect squares end in 3, and so no perfect fourth powers end in 3, either.  This means that 9 Across has to start with 1 so that 5 Down ends in 1.  To help figure out 5 Down, below is a list of four-digit fourth powers:

6 1296 8 4096
7 2401 9 6561

So 5 Down must be either 2401 or 6561. If it were 2401, then 6 Across would begin with a “0,” so that leaves 6561 as the only option for 5 Down.

I’ll leave it to you to complete the puzzle. I won’t post a solution so that you’re not tempted to peek — but if you add 2 Down and 6 Across when you’re done, you’ll get 157,991.

How can you make your own CrossNumber puzzle? Start by making a grid, and shade in some of the squares. Usually the pattern of shaded squares is symmetric, but it doesn’t have to be. Fill in some of the entries with numbers which have specific properties, like being a perfect square or cube. Or perhaps make one of the entries the product or sum of two others. The only limit is your imagination! It might help to continue reading below, since then you could print different charts and look at the numbers for something interesting. (And get another puzzle to solve, too.)

Continue reading CrossNumber Puzzles