Archive:
Subtopics:
Comments disabled |
Fri, 11 Oct 2019 In a recent article about fair cake division, I said:
I got to wondering what that would look like, and the answer is, not very interesting. A regular 17-gon is pretty close to a circle, and the 23 pieces, which are quite narrow, look very much like equal wedges of a circle: This is generally true, and it becomes more nearly so both as the number of sides of the polygon increases (it becomes more nearly circular) and as the number of pieces increases (the very small amount of perimeter included in each piece is not very different from a short circular arc). Recall my observation from last time that even in the nearly extreme case of , the central angles deviate from equality by only a few percent. Of particular interest to me is this series of demonstrations of how to cut four pieces from a cake with an odd number of sides: I think this shows that the whole question is a little bit silly: if you just cut the cake into equiangular wedges, the resulting slices are very close in volume and in frosting. If the nearly-horizontal cuts in the pentagon above had been perfectly straight and along the !!y!!-axis, they would have intersected the pentagon only 3% of a radius-length lower than they should have. Some of the simpler divisions of simpler cakes are interesting. A solution to the original problem (of dividing a square cake into nine pieces) is highlighted. The method as given works regardless of where you make the first cut. But the results do not look very different in any case: The original SVG files are also available, as is the program that wrote them. [Other articles in category /math] permanent link Thu, 10 Oct 2019
Incenters of chocolate-iced cakes
A MathOverflow post asks:
Okay, this is obvious.
This one stumped me; the best I could do was to cut the cake into 27 slabs, each !!\frac{10}3×10×10!! cm, and each with between 1 and 5 units of icing. Then we can give three slabs to each grandkid, taking care that each kid's slabs have a total of 7 units of icing. This seems like it might work for an actual cake, but I suspected that it wasn't the solution that was wanted, because the problem seems like a geometry problem and my solution is essentially combinatorial. Indeed, there is a geometric solution, which is more interesting, and which cuts the cake into only 9 pieces. I eventually gave up and looked at the answer, which I will discuss below. Sometimes when I give up I feel that if I had had thought a little harder or given up a little later, I would have gotten the answer, but not this time. It depends on an elementary property of squares that I had been completely unaware of. This is your last chance to avoid spoilers. The solution given is this: Divide the perimeter of the square cake into 9 equal-length segments, each of length !!\frac{120}{9}!! cm. Some of these will be straight and others may have right angles; it does not matter. Cut from the center of the cake to the endpoints of these segments; the resulting pieces will satisfy the requirements. “Wat.” I said. “If the perimeter lengths are equal, then the areas are equal? How can that be?” This is obviously true for two pieces; if you cut the square from the center into two pieces into two parts that divide the perimeter equally, then of course they are the same size and shape. But surely that is not the case for three pieces? I could not believe it until I got home and drew some pictures on graph paper. Here Grandma has cut her cake into three pieces in the prescribed way: The three pieces are not the same shape! But each one contains one-third of the square's outer perimeter, and each has an area of 12 square units. (Note, by the way, that although the central angles may appear equal, they are not; the blue one is around 126.9° and the pink and green ones are only 116.6°.) And indeed, any piece cut by Grandma from the center that includes one-third of the square's perimeter will have an area of one-third of the whole square: The proof that this works is actually quite easy. Consider a triangle !!OAB!! where !!O!! is the center of the square and !!A!! and !!B!! are points on one of the square's edges. The triangle's area is half its height times its base. The base is of course the length of the segment !!AB!!, and the height is the length of the perpendicular from !!O!! to the edge of the square. So for any such triangle, its area is proportional to the length of !!AB!!. No two of the five triangles below are congruent, but each has the same base and height, and so each has the same area. Since the center of the square is the same distance from each of the four edges, the same is true for any two triangles, regardless of which edge they arise from: the area of each triangle is proportional to the length of the square's perimeter at its base. Any piece Grandma cuts in this way, from the center of the cake to the edge, is a disjoint union of triangular pieces of this type, so the total area of any such piece is also proportional to the length of the square's perimeter that it includes. That's the crucial property of the square that I had not known before: if you make cuts from the center of a square, the area of the piece you get is proportional to the length of the perimeter that it contains. Awesome! Here Grandma has used the same method to cut a pair of square cakes into ten equal-sized pieces that all the have same amount of icing. The crucial property here was that the square’s center is the same distance from each of its four edges. This is really obvious, but not every polygon has an analogous point. The center of a regular polygon always has this property, and every triangle has a unique point, called its incenter, which enjoys this property. So Grandma can use the same method to divide a triangular cake into 7 equally-iced equal pieces, if she can find its incenter, or to divide a regular 17-gonal cake into 23 equally-iced equal pieces. Not every polygon does have an incenter, though. Rhombuses and kites always do, but rectangles do not, except when they are square. If Grandma tries this method with a rectangular sheet cake, someone will get shortchanged. I learned today that polygons that have incenters are known as tangential polygons. They are the only polygons in which can one inscribe a single circle that is tangent to every side of the polygon. This property is easy to detect: these are exactly the polygons in which all the angle bisectors meet at a single point. Grandma should be able to fairly divide the cake and icing for any tangential polygon. I have probably thought about this before, perhaps in high-school geometry but perhaps not since. Suppose you have two lines, !!m!! and !!n!!, that cross at an acute angle at !!P!!, and you consider the set of points that are equidistant from both !!m!! and !!n!!. Let !!\ell!! be a line through !!P!! which bisects the angle between !!m!! and !!n!!; clearly any point on !!\ell!! will be equidistant from !!m!! and !!n!! by a straightforward argument involving congruent triangles. Now consider a triangle !!△ABC!!. Let !!P!! be the intersection of the angle bisectors of angles !!∠ A!! and !!∠ B!!. !!P!! is the same distance from both !!AB!! and !!AC!! because it is on the angle bisector of !!∠ A!!, and similarly it is the same distance from both !!AB!! and !!BC!! because it is on the angle bisector of !!∠ B!!. So therefore !!P!! is the same distance from both !!AC!! and !!BC!! and it must be on the angle bisector of angle !!∠ C!! also. We have just shown that a triangle's three angle bisectors are concurrent! I knew this before, but I don't think I knew a proof. [ Addendum 20191011: Many illustrated examples. ] [Other articles in category /math] permanent link Fri, 04 Oct 2019
Addenda to recent articles 201910
Several people have written in with helpful remarks about recent posts:
Thanks to everyone who wrote in, even people I forgot to mention above, and even to the Twitter person who didn't actually write in. [Other articles in category /addenda] permanent link Thu, 03 Oct 2019I recently mentioned a citation listing on one of the pages of the United States Code at LII. It said:
My comment was “Whew”. But this wouldn't have been so awful if LII had made even a minimal effort to clean it up:
That's the result of (I wonder if that long citation at the end is actually two citations.) [Other articles in category /IT] permanent link
The pain of tracking down changes in U.S. law
Last month when I was researching my article about the free coffee provision in U.S. federal highway law, I spent a great deal of time writing this fragment: I knew that the provision was in 23 USC §131, but I should explain what this means. The body of U.S. statutory law can be considered a single giant document, which is "codified" as the United States Code, or USC for short. USC is divided into fifty or sixty “titles” or subject areas, of which the relevant one here, title 23, concerns “Highways”. The titles are then divided into sections (the free coffee is in section 131), paragraphs, sub-paragraphs, and so on, each with an identifying letter. The free coffee is 23 USC §131 (c)(5). But this didn't tell me when the coffee exception was introduced or in what legislation. Most of Title 23 dates from 1958, but the coffee sign exception was added later. When Congress amends a law, they do it by specifying a patch to the existing code. My use of the programmer jargon term “patch” here is not an analogy. The portion of the Federal-Aid Highway Act of 1978 that enacted the “free coffee” exception reads as follows:
(The “[…]” is my elision. The Act includes the complete text that was to be inserted.) The act is not phrased as a high-level functional description, such as “extend the list of exceptions to include: ... ”. It says to replace the text ‘and (4)’ with the text ‘(4)’; then replace the period with a comma; then …”, just as if Congress were preparing a patch in a version control system. Unfortunately, the lack of an actual version control system makes it quite hard to find out when any particular change was introduced. The code page I read is provided by the Legal Information Institute at Cornell University. At the bottom of the page, there is a listing of the changes that went into this particular section:
Whew. Each of these is a citation of a particular Act of Congress. For example, the first one
refers to “Public law 85–767”, the 767th law enacted by the 85th Congress, which met during the Eisenhower administration, from 1957–1959. The U.S. Congress has a useful web site that contains a list of all the public laws, with links — but it only goes back to the 93rd Congress of 1973–1974. And anyway, just knowing that it is Public law 85–767 is not (or was not formerly) enough to tell you how to look up its text. The laws must be published somewhere before they are codified, and scans of these publications, the United States Statutes at Large, are online back to the 82nd Congress. That is what the “72 Stat. 904” means: the publication was in volume 72 of the Statutes at Large, page 904. This citation style was obviously designed at a time when the best (or only) way to find the statute was to go down to the library and pull volume 72 off the shelf. It is well-deisgned for that purpose. Now, not so much. Here's a screengrab of the relevant portion of the relevant part of the 1978 act: The citation for this was:
(Note that “title I, §§ 121, 122” here refers to the sections of the act itself, not the section of the US Code that was being amended; that was title 23, §131, remember.) To track this down, I had no choice but to grovel over each of the links to the Statutes at Large, download each scan, and search over each one looking for the coffee provision. I kept written notes so that I wouldn't mix up the congressional term numbers with the Statutes volume numbers. It ought to be possible, at least in principle, to put the entire U.S. Code into a version control system, with each Act of Congress represented as one or more commits, maybe as a merged topic branch. The commit message could contain the citation, something like this:
Or maybe the titles would be directories and the sections would be numbered files in those directories. Whatever. If this existed, I would be able to do something like:
and the Act that I wanted would pop right out. Preparing a version history of the United States Code would be a dauntingly large undertaking, but gosh, so useful. A good VCS enables you to answer questions that you previously wouldn't have even thought of asking. This article started as a lament about how hard it was for me to track down the provenance of the coffee exception. But it occurs to me that this is the response of someone who has been spoiled by plenty. A generation ago it would have been unthinkable for me even to try to track this down. I would have had to start by reading a book about legal citations and learning what “79 Stat. 1028” meant, instead of just picking it up on the fly. Then I would have had to locate a library with a set of the Statutes at Large and travel to it. And here I am complaining about how I had to click 18 links and do an (automated!) text search on 18 short, relevant excerpts of the Statutes at Large, all while sitting in my chair. My kids can't quite process the fact that in my childhood, you simply didn't know what the law was and you had no good way to find out. You could go down the the library, take the pertinent volumes of the USC off the shelf, and hope you had looked in all the appropriate places for the relevant statutes, but you could never be sure you hadn't overlooked something. OK, well, you still can't be sure, but now you can do keyword search, and you can at least read what it does say without having to get on a train. Truly, we live in an age of marvels. [ Addendum 20191004: More about this ] [Other articles in category /law] permanent link Wed, 02 Oct 2019Last month I mentioned that, while federal law generally prohibits signs and billboards about signs within ⅛ mile of a federal highway, signs offering free coffee are allowed. Vilhelm Sjöberg brought to my attention the 2015 U.S. Supreme Court decision in Reed v. Town of Gilbert. Under the Reed logic, the exemption for free coffee may actually be unconsitutional. The majority's opinion states, in part:
The court concluded that the Sign Code (of the town of Gilbert, AZ) was therefore subject to the very restrictive standard of strict scrutiny, which required that it be struck down unless the government could demonstrate both that it was necessary to a “compelling state interest” and that it be “narrowly tailored” to achieving that interest. The Gilbert Sign Code did not survive this analysis. Although the court unanimously struck down the Sign Code, a concurrence, written by Justice Kagan and joined by Ginsburg and Breyer, faulted the majority's reasoning:
Kagan specifically mentioned the “free coffee” exception as being one of many that would be imperiled by the court's reasoning in this case. Thanks very much to M. Sjöberg for pointing this out. [Other articles in category /law] permanent link Tue, 01 Oct 2019
How do I keep type constructors from overrunning my Haskell program?
Here's a little function I wrote over the weekend as part of a suite for investigating Yahtzee:
I don't claim this code is any good; I was just hacking around exploring the problem space. But it does do what I wanted. The
which means that we have two rolls remaining in the round, and the most recent roll of the five dice showed 6, 4, 4, 3, and 1, respectively. It also takes a choice of which dice to keep: The list
means to keep the 4's and reroll the 6, the 3, and the 1.
The
This function was not hard to write and it did work adequately. But I wasn't satisfied. What if I have some unrelated integer list
and I pass it to a function that is expecting a
The declared type of
But now I need to rewrite
This still compiles and it still produces the results I want. And it
has the type checking I want. I can no longer pass a raw integer
list, or any other isomorphic type, to I could rename
And I can do something similar on the output side also:
This is not unreasonably longer or more cluttered than the original
code. It does forgo type checking inside of Is this considered The Thing To Do? And if so, where could I have learned this, so that I wouldn't have had to invent it? (Or, if not, where could I have learned whatever is The Thing To Do?) I find most Haskell instruction on the Internet to be either too elementary
or too advanced
with very little practical advice about how to write, you know, an actual program. Where can I find some? [Other articles in category /prog/haskell] permanent link Fri, 27 Sep 2019
Typographical mysteries of Yeadon
Here are some pictures I took of the firehouse in Yeadon, PA. Every time I drive past this, I wonder: is that the original letter “O”? Or was there originally a narrow “O” that was lost or damaged, and which couldn't be replaced with a matching letter? Here's the Google Street View version, from November 2016. The letters are painted green, but the “O” is still the circular one. [ Addendum 20191004: More about this ] [Other articles in category /IT/typo] permanent link Wed, 25 Sep 2019A couple of months ago I asked why the disco ball had to wait until the 20th century:
I think the lighting issue is the show-stopper. To make good use of a disco ball you really do need a dark room and a spotlight. You can get reflections by hanging the ball under an orbiculum, but then the room will be lit by the orbiculum, and the reflections will be pale and washed out, at best. Long ago I attended a series of lectures by Atsushi Akera on the hidden prerequisites for technological adoption. For example, you can't have practical skyscrapers without also inventing elevators, and you can't have practical automobiles without also inventing windshield wipers. (And windshields. And tires. And … ) This is an amusing example of the same sort. You can't have practical disco balls without also inventing spotlights. But now I kinda wonder about the possibility of wowing theatre-goers in 1850 with a disco ball, lit by a sort of large hooded lantern containing a limelight and a (lighthouse-style) Fresnel lens. [ Addendum: Apparently, nobody but me has ever used the word “orbiculum”. I don't know how I started using it, but it seemsthat the correct word for what I meant is oculus. ] [Other articles in category /tech] permanent link Yesterday Katara asked me about impeachment, and in mentioning the impeachment of Andrew Johnson, I realized that I didn't know who would have assumed the presidency, had Johnson been convicted. Who was Johnson's vice president? Well, I couldn't remember because he didn't have one. Until the ratification of the 25th Amendment in 1967, there was no provision for the replacement of a vice-president except through a normal election. Under the Presidential Succession Act of 1792, next in line was the President Pro Tempore of the Senate. This is a largely ceremonial position, filled by a senator, and elected by the Senate. The President Pro Tempore in 1868 was Benjamin Wade, senator from Ohio. Wade, as a senator, would be voting on Johnson's conviction and therefore had an enormous conflict of interest: if Johnson was removed, Wade would assume the presidency. There were calls for Wade to abstain from voting. Which he did. Not! Ha ha, of course he didn't. He voted to convict. The conviction, famously, fell short by one vote: it went 35–19 in favor of conviction, but they needed 36 votes to convict. Suppose it had gone 36-18, with Wade's vote being the 36th, and Wade taking over the presidency as a result? Wikipedia claims (with plausible citation) that at Wade told at least one other senator what cabinet position he could expect to receive in exchange for his vote to convict.
[ Maybe I should also mention that many sources suggest that Johnson would have been removed had his successor been someone less divisive than Wade. ] [Other articles in category /politics] permanent link Wed, 18 Sep 2019Suppose you have a bottle that contains !!N!! whole pills. Each day you select a pill at random from the bottle. If it is a whole pill you eat half and put the other half back in the bottle. If it is a half pill, you eat it. How many half-pills can you expect to have in the bottle the day after you break the last whole pill? Let's write !!E(N)!! for the expected number of half-pills. It's easily seen that !!E(N) = 0, 1, \frac32!! for !!N=0,1,2!!, and it's not hard to calculate that !!E(3) = \frac{11}{6}!!. For larger !!N!! it's easy to use Monte Carlo simulation, and find that !!E(30)!! is almost exactly !!4!!. But it's also easy to use dynamic programming and compute that $$E(30) = \frac{9304682830147}{2329089562800}$$ exactly, which is a bit less than 4, only !!3.994987!!. Similarly, the dynamic programming approach tells us that $$E(100) = \frac{14466636279520351160221518043104131447711}{2788815009188499086581352357412492142272}$$ which is about !!5.187!!. (I hate the term “dynamic programming”. It sounds so cool, but then you find out that all it means is “I memoized the results in a table”. Ho hum.) As you'd expect for a distribution with a small mean, you're much more likely to end with a small number of half-pills than a large number. In this graph, the red line shows the probability of ending with various numbers of half-pills for an initial bottle of 100 whole pills; the blue line for an initial bottle of 30 whole pills, and the orange line for an initial bottle of 5 whole pills. The data were generated by this program. The !!E!! function appears to increase approximately logarithmically. It first exceeds !!2!! at !!N=4!!, !!3!! at !!N=11!!, !!4!! at !!N=31!!, and !!5!! at !!N=83!!. The successive ratios of these !!N!!-values are !!2.75, 2.81,!! and !!2.68!!. So we might guess that !!E(N)!! first exceeds 6 around !!N=228!! or so, and indeed !!E(226) < 6 < E(227)!!. So based on purely empirical considerations, we might guess that $$E(N) \approx \frac{\log{\frac{15}{22}N}}{\log 2.75}.$$ (The !!\frac{15}{22}!! is a fudge factor to get the curves to line up properly.) I don't have any theoretical justification for this, but I think it might be possible to get a bound. I don't think modeling this as a Markov process would work well. There are too many states, and it is not ergodic. [ Addendum 20190919: Ben Handley informs me that !!E(n)!! is simply the harmonic numbers, !!E(n) = \sum_1^n \frac1n!!. I feel a little foolish that I did not notice that the first four terms matched. The appearance of !!E(3)=\frac{11}6!! should have tipped me off. Thank you, M. Handley. ] [ Addendum 20190920: I was so fried when I wrote this that I also didn't notice that the denominator I guessed, !!2.75!!, is almost exactly !!e!!. (The correct value is !!e!!.) I also suspect that the !!\frac{15}{22}!! is just plain wrong, and ought to be !!e^\gamma!! or something like that, but I need to take a closer look. ] [ Addendum 20191004: More about this ] [Other articles in category /math] permanent link Tue, 17 Sep 2019Today it occurred to me that in the many comedy duos that feature a “straight man” and a “comedian”, the straight man is invariably named first. The central example, of course, is Abbott and Costello. But we also have:
and this even extends to entirely fictitious pairs such as Jeeves and Wooster, Harold and Kumar, or Sam and Max, Freelance Police. Also, if you are a mathematician, Smothers and Smothers. This is why people hate mathematicians. I did Google search for "Kermit and Fozzie" (hits outnumber "Fozzie and Kermit" by around three-to-one) and "Kermit and Miss Piggy" (hits outnumber "Miss Piggy and Kermit", although only by about 60%.) Wikipedia says this is no accident!
But my co-worker Jeff Culverhouse found a counterexample: Silent Bob is certainly the straight man of Jay and Silent Bob. Wikipedia also has a list of American Comedy Duos. Not all of them follow the straight man / comedian pattern, and I don't recognize many of those that do. More research is needed. [ Addendum: I wanted to find a gender-neutral term for "straight man", but failed. ] [Other articles in category /misc] permanent link |