Getting rid of triangles, and other ways to Euler

That proof that any convex polyhedron made of pentagons and hexagons must contain at least 12 pentagons rests on Euler’s polyhedron formula: If a convex polyhedron has V vertices, E edges, and F faces, then

V-E+F=2

So how is that proved? Lots of ways, some of which rely on the Jordan curve theorem, so then you need a proof of that. An outline of one that doesn’t use the Jordan curve theorem, Triangle Removal, is as follows.

First, transform the polyhedron into a planar graph. You can think of this as removing one face of the polyhedron, and then stretching the boundaries of that face and deforming the other edges until all the edges lie in a plane. Or you can think of it as putting a light source near one face and a plane on the opposite side: the shadow cast onto the plane is the planar graph. This graph has the same number of vertices and edges as the polyhedron, and apparently one fewer face — until you realize the entire plane exterior to the graph can be thought of as a face too.

Okay, we have our graph. Now do the following: Find any interior face that has more than three edges, and draw a diagonal through it from one vertex to another. Doing that increases the number of edges by 1, and divides one face into two, but leaves the vertices unchanged. That means V-E+F is unchanged. Repeat that until all the interior faces are triangles.

Now do this:

  1. Identify a triangle that has two edges on the border of the graph. If you can’t find one, go to step 2. If you can find one, remove those two edges. This eliminates two edges, one face, and one vertex, so again V-E+F is unchanged. Now repeat step 1.
  2. Identify a triangle that has one edge on the border of the graph. Remove that edge. This eliminates one edge, one face, and no vertices, so again V-E+F is unchanged. Now repeat step 1.

Keep repeating as long as you can. Here I get hand wavy, because I’m less than clear on the argument, but: You don’t want to do step 2 if you can do step 1, because that leads to dead ends — specifically, a graph broken up into two disconnected graphs. Always do step 1 if you can, step 2 only if you can’t do step 1, and the graph will stay connected.

For instance, starting from a (kinda irregular) square pyramid. Here it’s turned into a planar graph with one quadrilateral and three triangular faces (the fourth triangle mapping to the exterior of the graph). The quadrilateral is divided into two triangles, and then triangles are removed one at a time.

Since the graph stays connected, the process continues until there’s only one triangle left. At this point we stop and take a tally: There are 3 vertices, 3 edges, and 2 faces (the interior of the triangle, and the exterior). So V-E+F = 2, and since every step we took preserved the value of V-E+F, this proves V-E+F=2 for the original polyhedron.

Something about that proof appeals to me, even though there’s that one part I’m hazy on.

The Sum of Angles proof I find clearer, but less cute. Here again you turn the polyhedron into a planar graph with straight edges. Now add up the interior angles of all the faces (including the exterior face). For face i, which has k_i edges, the sum of the interior angles is (k_i-2)\pi. Summing over all the faces,

\Sigma_{i=1}^F(k_i-2)\pi = \left(\Sigma_{i=1}^Fk_i-\Sigma_{i=1}^F2\right) = (2E-2F)\pi

But we get the same result if we sum the angles meeting at each vertex. For each interior vertex, the sum is 2\pi, adding up to 2\pi(V-k) where k is the number of vertices on the border. For the vertices on the border, it’s 2(\pi-\theta_i) where \theta_i is the exterior angle at the ith vertex of the exterior polygon, and the 2 is because we include the (equal) contributions of the internal and external polygons. But the sum of the exterior angles of a polygon is 2\pi, so the exterior vertices contribute a total of 2\pi k-4\pi. Altogether, then, the sum is 2\pi V-4\pi.

So (2E-2F)\pi = 2\pi V-4\pi, or E-F = V-2,

Either way, no Jordan curve theorem required! Yay.

Advertisements

Hexagonal filth

I was amused by this report of a petition to change the representation of soccer balls on UK signs. At present the image is of a ball divided into brown and white hexagons. At least on one side.

The problem is, if it’s hexagons all the way around, it’s a geometric impossibility. You can’t have a convex polyhedron consisting solely of hexagons, regular or otherwise. In fact: If a convex polyhedron has only hexagons and/or pentagons as faces, then there must be at least 12 pentagons.

The proof is based on Euler’s polyhedron formula: If a convex polyhedron has V vertices, E edges, and F faces, then

V-E+F=2.

