Sunday, January 15, 2017

Points In A Circle Problem: Various Notes On N = 3

I haven't had much time to think about the problem lately, what with all the Holiday Challenge action, but there are a few notes from my notebook that I thought I would record. I'll begin by stating the problem once again using our compact notation.

Given N obstacle points X1, …, XN in the closed unit disk, let

aN(X1, …, XN)

denote the greatest possible area of a triangle in the disk that doesn't strictly contain any of the Xi. Let

aN* = minimum possible value of aN(X1, …, XN).

Then for each given value of N, our problem is to calculate aN* and find a minimal set of obstacles—that is, N points Xi* for which aN(X1*, …, XN*) = aN*. 

So far, here is what we know:
  • a1* = 1 and a1(X) = 1 if and only if X = O, the center of the disk.
  • a2* = 1 and a2(X1, X2) = 1 if X1 = O or X2 = O.
  • a3* ≤ a3(O1, O2, O3) = 0.8286369…, a value we'll abbreviate by A0.
Here, the points Oi are equally spaced around a circle of radius r0 = 0.320963….

Now the notes (edited 1/16/2017 to correct the error noted below in the comments):

1) If all three obstacle points are located a distance at least 0.798677… from the disk center, then an equilateral triangle inscribed in a centered circle of radius 0.798677… is feasible and has area greater than A0. Such a set of obstacle points therefore can't be minimal. (We'll strengthen this statement at the end of the post.)

2)  Because the long side of an edge triangle passes the disk center at a distance ½r0 = 0.16048… from the origin, it follows that if any obstacle point were located less than a distance 0.16048… from the origin, then we could produce a feasible triangle of area greater than by A0 by first drawing a feasible edge triangle and then pushing its long side inward toward the center. (To see that a feasible edge triangle exists, first rotate and reflect the disk if necessary so that any obstacles with r ≥ 0.16048… are in the closed upper half-disk. Then the edge triangle to the bottom of the disk is feasible.) Thus, a set of minimal obstacles must be confined to the annulus 0.16048 ≤ r < 1.

Confining the minimal obstacles to an annulus or some other two-dimensional region probably doesn't help fundamentally with solving the problem, because it doesn't reduce the problem's dimensionality. However, confining the obstacles could conceivably help with ruling out various cases one might find oneself considering; and it does reduce the acreage of the problem, which could increase the power of some numerical experiments.

Continuing with items from the notebook:

3) A natural question to ask is whether the conjectured minimal set {O1, O2, O3} is stable. That is, could you perturb the Oi slightly and obtain a better set of obstacles?

I think not…when I wrote a quickie computer program to evaluate several million small perturbations of the triple, for every perturbation the computer was able to find a triangle of area greater than A0 (by checking the perturbed edge and spotlight triangles). This isn't a proof of stability, of course. (Nor would a stability proof be enough by itself to establish that the Oi are a minimal set: better obstacles might exist but not be obtainable by a small perturbation of the Oi.)

One easy result that at least relates to stability is the following: If {X, Y, Z} is a minimal set of obstacles and triangle XYZ is congruent to triangle O1O2O3 by a rigid motion with a sufficiently small translation, then {X, Y, Z} is a rotation of {O1, O2, O3}. In simpler terms: if you hold triangle O1O2O3 rigid and nudge it off the center of the disk, possibly with some rotation, then the resulting points are no longer a minimal set of obstacles.

To see this, let t be the nonero vector pointing from the center of the disk to the center of triangle XYZ. Translate triangle XYZ back to the center of the disk via −t to form triangle X'Y'Z'. Triangle X'Y'Z' is just a rotation of triangle O1O2O3, which means that the edge triangles through the sides of triangle X'Y'Z' all have area A0. Now define the unit vector u1 pointing directly away from Y'Z', unit vector u2 pointing directly away from Y'X', and unit vector u3 pointing directly away from X'Z'. Now, you can't run against all three of these directions at once: at least one of the inner products t·ui must be positive. This is easy to show by a sketch, or by choosing coordinates so that u1 = (0, 1), u2 = (Sqrt[3]/2, −½), u3 = (−Sqrt[3]/2, −½), and t = (tx, ty). So if, say, t·u1 is positive, then for sufficiently small ||t||, the area of the edge triangle through YZ exceeds the area of the edge triangle through Y'Z'. But the edge triangle through Y'Z' has area A0, so the area of the edge triangle through YZ exceeds A0, and the obstacles X, Y, Z are not a minimal set.

4) Because the problem of N + 1 obstacles includes the problem of N obstacles as a special case, we have aN* ≤ aM* whenever NM.

Proof (example): Suppose {P, Q, R, S} is a minimal set of obstacles for N = 4, and {X, Y, Z} is a minimal set obstacles for N = 3. Then we have

