Logic Puzzles II

Last week, we looked at solving some simple logic puzzles.  This week, the logic puzzle is quite a bit more involved —  I hope you enjoy it!

Six logical friends — Arlen, Boris, Cecil, Doran, Edith, and Frank — having just finished some pretty hairy logic problems, decided to go to Wacky Jack’s Primo Ice Cream Emporium to celebrate. Each ordered their ice cream in a waffle cone or a dish, except for the one who ordered the Slurp-A-Licious Bucket-O-Yum — a delectable concoction with two scoops each of Jack’s five Specialty Flavors — in which case it came in a commemorative Wacky Jack Bucket (which you got to keep if you ate it all). From the following clues, can you decide who ordered what?  Note: All solvers made their selections from Jack’s five Specialty Flavors: Blueberry Farkle, Chocolate Smudge, Marshmallow Whoop, Pecan Passion, and Peppermint Blast. For the cones, you must specify the order of the scoops.

1. No cone had more than three scoops of ice cream, and no dish had more than five.
2. Except for the problem solver who got the Slurp-A-Licious Bucket-O-Yum, no one got more than one scoop of the same flavor.
3. The number of scoops in Edith’s dish was the same as the sum of the numbers of scoops in Arlen’s and Cecil’s cones.
4. Cecil and Edith together had the same number of scoops as Arlen and Frank together.
5. If Frank had an even number of scoops, then there were 23 scoops among the six solvers.
6. If Frank had an odd number of scoops, then there were 25 scoops among the six solvers.
7. If Boris had an odd number of scoops, then Edith had an even number.
8. Boris had fewer scoops than Doran.
9. Exactly two solvers had exactly three scoops of ice cream.
10. Frank ordered a dish if and only if Boris ordered a cone.
11. Arlen had three scoops of ice cream if and only if no two cones had the same number of scoops.
12. Exactly four solvers had Marshmallow Whoop, exactly four had Pecan Passion, and exactly two had both.
13. Either Arlen’s flavors were a subset of Edith’s, or Frank’s were a subset of Cecil’s.
14. Frank did not order Pecan Passion, and Cecil did not order Marshmallow Whoop.
15. If Cecil ordered just one scoop, then Arlen ordered Pecan Passion.
16. Boris and Doran were the only two to order Peppermint Blast.
17. Arlen and Frank had no flavors in common if and only if Boris and Frank had exactly one flavor in common.
18. Two cones had a scoop of Chocolate Smudge second from the top.
19. Frank had exactly two scoops if and only if Pecan Passion was always the bottom scoop of the cone it was on.

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!

As I get ready for the new semester and update course syllabi, I am reminded of why I do things a bit differently.  I’ll let this speak for itself.

On Cheese

A new semester is about to start! Finally, those students we have worked so hard to prepare are ready to learn The Calculus!  (Note: We do not teach The Calculus, but rather facilitate its learning.)

With class Roster in hand, we make for the Cheesemonger. (Mr. Hadley has been here for decades.) “Mr. Hadley, twenty-one, if you please,” I say, handing him my Roster. That is all there is to it. The next morning, twenty-one perfectly crafted cubes of Preferred Cheese (each having a mass of precisely 100g) are in my class Cupboard — one for each student, clearly labelled. We are ready!

Of course the students’ initial enthusiasm is high, until the inevitable First Exam. Surely much of the material is review — so we use the Petite grater to shave off a small bit of cheese from a student’s Block when they make the inevitable First Mistake. (There is always the exception, naturally — the Micro is used for sign errors, as well as trivial arithmetic errors.) This is done to accurately track students’ progress.

As the semester progresses, the situation becomes more dire. More egregious errors require the use of a Usual grater, while blocks of students who neglect to turn in entire assignments surely warrant being shaved by an Ultra. After years of experience, we are able to gauge precisely how much cheese must be shaved for each particular type of error. (Truly, it is all in the wrist.)

The end draws near — and although well-acquainted with the system, students still worry about the mass of their Block. They must realize that what is done is done — and No!, it is not possible to replenish the cheese! Is there no justice? They have been warned aplenty, but it is not our fault they do not heed our omens.

