Month: December 2017

Beguiling Games IV: Scruffle.

We’ll start this installment of Beguiling Games by discussing who has a winning strategy in Splotch!  Recall the rules of the game:  players alternately color in squares in a 4 x 4 grid, with the goal of creating a specified splotch, shown below.  The splotch may be rotated and/or reflected as well.

Day119Splotch1

For a more complete description together with an example of how the game is played, you can look at the previous installment of Beguiling Games.

OK, now for the solution!  It turns out that the second player can always win.  Let’s see how.  I found it easiest to think about a strategy by imagining the grid as being divided into quadrants, like this:

Day124Splotch1

Now here is the important observation:  the first player who fills in a second square in any of the quadrants loses, regardless of whether the squares are adjacent or diagonally situated.  Of course there are other ways to lose, too — as with all these two-player games, there are multiple ways to analyze them.

So let’s get specific.  Suppose the first player colors in square A1 (see the figure below).  The second player then colors in the square labelled B1.

Day124Splotch2

At this point, the red squares indicate all the places the first player cannot play without losing the next turn.  So the first player must color in one of the two empty squares, after which the second player will color in the other one.  So after two turns for each player, the board now looks like this:
Day124Splotch3.png

So no matter what square the first player colors in next, one of the quadrants will contain two filled-in squares, and so the second player will win on the next move.

A similar strategy may be used no matter where the first player begins.  Consider the first few moves in the following game.  The first player colors in the square A1, and the second player colors in B1.

Day124Splotch4

Again, the first player must avoid the red squares, or else the second player would win on the next turn.  Whichever square the first player colors in next, the second player can always play “two away.”  The result will be 1) the first player will not be able to win on the next turn, and 2) one square in every quadrant will be colored in.  This means that the first player is forced to put a second square in one of the quadrants on the next move, meaning that the second player will win on the turn after that.

This is the simplest strategy I found for the second player.  I would be happy to hear if some reader found an even simpler way to describe a winning strategy!

What about using other splotches?  If the splotch contains too many squares, it is possible to force a draw.  For example, given the splotch below, either player may force a draw simply by coloring in the four corners on their first four moves.

Day125Splotch5.png

Interestingly, it is difficult to come up with a splotch where the first player has a winning strategy (other than a splotch which is just a single square, of course).  The more squares included in the splotch, the more difficult the analysis.  But for simpler splotches, it seems a clever division of the board allows the second player to win.

For example, consider the following square splotch.

Day125Splotch6

Now divide the board into the following 2 x 1 regions, or dominoes:

Day125Splotch7

Player two has a simple winning strategy.  Whenever the first player fills in a square, the second player fills in the other square of the domino.  It should be clear that the second player can never lose this way.  The first player will eventually have to fill in a square directly above or below a filled-in domino, and when this happens, the second player wins on the next move.

A complete analysis of Splotch! is likely beyond reach.  Just counting the number of possible splotches (up to rotation and reflection) would be a challenging task unless you wrote a computer program to exhaustively find them.  Without rotations and reflections, there are 216 = 65,536 possible subsets of 16 squares, and hence 65,535 splotches (since a splotch must include at least one square).  So a computer program would be able to find them all relatively quickly.  The interested reader is welcome to undertake such a task….

Here is another simple two-player game for you to think about, which I call Scruffle.  It is played on a typical 3 x 3 Tic-Tac-Toe grid.  Players alternate playing either a 1, 2, or 3 anywhere in the grid.  A player wins when a number they place creates a column, row, or diagonal which contains a 1, 2, and 3 in any order.

There is one additional constraint:  only three of each number may be placed in the grid.  So once three 1’s (for example) are placed in the grid, no player may place another 1 anywhere in the grid.  This is not an arbitrary constraint — you can show that the game cannot end in a draw with this condition.  See if you can show this!

For the first puzzle, show that the first player has a winning strategy.  This is not difficult; the simplest strategy I found involves the first player’s second turn involving playing the same number they played on the first turn.

A slightly more challenging puzzle is to require the first player to play a different number than the number they played on their first move.  Does the first player still have a winning strategy?  I’ll give you the solution in the next installment of Beguiling Games!

Bay Area Mathematical Artists, IV.

We had our last meeting of the Bay Area Mathematical Artists in 2017 this weekend!  We had a somewhat lower turnout than usual since we’re moving into the holiday season.  But it really wasn’t possible to move the seminar a week earlier, since many of us affiliated with universities were in the middle of Final Exams.