a4(P, Q, R, S) = a4* ≤ a4(X, Y, Z, Z) = a3(X, Y, Z) = a3*

so that a4* ≤ a3*.

Because of this, any bound we find for small N becomes a bound on all higher values of N also. (The N = 3 bound a3* ≤ A0 implies the bound aN* ≤ A0 for all N ≥ 3.)

5) A minimal set of 3 or more obstacles can't consist of collinear points. If the obstacles were collinear, there would exist a feasible triangle of area 1, which exceeds A0, so that the obstacles couldn't be minimal.

6) For any diameter of the disk, there must be at least one obstacle on either side of that diameter, otherwise again there would exist a feasible triangle of area 1. (From this it also follows that any diameter of the disk contains at most one obstacle.)

7) Let's draw the three edge triangles ABC, DEF, GHI passing through points O1, O2, and O3:


If all three obstacle points X, Y, Z were to be located outside of any single edge triangle, then that edge triangle could be perturbed to create a feasible triangle of greater area. So the apportionment of minimal obstacle points among the 22 regions shown is not arbitrary. For example, it is easy to check that every region in the diagram falls outside of some edge triangle, so that in a minimal set of obstacles, no single open region can contain all three obstacle points.

8) Let's go further and draw not only the three edge triangles ABC, DEF, GHI, but also the six spotlight triangles ABJ, ABK, DEL, DEM, GHN, GHP:


In this diagram, the regions are sub-regions of the regions in the previous diagram. Therefore all three obstacles in a minimal set can't be located in any single region of this diagram either. And similarly to before, if all three obstacles in a minimal set were to be located outside of any one of the nine triangles, then that triangle could be perturbed to create a feasible triangle of greater area. So again the apportionment of minimal obstacle points among the regions is not arbitrary.

There are 82 regions altogether, which results in 95,202 ways to place the obstacle points. Listing these ways with a computer is easy; in Mathematica we can do it like this:

Flatten[Map[Permutations, IntegerPartitions[3, {82}, {0, 1, 2}]],1]

It is also easy to tell the computer which regions belong to which triangles, enabling an automated check of whether any given apportionment of the three points results in a forbidden circumstance of all three obstacle points lying outside of any of the nine triangles that define the figure. The configurations falling afoul of this rule then get culled.

For example, one of the configurations that gets culled is this one, because putting an obstacle point in each of the shaded regions leaves all of the obstacle points outside of triangle ABJ. You could slide vertex J downward and it would increase the altitude on side AB, thus increasing the area beyond A0; this shows that the implied set of obstacles is not minimal.


One of the configurations that survives the culling is this one:



You can verify that placing an obstacle point in each of the shaded regions guarantees that all nine of the triangles contain at least one obstacle point. The bottom region guarantees triangles ABJ, ABK, DEF, GHN, and GHP; the region touching that one guarantees triangles ABC, DEL, DEM; and the region near the top guarantees triangle GHI.

A total of 411 configurations survive, and by telling the computer which regions map to which regions under symmetries of the figure, these can be reduced to 79 distinct configurations. Here is an animation showing all 79 of them:


Certain regions of the diagram are absent from all of the valid configurations; therefore in a minimal set of obstacles, no obstacle point can be located in these regions. The forbidden regions are shaded here:


Of course, we could have drawn the original nine triangles oriented at some other angle. If a region is excluded in one orientation, it is excluded in all orientations. This means that no obstacle point in a minimal set can be so far from the origin that it belongs to some forbidden region in any orientation. The innermost point of any forbidden region is located a distance 0.76664… from the center of the disk. This shrinks the annulus to which obstacle points in a minimal set must belong: the known bounds are now r ≥ 0.16048… and r ≤ 0.76664….

Wednesday, January 4, 2017

More Book Titles With Curious Properties

I couldn't help generalizing the 4th Holiday Challenge…so here are some more book titles with special properties.

If you know of better answers in the following categories (or additional categories altogether), put them in the comments and I'll update the list. Rules for subtitles etc. are the same as in the Holiday Challenge. (Also, I am not including juvenile books.)


Book Titles With Special Properties


Title at least three words long; all words have the same number of letters

Less Than Zero, by Bret Easton Ellis


Title at least four words long; words in alphabetical order

The Time Traveler's Wife, by Audrey Niffenegger


One-word fiction titles; most and fewest letters

Immortality, by Milan Kundera

Scaramouche, by Rafael Sabatini

It, by Stephen King


One-word nonfiction titles; most and fewest letters

Hydrofunctionalization, ed. V.P. Ananikov and M. Tanaka

FDR, by Jean Edward Smith


Most words in a fiction title with every word at least 6+ letters

Everything Ravaged, Everything Burned, by Wells Tower