For our hex-and-pent-agon polyhedron, consisting of h hexagons and p pentagons, F = p+h, of course. What’s E? Well, each hexagon has 6 edges and each pentagon has 5, but that counts each edge twice since each edge belongs to two faces. So E = (5p+6h)/2.

Now, at each vertex, at least 3 edges meet. If you add up the number of edges at each vertex over all vertices you get at least 3V; but since each edge contributes 2 to that total, 3V \le 2E.

But from Euler’s formula,

3V = 6+3E-3F \le 2E

or

6-3F \le -E

and substituting our formulas for F and E,

6-3p-3h \le -(5p+6h)/2

or

12-6p-6h \le -5p-6h

or

12-p \le 0

or

p \ge 12.

QED.

(The equality holds if every vertex has 3 edges — or equivalently, 3 faces. In particular, if you’re using only regular hexagons and pentagons, then there isn’t room at a vertex for more than 3 faces to meet there. So for a polyhedron made of regular hexagons and pentagons, or any polyhedron with exactly three hexagons and/or pentagons meeting at each vertex, p = 12.)

Hence the government must be petitioned. As The Aperiodical says, “Ban this hexagonal filth!”

Enigma 1759

Spoiler for New Scientist Enigma 1759: “Cell count” (Follow the link to see the puzzle.)

I can’t see an easy way to do this by hand, but it can be done in a spreadsheet; the key is to figure out the needed formula.

Consider just the upper right quadrant; of course the number of cells crossed for the whole circle will be 4 times the number for the quadrant. Now consider each increment along the x axis from 0 to 1 to 2 to … to r, the radius. When x goes to (x+1), y goes from √(r2x2) to √(r2–(x+1)2). The number of cells passed through in this column is 1 greater than the number of times the circle crosses a horizontal line (not counting lines started or ended on). Think about it hard enough and you realize the number of cells crossed in the file starting at x is:

√(r2x2)√(r2–(x+1)2)

where xand xare respectively the ceiling and floor functions. Multiply that by 4 and sum over all x from 0 to r–1 and you have the number of cells crossed.

So put that into a spreadsheet and graph the result:

chart_1For a radius of less than 50, the only place the number of cells decreases when the radius increases is in going from radius 24 (188 cells) to 25 (180 cells).

Enigma 1758

Spoiler for New Scientist Enigma 1758: “Path-o-logical” (Follow the link to see the puzzle.)

If a is a north-south side of the park and b is the length of a path then a and b are a side and hypotenuse of a right triangle. Call its other side x. Likewise b and c, where c is an east-west side of the park, must be a side and hypotenuse of another right triangle. Now, if you draw a perpendicular to the south side of the park through the path intersection, then the second of these triangles is split into two. All these triangles are similar and in fact the one in the southeast corner is congruent to the one in the northwest, so that perpendicular line segment must also be and c, not a, is the long side of the park: ca + 25. Then the southwest triangle has sides x and 25. Call its hypotenuse (the distance from the southwest corner to the path intersection) y.

Summarizing, the sides of these three similar triangles are:

  • a : x : b
  • x : 25 : y
  • b : y : a+25

a and b must be integers (but nothing says x or y must be).

From similarity of the first two triangles we get x2 = 25a. From the Pythagorean Theorem applied to the first triangle, b2 – a2 = x2 = 25a. If we write ba + δ then 2δ+δ2/a = 25. δ then must be an integer in the range [1, 12] and of these only 12 and 10 give integer values for a in that equation, namely 144 and 20, with corresponding values for b of 156 and 30.

Then x = 60 or 10√5 respectively. Using the Pythagorean Theorem for the second triangle, y = 65 or 15√5 ~ 33.54 respectively. But for the path intersection to be inside the park we need yb. So the only solution that works is: a = 144, b = 156:

park

Enigma 1757

Spoiler for New Scientist Enigma 1757: “Power point” (Follow the link to see the puzzle.)

The only 3-digit powers of 1-digit numbers are: 128, 256, and 512 (2^7, 2^8=4^4, and 2^9 = 8^3), 243 and 729 (3^5 and 3^=9^3), 125 and 625 (5^3 and 5^4), 216 (6^3), and 343 (7^3).

The four numbers with 2 as the middle digit (125, 128, 625, and 729) can connect to each other but none can connect to anything else, so they’re eliminated, leaving us with the remaining five numbers. Now all we need is the order.

512 can connect only to 216, so if we don’t start with it we have to end with it. But we start with an odd number, so 512 must be the last number and 216 must be second to last.