As we had been doing before, we began with a social half hour while waiting for everyone to show up.  We then moved on to the more formal part of the afternoon.

There were three speakers originally slated to give presentations, but one had to cancel due to illness.  Still, we had two very interesting talks.

The first talk, Squircular Calculations, was given by Chamberlain Fong.  Chamberlain did speak at the inaugural September meeting, but wanted a chance to practice a new talk he will be giving at the Joint Mathematics Meetings in San Diego this upcoming January.

jmmscreen

So what is a squircle?  Let’s start with a well-known family of curves parameterized by p > 0:

|x|^p+|y|^p=1.

When p = 2, this gives the usual equation for a circle of radius 1 centered at the origin.  As p increases, this curve more and more closely approaches a square, and it is often said that “p = ∞” is in fact a square.

However, in Chamberlain’s opinion, the algebra becomes a bit unwieldy with this way of moving from a circle to a square.  He prefers the following parameterization:

x^2+y^2-s^2x^2y^2=1,

where s = 0 gives a circle, and the central portion of the curve when s = 1 is a square.  As s varies continuously from 0 to 1, the central portion of this curve continuously transforms from a circle to a square.  This parameterization was created by Manuel Fernandez Guasti; you can read his original paper here.

Chamberlain’s talk was about extending this idea in various ways into three dimensions.  He showed images of squircular cylinders, squircular cones, etc., and also gave equations in three-dimensional Cartesian coordinates for all these surfaces.  You can see some of the images in the title page of his presentation above.  It was quite fascinating, and there were lots of questions for Chamberlain when his talk was finished.  Feel free to email him at chamb3rlain@yahoo.com if you have further questions about squircles.

The second talk was given by Dan Bach (also a speaker at our inaugural meeting), entitled Making Curfaces with Mathematica.  Yes, “curfaces,” not “surfaces”!

Day124DanBach

Dan took us through a tour of his very extensive library of Mathematica-generated images.  He is fond of describing curves using parameters, and then changing the parameters over and over again to generate new images.

This is easy to do in Mathematica using the “Manipulate” command; below is a screen shot from Mathematica’s online documentation showing an example.

Day124Mma

The parameter n is used in plotting a simple sine function — as you move the slider, the graph changes dynamically.  Note that any numerical parameter may be experimented with in this way.  Simply make a slider and watch how your image changes with the varying parameter.

So what are “curfaces”?  Dan uses the term for images create by a family of closely related curves which, when graphed together, suggest a surface.  As we see in the example above, the family of curves suggests a spiraling ribbon in which several brightly colored balls are nestled.  Dan showed several more examples of this and discussed the process he used to create them.  To see more examples, you can visit his website www.dansmath.com or email him at art@dansmath.com.

Once the talks were over, we had some time for puzzles!  Earlier in the week, when I knew we were not going to have an overabundance of talks, I asked participants to bring some of their favorite puzzles so we could all have some fun after the talks.  We were all intrigued with the wide variety of puzzles participants brought.

My dissection puzzle was actually quite popular — that is, until a few of the participants solved it!

Day124Dissection

You might recognize this from my recent blog post on geometrical dissections.  The pieces above are arranged to make a square, but they may also be rearranged to make an irregular dodecagon.  Some asked if I had any more copies of this puzzle, but unfortunately, I didn’t.  Maybe I’ll have to start making some….

As has been our tradition, many of us went out to dinner afterwards.  We went to our favorite nearby Indian buffet, and engaged in animated conversation.  Interestingly, after talking a bit about mathematics and art, Chamberlain began entertaining us with his wide repertoire of word puzzles.

To give just one example, he asked us to come up with what he calls “mismisnomers.”  Usually, the prefix “mis-” means to incorrectly take an action, as in “misspell.”  But some words, like “misnomer,” begin with “mis-,” while the remainder of the word, “nomer” is not even a word!  How many mismisnomers can you think of?  This and similar amusing puzzles kept us going for quite a while, until it was finally time to head home for the evening.

So that’s all for the Bay Area Mathematical Artists in 2017.  Stay tuned in 2018…our first meeting next year will be at the end of January, and I’ll be sure to let you know how it goes!

Mathematics and Digital Art: Final Update (Fall 2017)