Brideshead Revisited, by Evelyn Waugh


Most words in a fiction title with every word at most 3+ letters

How It Is, by Samuel Beckett

The Name of the Rose, by Umberto Eco

In the Café of Lost Youth, by Patrick Modiano


Most words in a nonfiction title with every word at least 8+ letters

Teachers' Pedagogical Thinking: Theoretical Landscapes, Practical Challenges, by Pertii Kansanen et al.

Imperialism: Theoretical Directions, ed. Ronald H. Childcote

Organometallic Photochemistry, by Gregory L. Geoffroy and Mark S. Wrighton

Honorable mention for literary nonfiction: Slouching Towards Bethlehem, by Joan Didion (every word at least 7 letters)


Most words in a nonfiction title with every word at most 3+ letters

How We Won the War, by Vo Nguyen Giap and Van Tien Dung

What We Eat When We Eat Alone, by Deborah Madison



2016 Holiday Challenge: Results for Challenge 4, Book Titles

The final challenge, and the most open-ended of the challenges this year, was Challenge 4:
Like You'd Understand, Anyway. That's the title of a 2007 book of short stories by Jim Shepard. It's an unusual title because its shortest word is four letters long. Can you think of any other published books (fiction or nonfiction) in which the shortest word in the title is at least four letters long? The more words in the title, the better.
I should say that when I published this puzzle, I didn't know of a better answer than Like You'd Understand, Anyway. But I was confident that my readers would do better, and they did! I'll list the best answers I received, but first let me settle some ambiguities that various readers asked me about via email.
  • What qualifies as "a book"? Higher-quality answers will appear in the Library of Congress. But at the very least, there has to be an ISBN assigned.  
  • In Fahrenheit 451, the numeral 451 counts as a single "word" of three "letters." Other non-letter characters like ampersands, asterisks, etc., are handled similarly.
  • Sometimes it's hard to decide what "the title" of a book is. For example, I have an edition of The Hobbit that shows the title on the cover as The Hobbit, but then the inside title page adds Or There and Back Again in smaller font underneath. In such cases, I decide what "the title" of a book is by relying on the Library of Congress. They use a markup scheme called MARC to log books in the collection. According to this scheme, "the title" consists of the contents of MARC data field 245, subfields (a) and (b). For the case of The Hobbitlooking at the MARC data tells us that the title is seven words long. For subtitled books that aren't in the Library of Congress, we'll include the subtitle because that's the pattern we tend to find in MARC.

Without further ado, here are the best titles I received for Challenge 4, listed alphabetically within word count. Some of these were submitted by more than one reader. My two favorites are in bold: these get the job done without using subtititles—and they're fiction, where we don't expect to see so many examples. 

Whose Science? Whose Knowledge? Thinking from Women's Lives, by Sandra Harding

Your Healthy Journey: Discovering Your Body's Full Potential, by Fred Bisci

California Dreaming: Reforming Mathematics Education, by Suzanne Wilson

Dirk Gently's Holistic Detective Agency, by Douglas Adams

Julius Knipl, Real Estate Photographer, by Ben Katchor

Last Stand: America's Virgin Lands, by Barbara Kingsolver

Let's Explore Diabetes with Owls, by David Sedaris [1/12/2017]

Everything Ravaged, Everything Burned, by Wells Tower

Jeremy Thatcher, Dragon Hatcher, by Bruce Coville

Letter from Birmingham Jail (rare book illustrated by Faith Ringgold)

Miss Julia Takes Over, by Ann Ross

These Happy Golden Years, by Laura Ingalls Wilder

Willie Masters' Lonesome Wife, by William H. Gass

Finding these examples isn't easy! Some of the submissions I received arose from clever strategies, such as looking at 19th century books, and noticing that self-help books tend to have long titles with phrases like "Finding Your Inner."

Reader Ronda was the first person to send a published book title of at least four words with each word at least four letters long. And reader Beth K. won this year's drawing. Congratulations, both—a copy of Word Games 5 is on its way to you!

That wraps up the 2016 Holiday Challenge! Thanks for participating this year. My best wishes to everyone for a happy and healthy 2017.

Tuesday, January 3, 2017

2016 Holiday Challenge: Results for Challenge 3, Lewis Carroll's Two Walkers Problem

Holiday Challenges typically can't be solved by googling or opening a reference book. With Lewis Carroll's problem of the two walkers, I made an exception. This is just a math problem, and if you have Carroll's book Pillow Problems, you can look up the answer. You could even google the words in the puzzle and find Lewis Carroll's solution online. But I like the problem, and it's not so easy to get it right, either. Several readers submitted partial solutions, but nobody solved the problem fully. Even Carroll's answer was incomplete, as I'll discuss at the end.
A and B begin, at 6 a.m. on the same day, to walk along a road in the same direction, B having a start of 14 miles, and each walking from 6 a.m. to 6 p.m. daily. A walks 10 miles, at a uniform pace, the first day, 9 the second, 8 the third, and so on: B walks 2 miles, at a uniform pace, the first day, 4 the second, 6 the third, and so on. When and where are they together?
If you know how to make a distance-time graph, that's probably the easiest way to solve the problem. It's basically just transferring the narrative to paper. Here's what my graph looked like:


