Saturday, June 27, 2015

The Perimeter Puzzle Under an Additional Constraint

A reader sent this configuration for the perimeter puzzle:

This suggests a new version of the puzzle:

Maximize perimeter among configurations like the one above, namely: (1) The boundary doesn't self-intersect; and (2) there are no "holes."

(Requirement (1) is saying that we don't allow "kitty-corner" shaded squares, that is, two shaded squares that touch corners, with the other two squares meeting at that corner being unshaded.)

I tried my hand at this and was unable to improve on the reader's example, which has perimeter 40. Here are my best attempts, which also have perimeter 40:

Is 40 maximal? Well, it is not hard to see that a tame shape cannot have perimeter greater than 46. To see this, consider that if any of the 8 unshaded squares had 4 shaded neighbors, then because of the no-kitty-corner constraint, that unshaded square would have to be fully surrounded by shaded squares, that is, the unshaded square would be a hole. But by assumption there are no holes, hence each unshaded square must have 3 or fewer shaded neighbors. Moreover, at least one unshaded square must touch the boundary of the grid, or else the 8 unshaded squares would form a great big hole. So it follows by algorithm (1)–(3) of my last post that the perimeter must be less than or equal to \(8\times 3 + 19 + 4 = 47\). But the perimeter has to be even, so the perimeter must be less than or equal to 46.

I don't actually think there is a tame configuration with perimeter 46—the greatrest value attained seems to be 40.

For what it's worth, I wrote some computer code to identify the tame configurations among the 30 million or so in the full space. (It might have been easier to chuck my old work and build up the tame configurations from scratch, but I had a body of commands sitting there, so....) First I culled the kitty-corner cases, and then because it was easy I culled the single-square holes. For the remaining configurations, I wrote a function to convert the boundary into a graph-theoretic object, and then I used a built-in function to determine whether that graph was a single connected component. A total of 1,512,395 configurations survived the sorting process. Of these, 143,920 had perimeter 40, and none had perimeter greater than 40. So if my code does what it's supposed to do, then this is the maximum value.

Just for interest, here are some randomly chosen maximizers from the computer run:

Friday, June 26, 2015

Reading Judicial Opinions

Judicial opinions, while densely written, can be fascinating to read—even inspiring, because of the exemplars they offer of rigorous textual analysis, fair and disciplined debate, and rational reasoning applied to human affairs. Judges' opinons can also impress with their rhetoric and style. As a non-expert, I usually have to skip over some of the jargon and procedural matters, but after reading enough of these things, you even begin to understand how some of that stuff works.

Here are some notable examples of the genre.

1) No fireworks, but solid: the May 7, 2015 decision that struck down the bulk data collection component of the NSA's domestic spying program. Most of the public debate about the program revolves around constitutional rights, like freedom from unreasonable searches. However, the court case was decided purely on the basis of statutory interpretation. Contrary to the government's claims, the judge agreed with the ACLU that the Patriot Act as written had never authorized the bulk data collection program in the first place. I thought the decision paid very careful attention to the text under dispute. I also admired the way the judge was able to represent the claims of the losing party and give them their due.

2) The challenger: the November 6, 2014 decision that found same-sex marriage bans constitutional, teeing up the June 26, 2015 Supreme Court decision that ultimately ruled otherwise. Judge Sutton's decision was a very sophisticated piece of writing. Knowing that his decision would immediately undergo Supreme Court review, the author threw everything at the wall so that he could attract as many of the justices' votes as possible. The Supreme Court ruled 5-4 against him, but it seems to me that he earned at least the Chief Justice's dissenting vote with his argument that this decision should lie with the people rather than with the courts. Sutton also made the best case one could possibly make for the rational basis of same-sex marriage bans. I thought the greatest weakness of Sutton's decision was that it paid only light attention to the actual injuries of the plaintiffs seeking the relief of his court. Any court case is foremost about the specific conflict occurring among the particular individuals named in the suit; by turning the decision back to "the people," Judge Sutton largely waved away the injuries of the specific people who were seeking redress in his courtroom.

3) The interpreter: Chief Justice John Roberts's majority opinion in the June 25, 2015 decision upholding tax credits in Federally created health care exchanges. This was another statutory interpretation case. The first key to the decision is Roberts's conclusion that the sentence under dispute is actually ambiguous. The second key is the conclusion that the court cannot defer to the Executive branch for resolving the ambiguity, because the ambiguity does not concern a mere detail or technicality but rather the main thrust of the legislation at hand. The decision is interesting because it rejects not only the stunted, literalist textualism of Scalia but also the "tea leaves" approach of divining legislative intent. The key word in the decision is "plan." Roberts bases his decision not on a mysterious divination of legislative intent, but on a simple apperception of the legislative plan, as expressed plainly through a reading of the text as a whole. (More on this angle here.) Finally, I thought this decision was remarkable for the deceptively breezy style of its writing—the work, it seems to me, of both a talented writer and a formidable intellect.