Yes, it is the end of another semester of Mathematics and Digital Art!  It was a very different semester than the first two, as I have mentioned in previous posts, since I began the semester with Processing right away.  There are still a few wrinkles to iron out — for example, we had a lab project on interactivity (involving using key presses to change features of the movie as it is running) which was quite a bit more challenging than I expected it would be.  But on the whole, I think it was an improvement.

So in this final post for Fall 2017, I’d like to share some examples of student work.  In particular, I’ll look at some examples from the Fractal Movie Project, as well as examples of Final Projects.

Recall that the Fractal Movie Project involves using linear interpolation on the parameters in affine transformations in order to make an animated series of fractal images.  One student experimented with a bright color palette against a black background.  As the fractal morphed, it actually looked like the red part of the image rotated in three dimensions, even though the affine transformations were only two-dimensional.

MAK

 

Cissy wanted to explore the motion of rain in her movie.  Although she began with bright colors on a black background, once she saw her fractal in motion, she decided that more subtle colors on a white background would be better suited to suggest falling raindrops being blown about by the wind.MCissy

 

Sepid also incorporated movement in her movie — she created a rotating galaxy with a color palette inspired by the colors of the Aurora Borealis.  In addition, she learned how to use the Minim library so she could incorporate sound into her movie as well.  Here is a screen shot from her movie.

MSepid

 

Now let’s take a look at a few Final Projects.  Recall that these projects were very open-ended so that students could go in a direction of their choice.  Some really got into their work, with truly inspirational results.  The presentation that Sepid gave at a recent meeting of the Bay Area Mathematical Artists was actually work she was doing on her Final Project (read about it here).

Terry took on an ambitious project. She based her work on a Bridges paper by Adam Colestock, Let the Numbers Do the Walking: Generating Turtle Dances on the Plane from Integer Sequences (read the paper here).  Terry did have some programming experience coming into the course, and so she decided to code all of Adam’s turtle graphics algorithms from scratch! This was no simple task, but she worked hard and eventually accomplished her goal.

Here is a screen shot from one of her movies; Terry wanted to create an interesting visual effect by overlaying multiple copies of the same turtle path.  Since this particular path was not too dense in the plane, she was able to work with thicker lines.

FPTerry

Tera created a movie which involved rotating triangles and moving dots.  Her movie had a strong sense of motion, and incorporated a vibrant color palette. She remarked that working with color in this project was both fun and quite challenging. In her words, “Playing nicely with hot pink is not an easy feat.”

FP_TG

 

I would also like to share the fact that Professor Roza Aceska of Ball State University (Muncie, Indiana) will be teaching a course about digital art next semester using Processing which will be incorporating a lot of my course materials.  I am very excited about this!  Many faculty who come to my talks say they are interested in teaching such a course, but getting Department Chairs and Deans to approve such courses is sometimes an uphill battle.

Professor Aceska’s course will be a bit different from mine — her course is in the Honors Program, and as such, does not count as a mathematics credit.  So she will not have most of the mathematics assignments and quizzes that I had in my course.  But she will still be emphasizing the fascinating relationship between mathematics, programming, and art.  I hope to write more about her course sometime during the next semester.

One final remark — I am helping to organize a Mathematical Art Exhibition at the Golden Section Meeting of the Mathematical Association of America on February 24, 2018 at the California State University, East Bay.  So if you’re reading this and are in the Bay Area and would like to submit some mathematical art for inclusion in our exhibit, please let me know!

 

Knights and Rogues

 

They were dark times in the Kingdom of Verdoon.  A band of fierce Rogues was terrorizing the local hamlets.  King Buford was very displeased — he had no other option but to send out a legion of Brave Knights and Loyal Knights to round up the Rogues and deliver them to the castle dungeons.

So he chose seven of his bravest Brave Knights, and seven of his most loyal Loyal Knights, and dispatched them across Mount Kerchoo to the hamlet of Dunken, where the Rogues were last reported to have been wreaking havoc.

The Knights were capable Knights, and soon rounded up seven of the fiercest Rogues, including their leader, Thorn Yackley.  Now they had the difficult task of escorting the Rogues back through the narrow, winding path over Mount Kerchoo.

The Rogues were so fierce, no single sword could subdue any of them, nor could a single mace.  But they were no match for both a sword and a mace.

Now the Brave Knights carried a single sword, and the Loyal Knights a single mace.  So on the trek back to the castle — where they had to walk single file, the path was so narrow — it was vital that each Rogue be flanked by both a Brave Knight and a Loyal Knight in the event the Rogue tried to escape.