We are particularly meticulous with the shaving of the Final Exam — as it is an important assessment. Certain errors now warrant more grievous penalties — the Micro is no longer relevant. Beware the sign error!

But the wonders of being Complete! As a result of our experience (and training, naturally — Mr. Hadley is quite the Cheesemonger), the mass of each student’s Block represents their understanding of The Calculus entirely! Moreover, this mass may be converted to any number of convenient units — a percentage, perhaps, or one of various letters meant to convey a State of Understanding. But the work of the Facilitator is done! We rest well, and enjoy our cuppa. (Yes, some decry the fairness of such a system. No matter. Surely it is the best possible.)

Envelopes III: Art and Randomness

This week, I’ll discuss some of the artistic decisions made in producing the images in last week’s post, as well as explore randomly-generated envelopes.

First, let’s look at the following piece.

Initially, I created the image below, which is essentially a recreation of a hand-drawn sketch made in 1983.

Although the lines are clean and precise, the overall impression lacks a hand-drawn feel. I thought to create more texture by having the alternating envelopes go around the origin more than once, as seen here.

I liked this better, but I thought to adjust the angular sizes of the envelopes so that the tips were evenly spaced around a circle. I also adjusted the number of lines in each envelope, producing the final result.

The point of this discussion is to illustrate the process of creating digital art – it’s not as simple as just writing a few lines of code and executing them. There is an iterative give-and-take to the process, which is half the fun of it, anyway.

The next image I’d like to look at is the spiral, shown below.

This is a recreation of an image originally drawn in red, and I thought to create texture by introducing a color gradient. However, using a linear color gradient from the first line to the last produced the following result.

This looked a little off to me – moving toward the green a bit too fast. Now if you remember the discussion of color gradients when we looked at the Evaporation piece (see Day012), you’ll recall that we could create nonlinear gradients which created different visual effects. I found that changing the gradient from linear (a power of 1) to a power of 0.8 produced something I liked more. Of course the difference is not drastic, but I want to illustrate the fact fine-tuning parameters can introduce subtle effects in the final image.

Now on to a discussion of randomly-generated envelopes. Today will only be an introduction – there’s lots more to explore, including envelopes in three dimensions.  But I’ve only begun working on this idea a few weeks ago, and so hope to illustrate how previous work with randomness may be incorporated into the design of envelopes.

Of course just what is random is a more subtle question here. Below is an image where the successive endpoints used to create the envelope are randomly chosen from a unit square, and a color gradient is produced from the beginning to the end to give a sense of motion.

You’ll immediately notice that some envelopes span the entire width or height of the image. As it happens, this makes finding nicely-balanced images difficult. I looked at a few hundred images before I found the one above – most lacked balance.

I also wanted to try bright colors against black – this produces nice results for an online blog (though not so wonderful for a printed image). Again, I didn’t like the results obtained by allowing the points determining the envelopes to be completely random. So I introduced a constraint that the endpoint of the next segment had to be “close” to the previous one – in the image below, the endpoints could be no further than one unit in either the x- or y-direction from the previous point. So there are more local effects, and none of the broader lines slicing the image in half.

The image looked a little too square, and I thought the contrast too much for so many envelopes.  So I looked at a few hundred more images on a wider field, this time in yellow. I found one with some interesting interactions, shown below.

Now I felt I was getting somewhere. But I thought the image looked a bit too flat – I wanted to add some texture or dimensionality to the image.

The first thing I tried was slightly varying the yellows used to draw the lines. This helped to add a measure of interest to the envelope. But the background needed some work.

I wanted the background to contrast the flowing curves of the envelopes, and so I thought some overlapping squares of varying dark shades of gray might do the trick. Here is the result.

The background took a few hundred iterations as well. Now I didn’t want the squares too small, and I didn’t want too many – the sizes of the squares should compare to the sizes of the individual envelopes, and there should be roughly as many. But the problem was that randomly-generated sets of squares would often leave too many gaps in the background – and simply overlaying a background of a single shade of gray wasn’t particularly pleasing.