4) Roberts's dissent in the June 26 Supreme Court decision ruling that same-sex marriage bans are unconstitutional. Roberts adopts Sutton's position on the role of the judiciary and combines it with a vehement concern about the implications of Kennedy's new jurisprudence of "dignity." Roberts makes a strong case. He remedies the major weakness of Sutton's decision by stressing the harms to the plaintiffs, and I also thought he put the best possible face on "the argument from definition" (the view, more or less, that the plaintiffs are asking for something that is, if not impossible for them to have, nevertheless reasonable for them not to have, because marriage means a union of a man and a woman). Roberts notes that had the case been about the denial of tangible benefits to same-sex couples, he might have ruled in the plaintiffs' favor; instead, the plaintiffs sought a right that he cannot find in the Constitution. Roberts's real concern seems to be about the expansiveness of the concept of dignity as a constitutional right. Law professor Jeffrey Rosen also highlighted this issue after hearing the oral arguments in the case.

5) The majority decision itself. Stylistically, I have to agree with Scalia that the prose is often overwrought (but occasionally magnificent). The logic of the decision seems to be that if you look carefully at Supreme Court precedents about marriage, you can discover four things that make marriage a fundamental right under the Constitution. Then, you can observe that none of those things are special to opposite-sex unions. Therefore, it is reasonable to conclude that the fundamental right to marriage as accreted through Supreme Court jurisprudence actually includes, in fact substantively always has included, access by couples of the same sex. This decision was Kennedy's life work as a jurist. As Scalia famously predicted, this decision flows from his earlier decisions in Lawrence, Romer, and Windsor, which built the edifice of his concept of dignity in the Constitution.

One last comment on today's decision. I think that two factors made this result inevitable—if not today, then soon enough. One is that Scalia's concept of homosexual acts lost out to Kennedy's concept of homosexual persons. The state can attack actions in law, but the state can't attack persons. Second, although the defenders of same-sex marriage bans did their rhetorical best, once you take away religious justifications for these bans, you aren't left with enough reasoning firepower to win the day. Today's decision is going to be painful for many precisely because it underscores that we are a nation of secular laws, not religious doctrine. Roberts even perceived a subtle hostility to religion in Kennedy's decision, noting that Kennedy left room for religious people to "advocate" and "teach" their views, but said nothing about "exercising" them, which is the First Amendment's verb of choice. Presumably, Kennedy's reply to this would be just as strongly grounded in the Constitution: the exercise of religion is for citizens, not for the government.

The Supreme Court, August 2014

Tuesday, June 23, 2015

Solution to Perimeter Puzzle

On a six-by-six grid, shade 28 squares so that the perimeter of the resulting shape is (a) as small as possible (b) as large as possible.

This puzzle was my Father's Day indulgence. To maximize the perimeter, I intuitively created a "checkerboard" design inside the grid:

The perimeter of this shape is 56—and in fact, 56 is the greatest possible perimeter. To see this, consider any shading of 28 squares whatsoever, leaving 8 squares unshaded. One way to compute the perimeter of the resulting shape is as follows:

(1) For each unshaded square, count +1 for each neighbor that is shaded.

(2) For each shaded square on the boundary of the grid, count +1.

(3) For each shaded corner, count an additional +1.

The total for (1) must be less than or equal to 8 \(\times\) 4 = 32, because there are 8 unshaded squares and an unshaded square can have at most 4 shaded neighbors. Meanwhile, there are 20 boundary squares, so the total for (2) must be less than or equal to 20. And there are 4 corners, so the total for (3) must be less than or equal to 4. Hence, the total perimeter must be less than or equal to 32 + 20 + 4 = 56. QED

The smallest possible perimeter is 22. I found this value intuitively by creating a 5-by-5 block with 3 squares left over. I couldn't think of an optimality proof, so I wrote a computer program to analyze all 30,260,340 possible ways to shade 28 squares on a six-by-six grid. Sure enough, the smallest possible perimeter is 22, attained in the following distinct ways:

After that, I thought some more about how to find the minimum perimeter in some other way besides brute force. You can convert the problem to a quadratic integer program by assigning a variable \(x_i = 0, 1\) to each square and implementing the perimeter computation using algorithm (1)-(3) above. But I wanted an insightful approach. 

It seemed that what I wanted to know was the minimum perimeter of an orthogonal polygon of given area. Googling this question got me nowhere, however.

So by generalizing my simple-minded \(28 = 5\times 5 + 3\) approach, I conjectured that the minimum perimeter would be \(2({\rm Fl}(\sqrt{n})+n\,{\rm div}\,{\rm Fl}(\sqrt{n})+1^*)\), where \(n\) is the number of squares in the polygon, \({\rm Fl}(\cdot)\) is the Floor function, and the asterisk on the 1 means that you only add the 1 if \({\rm Fl}(\sqrt{n}) (n\,{\rm div}\,{\rm Fl}(\sqrt{n})) < n\). This conjecture just says that you can find the minimal perimeter by arranging the shaded squares in a nice rectangular shape, with the extra tiles stacked nicely on the side.