The two walkers are together for a single instant of time at noon on the third day, when they are both momentarily 23 miles from A's starting point, and later they are together for a period of time lasting from 6 p.m. on the fourth day until 6 a.m. the following morning, when they are both 34 miles from A's starting point. These are all the times and places where the two curves coincide.

Here are two distance-time graphs that I made on a computer. In the second one, I've excised the periods of night when the walkers are stationary.




In my first attempt at the problem, I didn't make a graph; I just scribbled down numbers for how far the two walkers were at the end of each day. Eyeballing the numbers, you can see that they pass each other on Day 3 and come together again at the end of Day 4. Figuring out the exact time of the meeting on Day 3 then takes a little more number-crunching.

Two readers found the solution at noon on Day 3. To see why this isn't the only solution, visualize the motion carefully. When A passes B at noon on Day 3, A is (of course) going faster. But A is slowing down, and B is speeding up, so it is inevitable that B will catch up to A sooner or later. (There's a problem like this in my physics book.)

Looking back at the original question with the answer in hand, one sees that Carroll chose his words carefully. Had he asked, "When and where do they meet?" the first crossing of the curves alone might be considered a sufficient answer. After all, A and B do meet there. (And in English, the word "meet" tends to suggest a first meeting.) Instead Carroll asks, "When and where are they together?" This elegant phrasing calls for a complete account of all the coincidences of the curves without telegraphing how many there will be.

Here's an animation I made to illustrate the problem. Walker A is the little blue line, and walker B is the larger green line. The pauses correspond to periods of night (6 p.m. to 6 a.m.) when the walkers are stationary.


Here's the same animation excluding periods of night:



Lewis Carroll's solution was more technical than just scribbling down numbers, or drawing a graph; it involved setting up a quadratic equation. Here's that approach in my own words.

Let An be the location of walker A at the completion of the nth day. Then, for example, A4 = 10 + 9 + 8 + 7. We could write this as A4 = 10 + 10 − 1 + 10 − 2 + 10 − 3, or 4 × 10 − (1 + 2 + 3). More generally, An = 10n − (1 + 2 + 3 + … + n − 1). Knowing that 1 + 2 + 3 + … + k = k(k+1)/2, we therefore have
An = 10nn(n − 1)/2.
Similarly if Bn is the location of walker B at the completion of the nth day, then by a similar process we find
Bn = 14 + n(n + 1).
The condition that A and B occupy the same location at the end of the nth day is AnBn = 0, or
10nn(n − 1)/2 − 14 − n(n + 1) = 0.
There are two real solutions, n = 4 and n = 7/3 = 2.333…. The solution n = 4 is easy to interpret: it means that at the end of the 4th day, the two walkers are at the same location. The second solution is, technically speaking, extraneous, because our variable n is supposed to be a whole number. But the fact that AnBn equals zero for n = 2.333… clues us that the quantities A2B2 and A3B3 have different signs, meaning that the walkers pass each other sometime during the third day. We can analyze the third day separately to find out when that happens, which is what Carroll proceeded to do.

In Pillow Problems, Carroll's final answer to this problem reads, "They meet at end of 2d. 6h., and at end of 4d. : and the distances are 23 miles, and 34 miles." That's a true statement. However as noted above, the question wasn't asking about when they meet; it was asking about when they are together. A complete statement of when the two walkers are together has to mention all of the times when they are together during the course of the situation described. That includes times such as 4d., 1h. So I consider a complete answer to the stated problem to be,
They are together at noon on the third day, 23 miles from A's starting point, and from 6 p.m. on the fourth day until 6 a.m. the following morning, 34 miles from A's starting point.

These are called "pillow problems" because Carroll solved almost all of them mentally while lying awake in bed—only writing down the solution after he had it, and only writing down the problem statement after that. Some of these feats of solving are tremendously impressive, notwithstanding Carroll's statement, in the self-effacing introduction to the first edition, that at first he himself could make little progress, only discovering with practice that he had become better at holding diagrams or equations in the mind long enough to work with them.

Carroll also writes about the errors that inevitably creep into such a process. In the case of the two walkers, I had to wonder if Carroll allowed himself just a little imprecision because he found the idea of A and B spending the night together a little too awkward to mention. Or maybe it was just an oversight. Carroll humorously anticipates such things in his introduction's final paragraph:

