[math-fun] More random polygons: fun puzzle
Given two parallelograms A,B in the plane and a translation vector v, let P(v) be the intersection of A+v with B. If we choose a random v such that P(v) is nonempty, how many sides on average do we expect P(v) to have? The set of such vectors v is a compact subset of R^2, so it's clear what probability measure to use: ordinary Lebesgue measure, rescaled. There is a nice answer to my question and at least one nice proof. I'll be curious to see proofs different from the one I found. I'm happy to answer requests for clarification, but no spoilers till Sunday, please. Jim Propp
So far, only Veit Elser has solved the puzzle (or at least he's the only one who sent me a solution), so let me provide a few hints. But first, an obvious remark: if the answer is independent of A and B (as the wording of the puzzle implies), it can only be 4, since that's what you get when the sides of A are parallel to the respective sides of B (e.g., when A and B are rectangles whose sides are horizontal and vertical). But it's a priori not at all obvious that the answer should be the same for all pairs of parallelograms. I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelograms-puzzle. George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a nonempty translate of itself, the expected number of sides is exactly 5. Anyway, two days have passed since I posted the puzzle, so I think it's appropriate to have an unbridled conversation, with or without spoilers. Jim Propp On Sat, Nov 4, 2017 at 12:32 PM, James Propp <jamespropp@gmail.com> wrote:
Given two parallelograms A,B in the plane and a translation vector v, let P(v) be the intersection of A+v with B. If we choose a random v such that P(v) is nonempty, how many sides on average do we expect P(v) to have?
The set of such vectors v is a compact subset of R^2, so it's clear what probability measure to use: ordinary Lebesgue measure, rescaled.
There is a nice answer to my question and at least one nice proof. I'll be curious to see proofs different from the one I found.
I'm happy to answer requests for clarification, but no spoilers till Sunday, please.
Jim Propp
Here's Veit's solution (SPOILER): ^L ^L ^L (Remember the days when we'd use "^L" in situations like this? Are any of you using mail-readers that force you to hit the space-bar when it encounters this character?) ^L ^L ^L Veit wrote: I get 4. It doesn’t matter if you average over v, or v+a+b, where a are samples of the discrete lattice generated by A inside some large region R, and b are samples of the discrete lattice generated by B, also inside R. You can interpret this enlarged average in terms of a double covering of the plane, inside V, by the two parallelogram tilings. Every polygon formed by the edges in this “double tiling” in fact corresponds to an instance of one of your intersections. To answer the question all we want to know is the average number of sides per polygon in the double tiling. We forget about vertices of one tiling being coincident with vertices of the other because that has zero measure. That leaves only vertices of degree 4. Now we look at the polygons formed by the double tiling as a graph and use Euler. We make estimates inside a large R and therefore ignore boundary corrections. Let the number of vertices inside R be V. Because the degrees are all 4, the number of edges is E=2V.
From Euler, applied to a planar graph, we get F=E-V=V (ignoring boundary corrections and the Euler characteristic). The average number of polygon sides is 2E/F=4V/V=4.
There's a way to avoid the "boundary corrections from large regions are small" dodge. Specifically, one can show that if you superimpose the lattices associated with A and B, then as long as everything is generic (with no triple-intersections), each copy of A is dissected (by the B-lattice) into a finite number of polygons whose average "sidedness" is exactly 4, and vice versa. One can prove this by induction (adding one cut-line at a time), or prove it in one gulp by an appeal to Euler's formula V-E+F=2. This hinges on the assumption that each internal vertex in the dissection has degree 4, each vertex on the edge of the copy of A has degree 3, and the corners of the copy of A have degree 2. I'll provide more details if anyone wants them. Jim On Mon, Nov 6, 2017 at 9:13 AM, James Propp <jamespropp@gmail.com> wrote:
So far, only Veit Elser has solved the puzzle (or at least he's the only one who sent me a solution), so let me provide a few hints. But first, an obvious remark: if the answer is independent of A and B (as the wording of the puzzle implies), it can only be 4, since that's what you get when the sides of A are parallel to the respective sides of B (e.g., when A and B are rectangles whose sides are horizontal and vertical). But it's a priori not at all obvious that the answer should be the same for all pairs of parallelograms.
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting- parallelograms-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a nonempty translate of itself, the expected number of sides is exactly 5.
Anyway, two days have passed since I posted the puzzle, so I think it's appropriate to have an unbridled conversation, with or without spoilers.
Jim Propp
On Sat, Nov 4, 2017 at 12:32 PM, James Propp <jamespropp@gmail.com> wrote:
Given two parallelograms A,B in the plane and a translation vector v, let P(v) be the intersection of A+v with B. If we choose a random v such that P(v) is nonempty, how many sides on average do we expect P(v) to have?
The set of such vectors v is a compact subset of R^2, so it's clear what probability measure to use: ordinary Lebesgue measure, rescaled.
There is a nice answer to my question and at least one nice proof. I'll be curious to see proofs different from the one I found.
I'm happy to answer requests for clarification, but no spoilers till Sunday, please.
Jim Propp
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting- parallelograms-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices. I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it. Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it. Jim
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.) A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute. First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.) Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices. Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice? Jim Propp On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2.
I think this needs the additional assumption that the polygon is convex. Take a polygon with a sawtooth top edge, and then a thin horizontal bar above the sawtooth. translate this down a bit, and the intersection isn't connected, and has lots more sides; each tooth of the saw, which has 2 sides, contributes an additional 4-sided quadrilateral to the intersection.
The part of his argument that I still don't understand is this: how do wet know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
This isn't true in general; it's not true for the intersections of of a short fat rectangle and the translates of a long skinny rectangle. I believe it is true for the intersection of a convex polygon and its translates, but don't have a proof yet. But the fact that the proof needs to use both the fact that the polygons are translates and that they are convex should help guide the search for a proof. Let's say that P and Q are two points on the boundary of A + v, neither of which are in A. We want to show there is a path from P to Q along the boundary of A + v that does not intersect A. This will show that the boundary of A+v has only one component outside of A. I don't have the proof yet, but I can "see" that this is true, with the relationship between v and P-Q telling us which of the two paths from P to Q stays outside of A. Andy
I forgot to specify that the 2n-gon is convex. (My bad, not Veit's.) Jim On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
<< how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice? >> Perhaps I missed something earlier: this is surely false, unless the polygon is convex! [Consider translated regular pentagonal stars.] WFL On 11/11/17, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Nov 11, 2017, at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
Here’s the proof, generalized to polytopes: P is a finite convex polytope in N dimensions. We want to know the topology of the intersection of the boundary of P and the boundary of P+v, where the translation vector v is not in any of the subspaces defined by the faces of P. 1. Let V be the subspace orthogonal to v and y the coordinate of R^N orthogonal to V. Orient y so that the y-coordinate of v, y(v), is positive. 2. Let X be the projection of P into V. 3. Consider the line L(x) parallel to v at an interior point x of X. Because of the face restriction on v, the intersection of L(x) and P is a pair of points, (x,y1(x)) and (x, y2(x)), where y2(x)>y1(x). This defines two continuous functions on X: the convex function y1(x) and the concave function y2(x). 4. The intersection of P and P+v is the set (x,y(x)), where x is in X and y1(x)+y(v)<=y<=y2(x). Assume henceforth the intersection is non-empty. The boundary of the intersection is the union of the sets C1: (x,y1(x)+y(x)) and C2: (x,y2(x)) where x is in X and satisfies y2(x)-y1(x)-y(v)>=0. C1 is a subset of the boundary of P+v and C2 is a subset of the boundary of P. 5. Because y2 is concave and y1 is convex, the function y2(x)-y1(x)-y(v) is concave on X. The subset of X, where y2(x)-y1(x)-y(v)>=0, therefore defines a closed convex set, X(v). 6. From the boundary of X(v), where y2(x)-y1(x)-y(v)=0, we have a continuous 1-1 map to the intersection of C1 and C2. 7. Since X(v) is a closed convex set its boundary is a topological sphere in N-1 dimensions. By 6. this is also the topology of the intersection of C1 and C2 which by 4. is the intersection of the boundaries of P and P+v. 8. N=2: The intersection of the boundaries of convex polygons P and P+v is a pair of points (a topological 1-sphere).
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler: What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty? (The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.) I'll let someone else have the fun of posting a solution. Jim Propp On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
Nobody? ... Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.") I like the fact that the answer to this one isn't a whole number. One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning. Jim On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2. Veit also solved the puzzle, and his solution is slicker than mine: "The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6." Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-) Jim On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples: 1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane. 2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor. -Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's
appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I like these two puzzles but I'm not making progress with them. Can you provide hints or references? Jim On Sunday, November 19, 2017, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
I wrote:
> I actually know two different proofs of the result. One follows the > approach to such problems that I learned from George Hart (see his email to > math-fun from October 18), and the other follows the approach I learned > from Warren Smith (see my email to math-fun from October 19). If you look > at their solutions to the random-slices-of-a-cube problem you might be > inspired, as I was, to see how to solve the random-intersecting-parallelog > rams-puzzle. > > George's method can also be used to prove that if you take a random > nonempty intersection of a regular hexagon with a translate of itself, the > expected number of sides is exactly 5. >
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's > appropriate to have an unbridled conversation, with or without spoilers. >
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I can do the first one — I thought the second was somehow it’s dual, but if you’re only connected to your nearest neighbor (note that this relation isn’t generally symmetric) I don’t see what to do. Happy Turkey Day! - Cris
On Nov 23, 2017, at 9:16 AM, James Propp <jamespropp@gmail.com> wrote:
I like these two puzzles but I'm not making progress with them. Can you provide hints or references?
Jim
On Sunday, November 19, 2017, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
> I wrote: > > >> I actually know two different proofs of the result. One follows the >> approach to such problems that I learned from George Hart (see his email to >> math-fun from October 18), and the other follows the approach I learned >> from Warren Smith (see my email to math-fun from October 19). If you look >> at their solutions to the random-slices-of-a-cube problem you might be >> inspired, as I was, to see how to solve the random-intersecting-parallelog >> rams-puzzle. >> >> George's method can also be used to prove that if you take a random >> nonempty intersection of a regular hexagon with a translate of itself, the >> expected number of sides is exactly 5. >> > > Hint: instead of counting sides, count vertices. > > I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it. > > Anyway, two days have passed since I posted the puzzle, so I think it's >> appropriate to have an unbridled conversation, with or without spoilers. >> > > Let me say, by way of motivation, that the "George-style" proof is > really sweet. You'll feel good when you find it. > > Jim >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I would add to this: suppose you give each vertex in the square lattice a uniformly random real-valued “height" in the unit interval. We now perform local greedy search that tries to minimize the height: start at a vertex, and move to the neighbor with the lowest height, until you reach a local minimum where all the neighors are higher than the current vertex. Each local minimum has a “basin of attraction”, i.e., a set of initial vertices which will lead to it if we carry out this process. The distribution of the sizes of these basins is complicated. But what is their average size? (This is rather like Veit’s second problem…) - Cris
On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
> I actually know two different proofs of the result. One follows the > approach to such problems that I learned from George Hart (see his email to > math-fun from October 18), and the other follows the approach I learned > from Warren Smith (see my email to math-fun from October 19). If you look > at their solutions to the random-slices-of-a-cube problem you might be > inspired, as I was, to see how to solve the random-intersecting-parallelog > rams-puzzle. > > George's method can also be used to prove that if you take a random > nonempty intersection of a regular hexagon with a translate of itself, the > expected number of sides is exactly 5. >
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's > appropriate to have an unbridled conversation, with or without spoilers. >
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Harking back to Veit's problem, I once tried making inroads on a closely-related discrete problem. Suppose the randomly-chosen centers are confined to lattice-points, each point populated with probability p. What does a typical Voronoi cell look like, and how does this vary with p? I adopt the convention that q = 1-p. At p=1, all the cells are just squares. As p falls from 1, some of the cells, with a probability of 4q, become pentagons of area 1.25. The expected area of the cells thus has a Taylor series in q that starts 1 + q + ... At some point I calculated the quadratic and cubic coefficients of this series, considering more-and-more-elaborate cell shapes, but I don't remember the results. On Fri, Nov 24, 2017 at 12:28 PM, Cris Moore <moore@santafe.edu> wrote:
I would add to this: suppose you give each vertex in the square lattice a uniformly random real-valued “height" in the unit interval. We now perform local greedy search that tries to minimize the height: start at a vertex, and move to the neighbor with the lowest height, until you reach a local minimum where all the neighors are higher than the current vertex.
Each local minimum has a “basin of attraction”, i.e., a set of initial vertices which will lead to it if we carry out this process. The distribution of the sizes of these basins is complicated. But what is their average size?
(This is rather like Veit’s second problem…)
- Cris
On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
> I wrote: > > >> I actually know two different proofs of the result. One follows the >> approach to such problems that I learned from George Hart (see his email to >> math-fun from October 18), and the other follows the approach I learned >> from Warren Smith (see my email to math-fun from October 19). If you look >> at their solutions to the random-slices-of-a-cube problem you might be >> inspired, as I was, to see how to solve the random-intersecting-parallelog >> rams-puzzle. >> >> George's method can also be used to prove that if you take a random >> nonempty intersection of a regular hexagon with a translate of itself, the >> expected number of sides is exactly 5. >> > > Hint: instead of counting sides, count vertices. > > I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it. > > Anyway, two days have passed since I posted the puzzle, so I think it's >> appropriate to have an unbridled conversation, with or without spoilers. >> > > Let me say, by way of motivation, that the "George-style" proof is > really sweet. You'll feel good when you find it. > > Jim >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The quadratic coefficient is 20, corresponding to three new shapes, two pentagons and a hexagon. One pentagonal type has an area of 11/8; the other pentagon (equivalent, I believe, to baseball's home plate) and the hexagon both have areas of 3/2. On Fri, Nov 24, 2017 at 2:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Harking back to Veit's problem, I once tried making inroads on a closely-related discrete problem. Suppose the randomly-chosen centers are confined to lattice-points, each point populated with probability p. What does a typical Voronoi cell look like, and how does this vary with p? I adopt the convention that q = 1-p.
At p=1, all the cells are just squares. As p falls from 1, some of the cells, with a probability of 4q, become pentagons of area 1.25. The expected area of the cells thus has a Taylor series in q that starts 1 + q + ... At some point I calculated the quadratic and cubic coefficients of this series, considering more-and-more-elaborate cell shapes, but I don't remember the results.
On Fri, Nov 24, 2017 at 12:28 PM, Cris Moore <moore@santafe.edu> wrote:
I would add to this: suppose you give each vertex in the square lattice a uniformly random real-valued “height" in the unit interval. We now perform local greedy search that tries to minimize the height: start at a vertex, and move to the neighbor with the lowest height, until you reach a local minimum where all the neighors are higher than the current vertex.
Each local minimum has a “basin of attraction”, i.e., a set of initial vertices which will lead to it if we carry out this process. The distribution of the sizes of these basins is complicated. But what is their average size?
(This is rather like Veit’s second problem…)
- Cris
Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
> Let H be a regular hexagon and t a translation vector, so that H+t is a > translate of H. Here's one way to prove that the average number of sides in > the intersection of a H with H+t, conditioned on the event that the > intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to > that later.) > > A polygon P obtained by intersecting H with H+t can have three different > sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of > an edge of H with an edge of H+t. So we can write the expected number of > vertices of P as a sum of 48 probabilities (many of which are equal to one > another, by symmetry): the probability that a particular vertex v of H > belongs to H+t (which we sum over the 6 vertices v of H), the probability > that a particular vertex v+t of H+t belongs to H (which we sum over the 6 > vertices v of H), and the probability that a particular edge e of H > intersects a particular edge e'+t of H+t (summed over all 24 pairs of > nonparallel edges e,e' of H). But these probabilities are all easy to > interpret geometrically and thus easy to compute. > > First, let's find the common denominator of these probabilities: the > area of the set of vectors {t: the intersection of H and H+t is nonempty}. > This is the Minkowski difference H-H, and since H is centrally symmetric, > it's just 2H (up to translation). Since H is made of 6 unit equilateral > triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just > say "area 24" from now on.) > > Now, on to the numerators and the probabilities! For each vertex of H, > the set of vectors t for which that vertex of H belongs to H+t is just a > translate of H, with area 6; so the probability that the vertex v belongs > to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get > 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, > the probability that v+t belongs to H is 3/2. Finally, consider the pairs > e,e'. The set of vectors t for which e intersects e'+t is just a > parallelogram, namely, the parallelogram spanned by e and e' (treated as > vectors), which consists of two unit triangles; so the probability measure > of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 > pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, > obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices. > > Veit's proof collapses the 24 edge-meets-edge terms into a single term > whose value is the constant 2! What's more, his argument can be used to > show that for any centrally symmetric 2n-gon, the expected number of > vertices in the intersection of the 2n-gon with a translate of itself, > conditioned on the event that the intersection is nonempty, is exactly n+2. > The part of his argument that I still don't understand is this: how do we > know that (generically) the boundaries of the two 2n-gons intersect exactly > twice? > > Jim Propp > > > > On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> > wrote: > >> I wrote: >> >> >>> I actually know two different proofs of the result. One follows the >>> approach to such problems that I learned from George Hart (see his email to >>> math-fun from October 18), and the other follows the approach I learned >>> from Warren Smith (see my email to math-fun from October 19). If you look >>> at their solutions to the random-slices-of-a-cube problem you might be >>> inspired, as I was, to see how to solve the random-intersecting-parallelog >>> rams-puzzle. >>> >>> George's method can also be used to prove that if you take a random >>> nonempty intersection of a regular hexagon with a translate of itself, the >>> expected number of sides is exactly 5. >>> >> >> Hint: instead of counting sides, count vertices. >> >> I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it. >> >> Anyway, two days have passed since I posted the puzzle, so I think it's >>> appropriate to have an unbridled conversation, with or without spoilers. >>> >> >> Let me say, by way of motivation, that the "George-style" proof is >> really sweet. You'll feel good when you find it. >> >> Jim >> > >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the arithmetic all wrong. I think I got the linear coefficient right, but the quadratic one is certainly less than 20. Perhaps I will do a more careful census over the weekend, especially if anybody else on list shows any sign of understanding what I'm doing and being interested :) On Fri, Nov 24, 2017 at 2:30 PM, Allan Wechsler <acwacw@gmail.com> wrote:
The quadratic coefficient is 20, corresponding to three new shapes, two pentagons and a hexagon. One pentagonal type has an area of 11/8; the other pentagon (equivalent, I believe, to baseball's home plate) and the hexagon both have areas of 3/2.
On Fri, Nov 24, 2017 at 2:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Harking back to Veit's problem, I once tried making inroads on a closely-related discrete problem. Suppose the randomly-chosen centers are confined to lattice-points, each point populated with probability p. What does a typical Voronoi cell look like, and how does this vary with p? I adopt the convention that q = 1-p.
At p=1, all the cells are just squares. As p falls from 1, some of the cells, with a probability of 4q, become pentagons of area 1.25. The expected area of the cells thus has a Taylor series in q that starts 1 + q + ... At some point I calculated the quadratic and cubic coefficients of this series, considering more-and-more-elaborate cell shapes, but I don't remember the results.
On Fri, Nov 24, 2017 at 12:28 PM, Cris Moore <moore@santafe.edu> wrote:
I would add to this: suppose you give each vertex in the square lattice a uniformly random real-valued “height" in the unit interval. We now perform local greedy search that tries to minimize the height: start at a vertex, and move to the neighbor with the lowest height, until you reach a local minimum where all the neighors are higher than the current vertex.
Each local minimum has a “basin of attraction”, i.e., a set of initial vertices which will lead to it if we carry out this process. The distribution of the sizes of these basins is complicated. But what is their average size?
(This is rather like Veit’s second problem…)
- Cris
Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
> Here's an easier puzzle of the same kind; it's probably the one I'd > present to people first now that I know about it, since the calculations > are simpler: > > What's the expected number of vertices in the intersection of a > rightside-up equilateral triangle and an upside-down equilateral triangle > of the same size, conditioned on the event that the intersection is > nonempty? > > (The equilaterality of the triangle is a red herring; any triangle and > its rotated-by-180-degrees twin will do.) > > I'll let someone else have the fun of posting a solution. > > Jim Propp > > On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com
> wrote: > >> Let H be a regular hexagon and t a translation vector, so that H+t is a >> translate of H. Here's one way to prove that the average number of sides in >> the intersection of a H with H+t, conditioned on the event that the >> intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to >> that later.) >> >> A polygon P obtained by intersecting H with H+t can have three different >> sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of >> an edge of H with an edge of H+t. So we can write the expected number of >> vertices of P as a sum of 48 probabilities (many of which are equal to one >> another, by symmetry): the probability that a particular vertex v of H >> belongs to H+t (which we sum over the 6 vertices v of H), the probability >> that a particular vertex v+t of H+t belongs to H (which we sum over the 6 >> vertices v of H), and the probability that a particular edge e of H >> intersects a particular edge e'+t of H+t (summed over all 24 pairs of >> nonparallel edges e,e' of H). But these probabilities are all easy to >> interpret geometrically and thus easy to compute. >> >> First, let's find the common denominator of these probabilities: the >> area of the set of vectors {t: the intersection of H and H+t is nonempty}. >> This is the Minkowski difference H-H, and since H is centrally symmetric, >> it's just 2H (up to translation). Since H is made of 6 unit equilateral >> triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just >> say "area 24" from now on.) >> >> Now, on to the numerators and the probabilities! For each vertex of H, >> the set of vectors t for which that vertex of H belongs to H+t is just a >> translate of H, with area 6; so the probability that the vertex v belongs >> to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get >> 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, >> the probability that v+t belongs to H is 3/2. Finally, consider the pairs >> e,e'. The set of vectors t for which e intersects e'+t is just a >> parallelogram, namely, the parallelogram spanned by e and e' (treated as >> vectors), which consists of two unit triangles; so the probability measure >> of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 >> pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, >> obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices. >> >> Veit's proof collapses the 24 edge-meets-edge terms into a single term >> whose value is the constant 2! What's more, his argument can be used to >> show that for any centrally symmetric 2n-gon, the expected number of >> vertices in the intersection of the 2n-gon with a translate of itself, >> conditioned on the event that the intersection is nonempty, is exactly n+2. >> The part of his argument that I still don't understand is this: how do we >> know that (generically) the boundaries of the two 2n-gons intersect exactly >> twice? >> >> Jim Propp >> >> >> >> On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com
>> wrote: >> >>> I wrote: >>> >>> >>>> I actually know two different proofs of the result. One follows the >>>> approach to such problems that I learned from George Hart (see his email to >>>> math-fun from October 18), and the other follows the approach I learned >>>> from Warren Smith (see my email to math-fun from October 19). If you look >>>> at their solutions to the random-slices-of-a-cube problem you might be >>>> inspired, as I was, to see how to solve the random-intersecting-parallelog >>>> rams-puzzle. >>>> >>>> George's method can also be used to prove that if you take a random >>>> nonempty intersection of a regular hexagon with a translate of itself, the >>>> expected number of sides is exactly 5. >>>> >>> >>> Hint: instead of counting sides, count vertices. >>> >>> I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it. >>> >>> Anyway, two days have passed since I posted the puzzle, so I think it's >>>> appropriate to have an unbridled conversation, with or without spoilers. >>>> >>> >>> Let me say, by way of motivation, that the "George-style" proof is >>> really sweet. You'll feel good when you find it. >>> >>> Jim >>> >> >> >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Nov 24, 2017 at 4:38 PM Allan Wechsler <acwacw@gmail.com> wrote:
> I did the arithmetic all wrong. I think I got the linear coefficient right,
> but the quadratic one is certainly less than 20. Perhaps I will do a more
> careful census over the weekend, especially if anybody else on list shows
> any sign of understanding what I'm doing and being interested :)
>
> On Fri, Nov 24, 2017 at 2:30 PM, Allan Wechsler <acwacw@gmail.com> wrote:
>
> > The quadratic coefficient is 20, corresponding to three new shapes, two
> > pentagons and a hexagon. One pentagonal type has an area of 11/8; the
> other
> > pentagon (equivalent, I believe, to baseball's home plate) and the
> hexagon
> > both have areas of 3/2.
> >
> > On Fri, Nov 24, 2017 at 2:17 PM, Allan Wechsler <acwacw@gmail.com>
> wrote:
> >
> >> Harking back to Veit's problem, I once tried making inroads on a
> >> closely-related discrete problem. Suppose the randomly-chosen centers
> are
> >> confined to lattice-points, each point populated with probability p.
> What
> >> does a typical Voronoi cell look like, and how does this vary with p? I
> >> adopt the convention that q = 1-p.
> >>
> >> At p=1, all the cells are just squares. As p falls from 1, some of the
> >> cells, with a probability of 4q, become pentagons of area 1.25. The
> >> expected area of the cells thus has a Taylor series in q that starts 1
> + q
> >> + ... At some point I calculated the quadratic and cubic coefficients of
> >> this series, considering more-and-more-elaborate cell shapes, but I
> don't
> >> remember the results.
> >>
> >> On Fri, Nov 24, 2017 at 12:28 PM, Cris Moore <moore@santafe.edu> wrote:
> >>
> >>>
> >>> I would add to this: suppose you give each vertex in the square lattice
> >>> a uniformly random real-valued “height" in the unit interval. We now
> >>> perform local greedy search that tries to minimize the height: start
> at a
> >>> vertex, and move to the neighbor with the lowest height, until you
> reach a
> >>> local minimum where all the neighors are higher than the current
> vertex.
> >>>
> >>> Each local minimum has a “basin of attraction”, i.e., a set of initial
> >>> vertices which will lead to it if we carry out this process. The
> >>> distribution of the sizes of these basins is complicated. But what is
> >>> their average size?
> >>>
> >>> (This is rather like Veit’s second problem…)
> >>>
> >>> - Cris
> >>>
> >>>
> >>>
> >>> > On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
> >>> >
> >>> > This kind of question brings up the phenomenon of probability
> >>> distributions
> >>> > that are very hard to compute and yet have easily computed
> expectation
> >>> values.
> >>> > Here are two of my favorite examples:
> >>> >
> >>> > 1. The expected number of sides of the Voronoi cells for random,
> >>> homogeneously
> >>> > distributed points in the infinite plane.
> >>> >
> >>> > 2. The expected number of stars per constellation, in the model where
> >>> stars are
> >>> > distributed homogeneously over an infinite plane (large sphere) and
> >>> assigned to
> >>> > constellations (connected graphs) by the rule that each star is
> joined
> >>> by an edge
> >>> > to its nearest neighbor.
> >>> >
> >>> > -Veit
> >>> >
> >>> >> On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com>
> >>> wrote:
> >>> >>
> >>> >> To get the answer, let's treat the number of vertices of the random
> >>> polygon
> >>> >> P as a sum of indicator functions, so that the expected number of
> >>> vertices
> >>> >> is the sum of the probabilities of the events associated with those
> >>> >> indicator functions. (I'll be concise and possibly confusing here,
> >>> since
> >>> >> the style of reasoning is similar to one I've described in greater
> >>> detail
> >>> >> before.) Each of the three vertices of the first triangle
> contributes
> >>> 1/4,
> >>> >> since that's the probability that the vertex will fall inside the
> >>> second
> >>> >> triangle when it's translated by a random vector that makes the
> >>> >> intersection of the two triangles nonempty (you can obtain 1/4 as
> the
> >>> ratio
> >>> >> of two areas). Each of the three vertices of the second triangle
> >>> >> contributes 1/4 for the same reason. So we get six contributions of
> >>> 1/4.
> >>> >> Meanwhile, for any edge e of the first triangle and any edge e' of
> the
> >>> >> second triangle not parallel to e, the probability that they'll give
> >>> rise
> >>> >> to a vertex of P is 2/4 (again obtained as a ratio of two areas), so
> >>> we get
> >>> >> six contributions of 2/4. So the expected number of vertices is
> >>> >> 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
> >>> >>
> >>> >> Veit also solved the puzzle, and his solution is slicker than mine:
> >>> >>
> >>> >> "The intersection has either 4 or 6 sides. The locus of translations
> >>> of the
> >>> >> down triangle that gives an intersection is the up triangle scaled
> by
> >>> 2.
> >>> >> Join the edge midpoints of that triangle to give a partition into 4
> >>> >> congruent triangles, one of which is a translate of the down
> >>> triangle, the
> >>> >> other three translates of the up (all four have the same area). If
> the
> >>> >> translation belongs to one of the up partitions, the intersection
> has
> >>> 4
> >>> >> sides. In the other case, the intersection has 6 sides. The expected
> >>> number
> >>> >> of sides is therefore (3/4)4 + (1/4)6."
> >>> >>
> >>> >> Either way, we see that a "random" intersection of a rightside-up
> unit
> >>> >> triangle with an upside-down unit triangle is a semi-enneagon! :-)
> >>> >>
> >>> >> Jim
> >>> >>
> >>> >> On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com>
> >>> wrote:
> >>> >>
> >>> >>> Nobody? ...
> >>> >>>
> >>> >>> Maybe these puzzles are less fun than I thought. (Or maybe "Fun is
> >>> fun,
> >>> >>> but enough's enough.")
> >>> >>>
> >>> >>> I like the fact that the answer to this one isn't a whole number.
> >>> >>>
> >>> >>> One frustrating feature of this particular puzzle is that someone
> >>> with no
> >>> >>> mathematical training might guess the correct answer using bogus
> >>> reasoning.
> >>> >>>
> >>> >>> Jim
> >>> >>>
> >>> >>> On Tue, Nov 14, 2017 at 10:13 PM, James Propp <
> jamespropp@gmail.com>
> >>> >>> wrote:
> >>> >>>
> >>> >>>> Here's an easier puzzle of the same kind; it's probably the one
> I'd
> >>> >>>> present to people first now that I know about it, since the
> >>> calculations
> >>> >>>> are simpler:
> >>> >>>>
> >>> >>>> What's the expected number of vertices in the intersection of a
> >>> >>>> rightside-up equilateral triangle and an upside-down equilateral
> >>> triangle
> >>> >>>> of the same size, conditioned on the event that the intersection
> is
> >>> >>>> nonempty?
> >>> >>>>
> >>> >>>> (The equilaterality of the triangle is a red herring; any triangle
> >>> and
> >>> >>>> its rotated-by-180-degrees twin will do.)
> >>> >>>>
> >>> >>>> I'll let someone else have the fun of posting a solution.
> >>> >>>>
> >>> >>>> Jim Propp
> >>> >>>>
> >>> >>>> On Sat, Nov 11, 2017 at 11:06 AM, James Propp <
> jamespropp@gmail.com
> >>> >
> >>> >>>> wrote:
> >>> >>>>
> >>> >>>>> Let H be a regular hexagon and t a translation vector, so that
> H+t
> >>> is a
> >>> >>>>> translate of H. Here's one way to prove that the average number
> of
> >>> sides in
> >>> >>>>> the intersection of a H with H+t, conditioned on the event that
> the
> >>> >>>>> intersection is nonempty, is 5. (Veit found a nicer way, but I'll
> >>> get to
> >>> >>>>> that later.)
> >>> >>>>>
> >>> >>>>> A polygon P obtained by intersecting H with H+t can have three
> >>> different
> >>> >>>>> sorts of vertices: a vertex of H, a vertex of H+t, and the
> >>> intersection of
> >>> >>>>> an edge of H with an edge of H+t. So we can write the expected
> >>> number of
> >>> >>>>> vertices of P as a sum of 48 probabilities (many of which are
> >>> equal to one
> >>> >>>>> another, by symmetry): the probability that a particular vertex v
> >>> of H
> >>> >>>>> belongs to H+t (which we sum over the 6 vertices v of H), the
> >>> probability
> >>> >>>>> that a particular vertex v+t of H+t belongs to H (which we sum
> >>> over the 6
> >>> >>>>> vertices v of H), and the probability that a particular edge e
> of H
> >>> >>>>> intersects a particular edge e'+t of H+t (summed over all 24
> pairs
> >>> of
> >>> >>>>> nonparallel edges e,e' of H). But these probabilities are all
> easy
> >>> to
> >>> >>>>> interpret geometrically and thus easy to compute.
> >>> >>>>>
> >>> >>>>> First, let's find the common denominator of these probabilities:
> >>> the
> >>> >>>>> area of the set of vectors {t: the intersection of H and H+t is
> >>> nonempty}.
> >>> >>>>> This is the Minkowski difference H-H, and since H is centrally
> >>> symmetric,
> >>> >>>>> it's just 2H (up to translation). Since H is made of 6 unit
> >>> equilateral
> >>> >>>>> triangles, 2H has area equal to 24 unit equilateral triangles.
> >>> (I'll just
> >>> >>>>> say "area 24" from now on.)
> >>> >>>>>
> >>> >>>>> Now, on to the numerators and the probabilities! For each vertex
> >>> of H,
> >>> >>>>> the set of vectors t for which that vertex of H belongs to H+t is
> >>> just a
> >>> >>>>> translate of H, with area 6; so the probability that the vertex v
> >>> belongs
> >>> >>>>> to H+t is just the area of H divided by the area of 2H, or
> >>> 6/24=1/4. We get
> >>> >>>>> 6 such terms, for a total of 6/4 = 3/2. Likewise, for each
> vertex
> >>> v of H,
> >>> >>>>> the probability that v+t belongs to H is 3/2. Finally, consider
> >>> the pairs
> >>> >>>>> e,e'. The set of vectors t for which e intersects e'+t is just a
> >>> >>>>> parallelogram, namely, the parallelogram spanned by e and e'
> >>> (treated as
> >>> >>>>> vectors), which consists of two unit triangles; so the
> probability
> >>> measure
> >>> >>>>> of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over
> >>> all 24
> >>> >>>>> pairs e,e', we get 24/12, or 2. Finally, we add up all the
> >>> probabilities,
> >>> >>>>> obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
> >>> >>>>>
> >>> >>>>> Veit's proof collapses the 24 edge-meets-edge terms into a single
> >>> term
> >>> >>>>> whose value is the constant 2! What's more, his argument can be
> >>> used to
> >>> >>>>> show that for any centrally symmetric 2n-gon, the expected number
> >>> of
> >>> >>>>> vertices in the intersection of the 2n-gon with a translate of
> >>> itself,
> >>> >>>>> conditioned on the event that the intersection is nonempty, is
> >>> exactly n+2.
> >>> >>>>> The part of his argument that I still don't understand is this:
> >>> how do we
> >>> >>>>> know that (generically) the boundaries of the two 2n-gons
> >>> intersect exactly
> >>> >>>>> twice?
> >>> >>>>>
> >>> >>>>> Jim Propp
> >>> >>>>>
> >>> >>>>>
> >>> >>>>>
> >>> >>>>> On Mon, Nov 6, 2017 at 10:07 PM, James Propp <
> jamespropp@gmail.com
> >>> >
> >>> >>>>> wrote:
> >>> >>>>>
> >>> >>>>>> I wrote:
> >>> >>>>>>
> >>> >>>>>>
> >>> >>>>>>> I actually know two different proofs of the result. One follows
> >>> the
> >>> >>>>>>> approach to such problems that I learned from George Hart (see
> >>> his email to
> >>> >>>>>>> math-fun from October 18), and the other follows the approach I
> >>> learned
> >>> >>>>>>> from Warren Smith (see my email to math-fun from October 19).
> If
> >>> you look
> >>> >>>>>>> at their solutions to the random-slices-of-a-cube problem you
> >>> might be
> >>> >>>>>>> inspired, as I was, to see how to solve the
> >>> random-intersecting-parallelog
> >>> >>>>>>> rams-puzzle.
> >>> >>>>>>>
> >>> >>>>>>> George's method can also be used to prove that if you take a
> >>> random
> >>> >>>>>>> nonempty intersection of a regular hexagon with a translate of
> >>> itself, the
> >>> >>>>>>> expected number of sides is exactly 5.
> >>> >>>>>>>
> >>> >>>>>>
> >>> >>>>>> Hint: instead of counting sides, count vertices.
> >>> >>>>>>
> >>> >>>>>> I'll sketch the proof tomorrow or Wednesday, if nobody beats me
> >>> to it.
> >>> >>>>>>
> >>> >>>>>> Anyway, two days have passed since I posted the puzzle, so I
> >>> think it's
> >>> >>>>>>> appropriate to have an unbridled conversation, with or without
> >>> spoilers.
> >>> >>>>>>>
> >>> >>>>>>
> >>> >>>>>> Let me say, by way of motivation, that the "George-style" proof
> is
> >>> >>>>>> really sweet. You'll feel good when you find it.
> >>> >>>>>>
> >>> >>>>>> Jim
> >>> >>>>>>
> >>> >>>>>
> >>> >>>>>
> >>> >>>>
> >>> >>>
> >>> >> _______________________________________________
> >>> >> math-fun mailing list
> >>> >> math-fun@mailman.xmission.com
> >>> >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> >>> >
> >>> >
> >>> > _______________________________________________
> >>> > math-fun mailing list
> >>> > math-fun@mailman.xmission.com
> >>> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> >>>
> >>>
> >>> _______________________________________________
> >>> math-fun mailing list
> >>> math-fun@mailman.xmission.com
> >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
> >>>
> >>
> >>
> >
> _______________________________________________
> math-fun mailing list
> math-fun@mailman.xmission.com
> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
>
Veit showed that (1) if you condition on the intersection being nonempty, a random intersection of a rightside-up unit triangle and an upside-down unit triangle has 6 sides with probability 1/4 and 4 sides with probability 3/4. I've calculated that (2) if you instead condition on a particular point lying in the intersection, the intersection has 6 sides with probability 13/27 and 4 sides with probability 14/27. This might seem paradoxical, but consider that, relative to probability distribution (2), probability distribution (1) exhibits "size-biasing": situations in which the intersection has bigger area get weighted more heavily. One might conversely say that, relative to probability distribution (1), probability distribution (2) exhibits "reciprocal size-biasing". Is there an existing phrase for that? Jim Propp On Fri, Nov 17, 2017 at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
I actually know two different proofs of the result. One follows the approach to such problems that I learned from George Hart (see his email to math-fun from October 18), and the other follows the approach I learned from Warren Smith (see my email to math-fun from October 19). If you look at their solutions to the random-slices-of-a-cube problem you might be inspired, as I was, to see how to solve the random-intersecting-parallelog rams-puzzle.
George's method can also be used to prove that if you take a random nonempty intersection of a regular hexagon with a translate of itself, the expected number of sides is exactly 5.
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think
it's appropriate to have an unbridled conversation, with or without spoilers.
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
participants (7)
-
Allan Wechsler -
Andy Latto -
Cris Moore -
Fred Lunnon -
James Propp -
Thane Plambeck -
Veit Elser