For \(n=1,2,3,\dots\) you get the sequence 4, 6, 8, 8, 10, 10, 12, 12, 12, 14, 14, 14, ....  I figured it couldn't hurt to search for this sequence in the Online Encylopedia of Integer Sequences. And what do you know? It was the minimal perimeter sequence that I was looking for!

The citation given for this result is Harary and Harborth (1976), "Extremal Animals," Journal of Combinatorics, Information & System Sciences 1(1), pp. 1–8. I don't find a PDF freely available online, but the second citation can be downloaded here. A simpler formula for the sequence is \(2{\rm Cl}(2\sqrt{n})\), where \({\rm Cl}(\cdot)\) denotes the Ceiling function. Harary and Harborth found this result by building an optimal configuration in a spiral pattern.

I see now that I would have had better luck at the outset if I'd googled "minimal perimeter polyomino." The first result for that search is this 2005 paper by Kurz, which extends Harary and Harborth by counting the number of optimal configurations. The formula for the number of optimal configurations is pretty complicated, but I think that for the case \(n=28\) there are supposed to be 6 distinct configurations with minimal perimeter 22. However, I only saw 5 distinct optimal configurations during my exhaustive search. I assume the discrepancy arises from the fact that Kurz will have counted the 4-by-7 polyomino, which has perimeter 22 (and hence is optimal too) but which doesn't fit inside the six-by-six grid that constrained our puzzle.

Just for fun, I'll end with a histogram showing how often each perimeter value occurs among the 30,260,340 possible configurations:

The most common perimeter value is 40, attained for example by this configuration:

Postscript: The Online Encyclopedia of Integer Sequences was recently the subject of a newspaper item in The Guardian; read it here. OEIS is supported by donations—having used the tool to such good advantage here, I have donated to them today.

Sunday, June 21, 2015

Perimeter Puzzle

On a six-by-six grid, shade 28 squares so that the perimeter of the resulting shape is (a) as small as possible (b) as large as possible.

Friday, June 19, 2015

Begins With (But Isn't) - Some Answers

1) Think of a word that begins with SUN, even though the word has nothing to do with the Sun in either its meaning or its history.


2) Think of a word that begins with BAD, even though the word has nothing to do with badness in either its meaning or its history.


3) (Challenge) Think of a word that begins with UP, even though the word has nothing to do with the adverb up in either its meaning or its history.


Saturday, June 13, 2015

Begins With (But Isn't)

1) Think of a word that begins with SUN, even though the word has nothing to do with the Sun in either its meaning or its history.

2) Think of a word that begins with BAD, even though the word has nothing to do with badness in either its meaning or its history.

3) (Challenge) Think of a word that begins with UP, even though the word has nothing to do with the adverb up in either its meaning or its history.

Saturday, June 6, 2015

Pronoun Trouble

I don't often write about current events, but since I've been doing grammar posts lately, I thought I'd write about Caitlyn Jenner and the said-he/said-she controversy. What moved me to write was this sentence from an a recent article by Emma Green in The Atlantic:
Calling Jenner "he" versus "she" has important implications for the speaker's understanding of gender identity.
Does calling Jenner "he" versus "she" tell us something about the speaker's understanding of gender identity? It might, or it might not. Myself, I would never address Caitlyn Jenner in anything other than the way she wants to be addressed, but that doesn't have anything to do with my understanding of gender identity. It just has to do with my understanding of manners. If you're introduced to somebody at a party and the person says "Call me Caitlyn," wouldn't it be quite rude of you not to do that? ("Hold on now! I know who you really are, and I'm going to call you...Bruce!") What kind of an asshole would do something like that?

Well, this guy, for one, although I did see that he later apologized.

Much of Twitter might not exist if more people had had better upbringing. I don't think anybody in my family would ever behave the way that guy did, because our mother raised us better than that. She might or might not have celebrated sex-change operations altogether (I never asked her about it), but as a well raised Southerner, she probably would have shaken Caitlyn Jenner's hand at a party and said "I'm pleased to meet you, Caitlyn."

Years ago when I was studying at the Mathematical Institute in Oxford, there was a male researcher who dressed in women's clothes. Or at any rate, I judged it likely that he was male, and people referred to him by a masculine name. I also judged it likely that he was wearing women's clothes, however questionable may have been his habit of wearing thick white socks with open-toed pumps. Anyway, nobody cared. Almost a hundred percent of all mental activity occuring at the Institute was directed toward proving theorems. Maybe Twitter is what it is in part because the effort required to send a Tweet is too small to interfere with the doing of more important things.