Other mistakes may perchance … await the penetrating glance of some critical reader, to whom the joy of discovery, and the intellectual superiority which he will thus discern, in himself, to the author of this little book, will, I hope, repay to some extent the time and trouble its perusal may have cost him!
C.L.D.
CH. CH., OXFORD
May, 1893

This coda is yet another example of Lewis Carroll's habit of speaking with tongue in cheek.

That's it for Challenge 3; tomorrow we'll wrap up the Holiday Challenge with some impressive book titles supplied by readers!

Monday, January 2, 2017

2016 Holiday Challenge: Results for Challenge 2, Candy Cane Word-Find

My readers appear to have solved this puzzle much faster than I did. Congratulations to reader Sharmin, who solved it first—a copy of Word Games 5 is on its way!


By the way, the email edition of yesterday's post was missing an embedded video, so for the benefit of my email subscribers, here's a direct link to Lisa Simpson challenging Bart Simpson to a game of rock/paper/scissors. (The video underlines that you shouldn't necessarily attribute rationality to your opponents!)

Getting back to Challenge 2, I thought people might like to see the process I use to create these word-find puzzles, so here is some detail on that.

The first thing is to rank the letters of the alphabet according to their visual density. I'll skip the steps for this and give the result:

I, Z, L, T, Y, P, C, F, J, E, S, A, B, R, G, K, H, V, X, D, U, O, Q, M, W, N

Next, we rank the words in the dictionary according to their dynamic range. Ideally, we want words like NINJA, which include both low-density letters (I, J) and high-density letters (N). That allows us to "paint" with a broad palette. But I had a hard time coming up with a holiday puzzle about ninjas, so I downloaded a list of holiday theme words from a teacher website:

ANGEL, BELLS, BIRTH, BLIZZARD, BLUSTERY, BOOTS, BOUGH, BOW, BOX, CANDLE, CANDY, CANDYCANE, CAP, CARD, CAROLERS, CAROLING, CAROLS, CELEBRATE, CELEBRATION, CEREMONY, CHARITY, CHESTNUTS, CHILL, CHILLY, CHIMNEY, CHRISTMAS, CHRISTMASCARD, CHRISTMASCAROL, CHRISTMASEVE, CHRISTMASTIDE, CHRISTMASTREE, CHRISTMASTREESTAND, CIDER, COAL, COLD, COOKIE, CRECHE, DECEMBER, DECORATE, DECORATIONS, DISPLAY, EGGNOG, ELF, ELVES, EVE, EVERGREEN, EXCHANGE, FAMILY, FAMILYREUNION, FATHERCHRISTMAS, FEAST, FELIZNAVIDAD, FESTIVAL, FESTIVE, FIR, FIREPLACE, FIREWOOD, FRANKINCENSE, FROSTY, FROSTYTHESNOWMAN, FRUITCAKE, GARLAND, GIFT, GIFTGIVING, GINGERBREAD, GINGERBREADHOUSE, GINGERBREADMAN, GINGERBREADWOMAN, GIVE, GOLD, GOODWILL, GOOSE, GREEN, GREETINGS, GUEST, HAPPY, HOLIDAY, HOLLY, HOPE, HOTCHOCOLATE, HOTCIDER, HUG, ICESKATES, ICICLE, ICY, IVY, JACKFROST, JESUS, JINGLEBELLS, JOLLY, JOY, JOYFUL, JOYEUXNOEL, KINGS, KRAMPUS, KRISKRINGLE, LIGHTS, LIST, LOG, LOVE, MANGER, MERRY, MERRYCHRISTMAS, MINCEPIE, MISTLETOE, MITTENS, MYRRH, NATIVITY, NAUGHTY, NICE, NIPPY, NOEL, NORTHPOLE, NUTCRACKER, OCCASION, ORNAMENTS, PACKAGE, PAGEANT, PARADE, PARTRIDGE, PARTY, PIE, PINETREE, PINECONE, PLUMPUDDING, POINSETTIA, POPCORNSTRING, PRESENTS, RECEIVE, RED, REINDEER, REJOICE, REUNION, RIBBON, RITUAL, RUDOLPH, SAINTNICHOLAS, SALES, SANTACLAUS, SANTASELVES, SANTASHELPERS, SANTASLIST, SANTASWORKSHOP, SCARF, SCROOGE, SEASON, SEASONSGREETINGS, SHOPPING, SKATE, SLED, SLEIGH, SLEIGHBELLS, SNOW, SNOWBALL, SNOWBOUND, SNOWFALL, SNOWFLAKE, SNOWMAN, SNOWY, SOCKS, SPIRIT, STAR, STNICK, STOCKING, STOCKINGSTUFFER, SUGARPLUM, SWEATER, TIDINGS, TINSEL, TOBOGGAN, TOGETHERNESS, TOY, TRADITION, TREE, TRIMMING, TRIPS, TURKEY, UNWRAP, VACATION, VISIT, WASSAIL, WINTER, WINTERTIME, WINTRY, WISEMEN, WISH, WONDER, WORKSHOP, WRAP, WRAPPINGPAPER, WREATH, XMAS, YULE, YULELOG, YULETIDE

Sorting these according to their dynamic range yields

{{WINTRY}, {NICE}, {NOEL}, {TRIMMING}, {WINTER}, {TOY, WISH}, {GOODWILL}, {WINTERTIME}, {MITTENS}, {NIPPY}, {TIDINGS}, {PINECONE}, {WISEMEN}, {CHIMNEY}, {LOG}, {TRADITION}, {FAMILYREUNION}, {MINCEPIE}, {COLD}, {SNOWFALL}, {SNOWY}, {REUNION}, {TINSEL}, {SNOWBALL}, {STNICK}, {PLUMPUDDING}, {NATIVITY}, {KINGS}, {HOLLY, IVY, JOY}, {OCCASION}, {CANDY}, {SAINTNICHOLAS}, {VACATION}, {CAROLING}, {STOCKING}, {GIFTGIVING}, {RIBBON}, {SHOPPING}, {HOLIDAY}, {CANDLE}, {NORTHPOLE}, {POINSETTIA}, {GOLD}, {POPCORNSTRING}, {FELIZNAVIDAD}, {COOKIE}, {LOVE}, {ANGEL}, {FIREWOOD}, {FAMILY}, {MISTLETOE}, {COAL}, {YULELOG}, {FRANKINCENSE}, {JOYEUXNOEL}, {JOYFUL}, {CEREMONY}, {CANDYCANE}, {FROSTYTHESNOWMAN}, {DECORATIONS, ORNAMENTS}, {YULE}, {NAUGHTY}, {SNOWFLAKE}, {JOLLY}, {UNWRAP}, {WRAP}, {RITUAL}, {WASSAIL}, {BOOTS}, {CELEBRATION}, {YULETIDE}, {HOTCIDER}, {PINETREE}, {CHESTNUTS}, {KRISKRINGLE}, {RUDOLPH}, {REINDEER}, {HOTCHOCOLATE}, {GIVE}, {VISIT}, {WRAPPINGPAPER}, {BLIZZARD}, {SANTASLIST}, {JINGLEBELLS}, {PAGEANT}, {GREETINGS}, {CIDER}, {GARLAND}, {STOCKINGSTUFFER}, {HOPE}, {CHRISTMASTIDE}, {SANTACLAUS, WREATH}, {GINGERBREADWOMAN}, {SUGARPLUM}, {TOBOGGAN}, {MERRY}, {SLED}, {BIRTH}, {GINGERBREADMAN}, {CHRISTMAS}, {SNOW}, {SEASON}, {MYRRH}, {SEASONSGREETINGS}, {CHRISTMASTREESTAND}, {SANTASWORKSHOP}, {LIGHTS}, {MERRYCHRISTMAS}, {CHRISTMASCAROL}, {NUTCRACKER}, {FROSTY}, {PRESENTS}, {TURKEY}, {MANGER}, {GREEN}, {SNOWMAN}, {DISPLAY}, {TOGETHERNESS}, {FIR}, {CAROLS}, {REJOICE}, {CHILL}, {SWEATER}, {SLEIGH}, {WORKSHOP}, {WONDER}, {CHRISTMASCARD}, {GUEST}, {BOW}, {CHRISTMASEVE}, {GINGERBREAD, SANTASELVES}, {FRUITCAKE}, {DECORATE}, {XMAS}, {KRAMPUS}, {EXCHANGE}, {BLUSTERY}, {GIFT}, {CHRISTMASTREE}, {PARTRIDGE}, {GINGERBREADHOUSE}, {FATHERCHRISTMAS}, {CHARITY}, {SANTASHELPERS}, {SCROOGE}, {GOOSE}, {EGGNOG}, {SOCKS}, {CHILLY}, {DECEMBER}, {CAROLERS, FESTIVAL}, {SLEIGHBELLS}, {FESTIVE}, {JACKFROST}, {SNOWBOUND}, {CARD}, {SPIRIT}, {RECEIVE}, {ELVES}, {EVERGREEN}, {TRIPS}, {HAPPY}, {RED}, {JESUS}, {BELLS}, {PARADE}, {EVE}, {BOX}, {PIE}, {PARTY}, {ICESKATES}, {LIST, STAR}, {SKATE}, {FIREPLACE}, {TREE}, {CRECHE}, {BOUGH}, {CELEBRATE}, {PACKAGE}, {ICICLE}, {SALES}, {ELF}, {CAP}, {FEAST}, {HUG, ICY}, {SCARF}}

Some of these looked good (like TOY) but didn't quite work out. Eventually I tried CANDY, doing an image search online for a line drawing of a candy cane. I was looking for a blocky image that would remain recognizable when converted to a low-resolution letter grid. Here was the image I chose:


I resized the image to 72 pixels by 40 pixels, and then created a histogram of pixel saturation:


Eyeballing the peaks in the histogram, I assigned a letter to each pixel according to the following rule:
  • Pixel saturation 0.9 or less:  Replace pixel with C or Y (flip a coin)
  • Pixel saturation between 0.9 and 2:  Replace pixel with letter A
  • Pixel saturation between 2 and 3.5: Replace pixel with letter D
  • Pixel saturation greater than 3.5:  Replace pixel with letter N.
Now I had a grid of letters resembling a candy cane. I ran the grid through a word-search-solver that I wrote a long time ago, just to see what words were present in the grid. I found several instances of short words like AND, with maybe a CYCAD or two—but no CANDY.

Even after ten thousand attempts, I still didn't have a grid with CANDY. I diagnosed the problem as not enough Ds next to Ys (or something like that), so I added some blurring to the pixel rule for saturation above 3.5. Instead of replacing all of these pixels with Ns, I set it to be 93% likely to replace the pixel with an N, with 7% likelihood of C, D, or Y. With this rule, the image still looked like a candy cane, and it only took around 500 attempts to produce a grid with one instance of CANDY in it. (I had to solve the puzzle myself, because my word-search solver tells me which words are in a grid, but not where they are located!)

From there I adjusted the font size and spacing of the grid in Microsoft Word, and the puzzle was finished.


Most ASCII art looks a lot nicer than this, as you can see from a google search. In part, that's because of the crudeness of my algorithm; it's also because most ASCII art uses a much larger character set with much greater dynamic range. Some programs even help themselves to different font colors.


I'll leave you with the first known example of typewriter art, this butterfly created by Flora Stacey in 1898. Stacey created striking effects by the technique of rotating her paper in the typewriter.


Nowadays you can upload images to websites like this one and have them converted into ASCII instantaneously.

Results of Challenge 3, Lewis Carroll's problem of the two walkers, coming next!

Sunday, January 1, 2017

2016 Holiday Challenge: Results for Challenge 1, Rock Paper Scissors

I'm not sure what the psychology of this is, but my readers mostly threw Rock, and that means I lost bigly, because my throw was Scissors!

The first person to beat me on their first try was reader Bill M.—but I have reason to know that Bill already owns a copy of Word Games 5, so the prize for Challenge 1 goes to reader Joanie, who threw Rock just an instant after Bill did. Congratulations, Joanie! A copy of Word Games 5 is on its way.

For what it's worth, I chose my throw randomly, with probabilities ⅓—⅓—⅓. According to classical game theory, this the optimal strategy (the so-called "Nash equilibrium"). Of course, the theory assumes that both players are rational, whereas in real life this is seldom the case. You'd be leaving a lot of money on the table if you played ⅓—⅓—⅓ against a little kid.  


In Challenge 1, we only played a single round. But rock/paper/scissors is usually played as a series of multiple rounds, creating a so-called "supergame." The mathematical theory of supergames is much more complicated than for single games, especially when the underlying game is non-zero-sum. This is due to the presence of such factors as signaling. You might have heard of the famous Prisoner's Dilemma tournament of 1980, created by political scientist Richard Axelrod. In Axelrod's tournament, game theorists and others submitted computer programs that repeatedly played Prisoner's Dilemma against one another. The winning strategy, submitted by Anatol Rapoport, was TIT-FOR-TAT. This profound strategy makes an initial friendly move and thereafter simply repeats whatever its opponent does. These matters are still lively topics of discussion in evolutionary biology (reciprocal altruism), economics, and other fields. Here is a bit more on TIT-FOR-TAT.

Bennington College held a tournament like Axelrod's when I was there, with each science professor advising a team of students. A team was allowed to submit more than one entry to the tournament. My team won the tournament by using the dastardly meta-strategy of coordinating our entries. We submitted one primary strategy, plus several copies of a secondary strategy. We pictured the primary strategy as being like an ant, and we pictured the secondary strategies as being like aphids, whose purpose was to be milked by the ant. Aphids were programmed to play a predetermined initial sequence of moves that would identify them to the ant. At first, until the ant was confident that it was dealing with an aphid, the ant played TIT-FOR-TAT. But as soon as the ant was confident that it was dealing with an aphid, the ant started milking it by playing an insanely aggressive strategy, which the aphid would do nothing to counter.  Of course, only the ant knew that there were aphids in the tournament available for milking, so only the ant racked up those easy points. The other competitors were understandably annoyed when we revealed how we'd won, but they had to acknowledge that we were within the rules (which hadn't anticipated coordination of strategies). So the trophy—an ant farm, as it turns out—went to our team.

My kids won the 2014 Holiday Challenge, which was a game of Hangman. This year, they wanted to play rock/paper/scissors, so I wrote a computer program they could play it on. The program is a simple Bayesian updater. The more you play, the better the program learns your tendencies. At each stage, it uses what it knows to choose the best throw. Here is an animation showing how the computer makes sharper and sharper predictions over time for what your next throw will be.


I would guess that over the long run, the best you can do against this program is to play ⅓—⅓—⅓ resulting in a stalemate. But the computer probably has exploitable weaknesses during a run of five to ten games.


I'll end with some "news you can use"—an article called "How to Beat Anyone at Rock Paper Scissors," published by the World RPS Society. (There had to be a society.) The article has some pretty good tips! In any case, the theory of RPS seems to be better documented online than the theory of Hangman. You could also check out this article summarizing the findings of an experiment in which people played rock/paper/scissors for money.


P.S. And in the category of "anything can be exciting," I give you this 4-minute video of the final round of the 2007 US Championships of Rock/Paper/Scissors. 

Saturday, December 31, 2016

Free Speech Among The Deplorables

1.

Carl Paladino, a wealthy Buffalo businessman, likes to send racist emails. Several of these were published (NSFW) when he ran for Governor of New York in 2010. This month's stir was bigger. Paladino apparently wrote a private reply to a newspaper's year-end quiz, intending to amuse his friends with it, but then he mistakenly sent the reply to the newspaper instead. Here are Paladino's published New Year's wishes:


In response to these comments, many in Buffalo have demanded that Paladino be removed from the city's school board, to which he was re-elected in May. The board has now voted 6–2 to ask the state Education Commissioner to remove him.

Personally, I believe Carl Paladino lacks the baseline character required of an educator. But whether the state's regulations, and the political forces arrayed on all sides, will actually permit his removal is something Commissioner Elia will have to judge. Jim Heaney, a Buffalo journalist and apparently no friend of Paladino's, has argued that executive action isn't the best approach in the present case. Among other ideas, Heaney suggests calling a special election for Paladino's board seat. If that were feasible, it sounds to me like a good idea: voters gave Paladino his authority, and ideally voters should be the ones to take it away. And I do think Paladino would lose…in May, he was nearly unseated by a high school student.

2.

Pamela Ramsey Taylor, director of a county nonprofit group in West Virginia, was removed by her board of directors in connection with a state investigation that began when Taylor posted a racist slur about Michelle Obama to her Facebook page. Mayor Beverly Whaling of Clay, West Virginia, who had commented approvingly on Taylor's post, quickly resigned her office as well.


What these people wrote is cruel and disgusting, and their apologies were insufficient. (Taylor's is here.) Yet was it fair for Whaling and Taylor to lose their jobs over this? Should the p.c. police be trawling Facebook for thought-crimes to punish people for IRL?

While I do object to p.c. thought-policing, that isn't a good description of what happened here. Mayor Whaling resigned under public pressure: those are the breaks. When you're an elected politician, you serve at the whims of the Mob, and your speech has a lot to do with it. And as I understand it, Taylor was removed in the first instance not for the content of what she posted, but rather because her post raised reasonable concerns in the Governor's office about the quality of service that Taylor's agency was providing to county residents under her leadership. And let's be real here: if you're a county-level services provider and the Governor of the state knows you by name, you done fucked up.

3.

Milo Yiannopoulus, a controversial right-wing pundit, recently signed a lucrative publishing contract with Threshold Editions, an imprint of Simon & Schuster. This has led some people on the Left to contemplate a publisher boycott. The Chicago Review of Books tweeted this:


I'll be interested to hear what the American Library Association says about this. The ALA hosts an annual campaign called "Banned Books Week", and although the word "banned" usually overstates what the ALA is criticizing, the basic idea that animates Banned Books Week is excellent:
Banned Books Week brings together the entire book community; librarians, booksellers, publishers, journalists, teachers, and readers of all types, in shared support of the freedom to seek and to express ideas, even those some consider unorthodox or unpopular.
By (literally) banning all of Simon & Schuster's books from its pages, the Chicago Review of Books directly contradicts these aims.

I hope this decision is reversed; it isn't even consistent with the journal's stated mission:
We seek to explore the connections between literature, current events, and pop culture. Our contributors are as diverse as the books we cover, from established authors, journalists, and writing professors to students and freelance critics.
What happens when even our literary journals lose faith in the power of words? The Chicago Review ought to fight Yiannopoulos's book by doing what it does best: writing a review of it.