By Josh Feldman
I don’t know about you, but by the end of winter this year, I needed a vacation. While I couldn’t escape the pandemic, I needed a change of scenery, and to spend time away from my home, where I have spent too much time both living and working. And thanks to all my 2020 getting canceled due to COVID-19, I had a lot of vacation time to burn. The only question is, where to go?
With flying not an option, I needed to pick a place that I could drive to in a day—preferably a place with plenty of outdoor activities available. Looking at the map and using the above criteria, it quickly became obvious that I would head to the Crescent City of New Orleans for my first holiday of 2021.
And what a vacation it was. While all my friends and co-workers dealt with polar vortex after polar vortex, I literally took it easy in the Big Easy. No matter where I went, whether it was Audubon Park, Jackson Square, Tulane, or Gabriel Knight’s old stomping grounds, there was always something unique to look at and yummy beignets to be had. And while the locals complained about Mardi Gras temperatures in the 30s, I laughed on the inside knowing it was far, far colder in my hometown.
After my extended stay in New Orleans, it seemed like all my friends had one specific question for me: where do you go running in the biggest city in Louisiana? I told everyone the same answer: that locals and tourists alike ran directly on the streetcar tracks of St. Charles Avenue.
Of course, even during the pandemic the streetcar was in service, so one always has to keep alert when running on the tracks. Yet another reason not to wear headphones while on the run! While one normally runs on the track of the train going in the opposite direction that you are running, occasionally you would need to move to the parallel track to get out of the way of an incoming streetcar.
When I told my friend Big T about my running exploits, he asked me if I was ever in a situation where I couldn’t move to the parallel track, as both myself and two trains going in opposite directions hit the same point simultaneously? I never thought about that possibility while on the run, but did I just get lucky? After many runs, I knew on average I would need to switch tracks an average of 10 times throughout my eight-mile run to avoid the oncoming streetcar.
As anyone who has visited New Orleans can tell you, while the streetcar allegedly has a schedule (in actuality, just like airline flights, it is purely random when they come and go). After doing many runs on St. Charles, I knew that I ran the eight-mile route in an hour, and that streetcars on average travelled at 10 miles per hour. Given the length of a streetcar, I figured I needed at least 0.02 miles of leeway to safely navigate to the parallel track in case I had to switch tracks. Maybe my puzzle friends can help figure out the odds of myself and two streetcars going in opposite directions arriving at the same time…
Problem: Given all of the above information, and assuming that I ran my eight-mile route continuously at 8 mph, streetcars run in both directions at the same frequency, and that streetcars in both directions always traversed the tracks at a constant 10 mph, what is the probability during an eight-mile run of me getting into a sticky situation where myself and two trains going in opposite directions would all hit the same point simultaneously?
Solution to Previous Puzzle: How Many Words in a Crossword Puzzle?
We restrict this puzzle set to crossword puzzles with nxn grids for n = 15 and 7. And rather than counting linguistic words we are counting geometric words; which we call “clues.” A clue is a continuous sequence of white (grid) squares going either across or down starting either at a black square or one edge of the grid and ending at another black square or the other edge of the grid. We are interested in the maximum number of clues under various constraints. We require that each white square be part of both an across clue and a down clue and that the length of a clue (the number of its white squares) be at least 3. Two other common constraints are connectivity and symmetry which vary within this problem set. Connectivity is fairly intuitive; it means that one can go from any white square to any other white square by either a horizontal move or a vertical move but NOT a diagonal move (like a rook in chess).
Symmetry is a little subtle. A symmetry of an object is a transformation of the object which leaves the object looking unchanged. There are 7 symmetries of a square, which with the identity, e – no transformation, comprise the dihedral group of order 8 (the reference to groups can be ignored). There are three rotations: 90°, 180°, and 270°, which I’ll call a, a2 and a3. (xy means x followed by y.) Note that a4 = e. And four flips: across the 45°, the 135°, vertical, and horizontal lines through the center. If we call the first flip b, then the rest are a2b, ab, and a3b, respectively where we are taking the rotations clockwise. There are 10 special subsets of the 7 symmetries; they are the only sets of symmetries which a square grid can satisfy all of while not satisfying any others. The sets are:
Every grid falls into one and only class of grids defined by one of the 10 sets of symmetries.
Problem A: What is the maximum possible number of clues in a
connected 15×15 CWP (crossword puzzle) with only 180° rotation symmetry?
Solution: I said to look it up. That is often the right way to solve problems these days, with our powerful search engines. However, looking something up is not always trivial. In this case, including the word “grid” may be needed.
There is also another possible issue. Problem A contains the constraint “only 180° rotation symmetry,” that is we are considering only the grids also described by Set 6 above. However, “only” is generally not in the references and that allows for grids described by Sets 7 thru 10. Since the class of grids defined by Sets 6 through 10 combined includes more grids than defined by Set 6 alone, that max could be greater. Fortunately, it isn’t.
Problem B: Same as Problem A but change 15 to 7 and prove your answer correct.
Solution: In this case the constraint “only 180° rotation symmetry” makes a difference. Some references found online, for example in the Online Encyclopedia of Integer Sequences or the papers of Kevin Ferland or Ferland and Pratt give the answer as 22. Illustration (1) shows a 7×7 connected grid with 22 clues. However, that grid has all seven symmetries so 22 is the maximum for the union of the classes defined by sets 6 to 10. Illustrations (2) and (3) show two dissimilar examples of grids each with only 180° rotation symmetry. All such maximal clue 7×7 connected grids are similar to one of these two and have only 16 clues.
To prove that the answer is correct, we assume we have a maximal clue 7×7 connected grid with only 180° rotation. The number of clues in our grid will be equal to 14 plus the number of rows and the number of columns that are “special,” where “special” means: WWWBWWW (3 white squares followed by a black square followed by 3 more white squares). By rotating our grid 90° we can assume that the number special columns is at least as great as the number of special rows. We then examine each possible number of special columns and show that the only possible cases are shown in illustrations (2) and (3).
Problem C: Same as Problem A (n=15) but change the symmetry rule (allow a different single symmetry, or multiple symmetries, or none at all)—no proof required.
Answer: For the class of grids defined by Set 6 the answer is clearly 96. For the other classes, I don’t know the answers; the problem is too difficult for me now. Some answers suggested by solvers are shown in the list of solvers. However, the answers for n=7 are not difficult at all; I’ll leave that for you to have fun with.
Problem D: Same as Problem A (n=15) but don’t require connectivity—no proof required.
Answer: 98. (As in Problems A and B, this is for grids defined by Set 6, those with only 180 rotation symmetry. However, for grids defined by Set 2 and dually by Set 4 the answer is 100 and that according to Ferland and Pratt is the overall maximum.)
Why are CWP and this question called puzzles and A to D problems? This question has no definitive right or wrong answer.
My Answer: It seems desirable to distinguish between questions for which there may be some ambiguity in an answer, even when an answer is presented and questions for which an answer is unambiguous. Since we have two words “puzzles” and “problems” which mean roughly the same thing, why not use one word for one type of question and the other word for the other type? And since “puzzles” is strongly connected to the class of questions with ambiguous answers by its usage with crosswords, and “problems” to the other class by its usage with mathematics, that is my recommendation.
This was a tough problem set, harder than it should have been; there were only eight stalwart solvers. For each solver, the problems solved are shown in parentheses. Robert Bartholomew (A,B); Bob Byrne (A, C with Set 1: 95); Bill Feldman (A, B, C with Set 1: 96); Rui Guo (A,D, C with Set 8: 92); Clive Keatinge (A, B); David Promislow (A,B,D); Naom Segal (B); Al Spooner (B, C with Set 5: 86).