So I had to play with the parameters generating the overlapping squares, as well as try a few hundred iterations until I found something with a nice balance. In addition, I wanted the background to be “interesting” in the largish hole just left of center – some iterations just produced a solid gray there, which didn’t work for me.

It took a bit of time – as well as feedback from my friend Sandy (thanks, Sandy!) to whom I showed successive drafts of this image – but I finally found a combination of colors/backgrounds which I felt held together. Of course you might think otherwise – and you are welcome to give it a try and create your own image with randomly-generated envelopes….

I hope this helps to illustrate the creative process – one of the main themes of this blog. While a final image may look complex with various different aspects interacting with each other, it’s not always the case that each aspect was conceived of at the same time. This is the great thing about computer-generated art – it’s so easy to explore a multitude of ideas without leaving the comfort of your keyboard.

But this is also perhaps the greatest challenge – because you can do so much, finding the right balance between simplicity and complexity in part distinguishes computer-generated images from computer-generated art.

Finally, I cannot resist including an image I tweeted a few days ago @cre8math — a variation on the spiral theme.  I find it unusually compelling.

Envelopes II: Making Spirals

While I don’t intend to make a habit of midweek posts (though thanks for the idea, Dane!), last week’s entry was so popular that I thought I’d write a short post on how the spiral designs are created.  Here’s one of last week’s images to refresh your memory.

These are not difficult to create,  but because of all the overlap of lines, it’s not immediately obvious how they are generated.  The image below shows the first forty line segments drawn, and highlights the endpoints of these segments.

The first line drawn is horizontal, and the endpoints are 180 degrees apart.   More lines are generated by having the orange endpoint (starting at the right) move 4 degrees counterclockwise, while the green endpoints (starting at the left) move just 3 degrees.  As a result, the endpoints of the second segment are just 179 degrees apart on the circle.  The orange endpoints start gaining on the green endpoints, closing the gap by 1 degree with each successive segment.

So the final spiral includes exactly 180 segments, which may be expressed in a form which may be easily generalized (and which is used in the Python code).  Note that the “180” on the left side of the equation represents the number of segments drawn, and the “180” on the right indicates the angular distance that the endpoints of the initial segment are separated on the circle.

$180 = \dfrac{180}{4-3}.$

All 180 segments are shown below, where the endpoints are retained to illustrate the process (although note that many endpoints are written over as the algorithm progresses).

The Python code is fairly short (here is the Sage link — look at some of the earlier posts about using Sage if you haven’t used it before). The only mathematics you need to understand is the standard conversion from polar to rectangular coordinates — it’s much easier to describe the endpoints first in polar coordinates since the radius of the circle is fixed and only the angles the endpoints make with the center of the circle change.

Finally, I include an image created with contrasting colors on the background as well.  Create your own version, and post as a comment!

Envelopes I

Most of us have probably created a mathematical envelope, although we likely didn’t call it that.  Below is an example which may easily be sketched on a piece of graph paper.  You can see the “move one up/down, move one left/right” method of determining the ends of the line segments.  I created this envelope of lines using Python — we’ll look at the code later so you can make some of your own.

I first began sketching envelopes when I was an undergraduate.  Of course they were aesthetically quite interesting — but as a mathematician, you cannot help but ask exactly what curve you’re approximating by drawing an envelope of lines.

Although it seems that you might be drawing tangents to a circular arc, this is not the case.  By continuing the pattern of moving one up/down and left/right, the envelope in the first quadrant develops into the following figure.

You can fairly easily see a parabola forming — and this parabola is in fact the curve whose tangents we drew on our graph paper.

How can we prove this?  We need a theorem about tangents to parabolas, which we state as it applies to the case at hand, as shown below.

Here is how the theorem goes.  Suppose P and Q are points on a parabola whose tangents intersect at R.  If X is a point on the parabola between P and Q, and if the tangent at X intersects PR at M and QR at N, then