343 can connect only to 243, so if we don’t end with it we have to start with it. But we end with 512, so 343 must be the first number and 243 must be second.

Then 256 must be in the middle: 343–243–256–216–512.

 

Enigma 1755

Spoiler for New Scientist Enigma 1755: “Sudoprime II” (Follow the link to see the puzzle.)

Label the columns a through e (left to right) and the rows 1 through 5 (top to bottom). We’re given a1 = 7 and b3=3.

We’ll make lots of use of the fact that the last digit of a prime (other than 2) must be 1, 3, 7, or 9.

To make a1 down prime, a2 must be 1, 3, or 9. If 1: a2 across is 11, 13, 17, or 19; only 19 works. If 3: a2 across is 31 or 37; only 31 works. If 9: a2 across is 97, which doesn’t work. So a1 down and a2 across are 71 and 19, or 73 and 31.

Try 71 and 19:

b2 down must be 937. a5 can be 3 or 9, but if 9, there is no value for a4 that makes a4 across and a4 down both prime. If a5 is 3 then a4 can only be 4.

Now e5 can only be 1, and then e4 must be 3. And now d4 can’t be anything!

Try 73 and 31:

b2 down can only be 137 or 139. If it’s 139 then a5 is 1, but now there are no valid values for a4. So b4 is 7. a4 across and a4 down can be 17 and 19, 47 and 41, or 67 and 61.

d4 and e5 each can only be 3 or 9. Then e4 must be 1. That means d4 is 3 and e5 is 9.

a4 cannot be 1, so a5 is 1.

e2 can only be 7. d2 then is 4, 6, or 9. d3 can be 1, 7, or 9. Checking the nine possibilities for d2 down, the only ones that work are 613 and 673. So d2 is 6. d3 can be 1 or 7. a4 can’t be 6 so must be 4, and then e1 can only be 3.

b3 across is 3_1 or 3_7. Checking the possible values for c3 the only one that works is 0, with d3 equal to 7.

That’s everything. The solution is

a b c d e
1 7 3
2 3 1 6 7
3 3 0 7
4 4 7 3 1
5 1 9

and the shaded regions required are 307 and 41.

 

Enigma 1752

Spoiler for New Scientist Enigma 1751: “Pentagon of squares” (Follow the link to see the puzzle.)

I’m not happy about my solution to this puzzle. I think I have the right answer, but I had to resort to a computer program to get it. I’m probably thinking about it stupidly.

Here’s a picture of what’s going on:

e1752The red line segments are the pentagon; as required, it doesn’t contain the center of the circle it’s inscribed in . The interior angles (angles between the red line segments) are marked a2, b2, c2, d2, and x. Since the non-square angle x is the smallest, I’ve made it one of the angles on the long side. We know all of the interior angles are less than 180°, and all the ones that are squares must be larger than x and therefore larger than 1, so abc, and d must be in the range [2..13]. Also marked are the radii through each vertex, and the radial angles (between the radii) α, β, ɣ, and δ.

We know the interior angles of a pentagon must sum to 540°, but that’s not enough of a constraint; we also have to make sure the pentagon can be inscribed in a circle. For that we use a theorem that says interior angles subtending the same chord are equal to one another, and to half the central angle subtending that chord. So for instance interior angle aand central angle α + β + ɣ subtend the same chord, so a= (α + β + ɣ)/2. Likewise x = (β + ɣ + δ)/2, and similarly (pun intended) b= 180 – (ɣ + δ)/2, c= 180 – (β + ɣ)/2, and d= 180 – (α + β)/2. From these relations we can get expressions for the radial angles:

α = 2(a2+c2)–360

β = 720–2(a2+c2+d2)

ɣ = 2(a2+d2)–360

δ = 720–2(a2+b2+d2)

So given choices for abc, and d, we can calculate α, β, ɣ, δ, and x. We require all of these to be positive; xa2b2c2, and d2; and α+β+ɣ+δ < 180 to make the center lie outside the pentagon.

There may be a clever way from here to find the one and only solution, but I don’t see it. Instead I wrote a Perl script that came up with:

a= 64, b2 = 169, c2 = 144, and d= 121; then α = 56, β = 62, ɣ = 10, and δ = 12 (summing to 140), and = 42. That in fact is exactly the pentagon I’ve illustrated above. In case you’re suspicious, the interior angles do indeed sum to 540.The answer they’re looking for is: 42, 64, and 121.