The question:  In how many ways could the Brave Knights, Loyal Knights, and the Rogues be lined up so that on the treacherous way back, each Rogue was flanked by both a Brave Knight and a Loyal Knight?

(For this problem, consider the Brave Knights indistinguishable from each other; similarly for the Loyal Knights and Rogues.)

Recently, I had been challenged to create a lesson which involved problem-solving with binomial coefficients.  But I didn’t want to create just any lesson — I wanted something interesting and novel.

Now if you’ve ever taught combinatorics and counting, you know that there is a deluge of problems about binomial coefficients — from choosing committee members, sitting people around a circular table, lining up books on shelves, etc.  So it’s not an easy task to come up with something you think might be new.

That was the genesis of Knights and Rogues.  Of course it may very likely not be new, since it really is difficult to come up with a combinatorics problem no one has thought about before.  But I did ask a colleague who knows a lot about problem solving, and he hadn’t seen it before.

The story is just to get students interested.  Combinatorially, we could state the problem as follows:

Given p 0’s, q 1’s, and r 2’s, in how many ways can you line them up so that each 2 is surrounded by both a 0 and a 1?

It turns out that there is a lot going on in this problem.  With three parameters, the analysis is far from straightforward.

There are a few restrictions on the parameters.  For example, we need p+q>r, or there are not enough Knights to flank the Rogues.  We also need

p,q\ge\left\lceil\dfrac r2\right\rceil,

or else there wouldn’t be enough Brave Knights and Loyal Knights to flank the Rogues.  For example,  if p = 2, q = 1, and r = 3 (so that q just falls short of the above inequality), you can see the problem — the one 1 can flank at most two 2’s, and so there is one 2 without an adjacent 1.  But if increase q to 2, we can have either the sequence 0212021 or 1202120.

Of course it is possible to consider specific examples, but it is also possible to consider infinite families of parameters — we’ll look at the case p = 2, q = n, and r = 2 to give you an idea of the reasoning involved.

Now when n = 1, there is only one possibility:  02120.    But when n is larger than 1, we need to look at two separate cases:  when the 2’s are separated by more than one 0/1, so that we are looking at two blocks of 021 or 120.  When the 2’s are separated by exactly one 0/1, we only have the options 02120 or 12021.  We need to count each case separately.

Let’s look at the first case.  We have two blocks of either 021 or 120.  This uses up the two 1’s but there are n – 2 1’s left over.  So we have n things to arrange:  two blocks, and n – 2 1’s.  This may done in

4\displaystyle{n \choose 2}

ways, since we first choose the 2 places for the blocks, but then multiply by 4 since each block has two possibilities:  021 or 120.

In the second case, if the 2’s are only separated by one number, we may have a block of 02120 and n – 1 1’s to place, giving n possibilities. With a block of 12021, we have the block, one 0, and n – 2’s to place, which can be done in

\displaystyle2{n\choose2}

ways (since the order of the block and the one 0 matters). Adding these three cases together results in

\displaystyle4{n\choose2}+n+2{n\choose2}=3n^2-2n

possible lineups for the Knights and Rogues.

Interestingly, these are the octagonal numbers (A000567 in the OEIS).  I have no idea why, though….

What I like about this problem is that parameterizing p, q, and r in different ways produces seemingly very different results.  One interesting parameterization is p = q = r = n.  It turns out that this sequence — at least the first several values, which I used the computer to generate and didn’t work out by hand — is also in the OEIS (A141147), and the description is the

number of linear arrangements of n blue, n red and n green items such that the first item is blue and there are no adjacent items of the same color (first and last elements considered as adjacent).

I find this particularly intriguing since in Knights and Rogues, 0’s and 1’s can be adjacent — but even though 2’s are not adjacent, it is not possible to have any block be 020 or 121, although these are counted in A141147.  Finding a bijection between the two linear arrangements would be a very interesting problem.

I hope you enjoyed reading about Knights and Rogues!  Again, this is another example of mathematics as it happens — I came up with this problem within the past few weeks, and I’ve just scratched the surface of this interesting puzzle.  I hope it’s actually a new problem, but I won’t be surprised if I get a comment like, “Oh, I saw that problem in…..”  Generating new, novel mathematics problems is not an easy task…..

And incidentally, the answer to the initial problem is 80,096.  Did you get it?