[PM] / [MR] = [MX] / [XN] = [RN] / [NQ],

where we use “[AB]” to mean the length of the segment AB.  But in our case, [PR] = [QR], so this means that

[PM] = [RN]  and  [MR] = [NQ],

which validates our “one down, one right” method of creating endpoints of tangent segments.  This is because by moving down one and right one, we are preserving the relationship [PM] = [RN], and hence also [MR] = [NQ].

For the curious reader, this helpful theorem about tangents to parabolas is very nicely proved by Steven Taschuk in his Notes on tangents to parabolas on p. 5 (where the names of points in my diagram above correspond to the names of points in his proof of the theorem).

So they’re parabolas!  Not what you’d expect at first glance.

Of course back when I was beginning college, there was no easy way to create desktop graphics, and so I used the tried and true pen-and-paper method.  I took a photo of one of my favorites from that time period.

Drawing these figure takes patience and concentration.  I distinctly recall the first draft of this piece.  If you look at the left square, you’ll notice that the blue lines look like they’re underneath the red lines.  This isn’t hard to do — just draw the red lines first, and then when drawing the blue lines, just stop at the red and continue after.  But I lost focus for just a second, and drew a blue line right over the red lines — and then had to start over.  There was no erasing.

For those of you who want to try creating images by hand, a word about technique.  When using an ink pen, the ink tends to blot — and if you drag the pen along a ruler, you might get end up with a smear of ink.  So keep a napkin or paper towel handy, and wipe the tip of your pen on the paper towel after drawing each line.  It’ll save you a lot of grief.

Despite the relatively simple method of drawing envelopes of lines, there is ample room for creativity.  Here is a computer-generated version of a drawing dated December 24, 1986.  It’s another of my favorites, and I love the effect of bright color against black.

There’s no reason to stop at purely geometrical designs, either.  Here is an abstract half-face of a tiger, created with a simulated graph paper background.

And then there’s polar graph paper!  When you wanted a graph, well, you just drew it — there was no graphing calculator/computer to do it for you.  So you had graph paper handy.  Below is a design I created just for this post, based on some older sketches.

Here’s another image based on a sketch made on polar graph paper.

It’s been really interesting to experiment with the computer, since designs which might have taken hours to draw can be rendered in a few seconds (after you’ve done the programming, of course).

Envelopes are not restricted to being created by lines, however.  The figure below creates a cardioid from tangent circles.

A base circle (in red) is given, and a point on the circle is selected (the white point at the left).  Now for every other point on the circle (like the red point), create a circle by using that point and the white point as ends of a diameter of the circle (drawn in black).  These circles are internally tangent to a cardioid.

I don’t have room for the proof of this construction here, but there is a very nice book called Envelopes by Boltyanskii (just google it) which illustrates many additional examples of envelopes as well as techniques to determine what the resulting curve is.  Some of the techniques do involve calculus, so be forewarned!  This book was my real introduction to a study of mathematical envelopes.

Now it’s time for you to create your own envelopes!  You can click on the Sage link to follow along and alter the code as you see fit.

The routines aren’t really too complex.  Note the use of vectors in Python to make working with the mathematics fairly simple.  This is so we can compute the endpoints of the segments of the envelope easily.  The mathematics involved is illustrated in the following figure.

It looks more complicated than it is.  Since $P_i$ is between $P$ and $R,$ we may write $P_i$ as a weighted average of $P$ and $R.$  We must do so in such a way that $i=0$ gives the point $P=P_0,$ and $P_{n-1}$ is just above $R.$

Similarly, $Q_i$ is a weighted average of $R$ and $Q,$ and must be such that $Q_0$ is just to the right of $R,$ and $Q_{n-1}=Q.$  Take a moment to study the figure and see that it all works out.  Note that the variables in the code mimic those in the figure exactly, so at least there is visual proof that the labels are correct!

So I’ll leave you to go ahead and experiment.  Feel free to comment with images you create using the Python code.  And stay tuned for next week, when I’ll talk about creating random envelopes.  There’s some really interesting stuff going on there….