The Jeweller's Dilemma

Question

You are well known as the best jeweller in Puzzovania; your shop is always well stocked and your pockets are always bulging.

One day, the local 'godfather' of Puzzovania's organised crime comes into your shop. Naturally, you owe him a favour - who doesn't in these parts? He hands you a diamond the size of a hen's egg and tells you what he requires from you:

"This is for my daughter. She's getting married - you understand? I want her to have the best-cut diamond in the whole of Puzzovania. It's family honour."

You nod mutely, inspecting the diamond in awe. It's the biggest one you've ever seen. You decide it would be more prudent not to ask where the diamond came from.

"So listen, my friend. The diamond needs to be cut to the shape of a convex polyhedron. Any size and shape; that doesn't matter. What matters is that every face of the polyhedron needs to have a different number of sides. My daughter's such a changeable character - never quite the same person twice. I want her jewel to reflect that. Do you think you can manage that for me?"

"Of ... of course, Godfather," you stammer. Once that imposing gentleman has taken his leave, you sit down, still holding the diamond, and wonder how you're going to do it. You need to call in a mathematician ... or possibly a puzzler!

Can you satisfy the Godfather's wishes? If so, construct a polyhedron as required (and prepare your best suit, since he'll probably invite you to the wedding as a reward). If not, prove the non-existence of such a polyhedron (and book your flight out of the country, to somewhere far enough away to be out of the reach of his power).

_{(Note: this puzzle sounds much better if you read all the Godfather's words in Marlon Brando's voice.)}

Answer 1

It is

not possible

Proof/construction:

Let $k$ be the greatest number of sides of any face. This face must touch $k$ other faces. But, each other face must have a distinct number of sides from $3,4,\dots,k-1$, which allows only $k-3$ other faces.

Even more strongly,

there must be a repeat even if you can ignore two faces. This means, either four faces with the same number of sides, a triplet and a pair, or three pairs.

Answer 2

It is possible!

How is that polyhedron?

It has 1 face, 1 edge and 0 vertexes!

WTF!? How!?

You will need a non-euclidean 3D space. There are many possibilities, but lets choose the one with euclidean Y and Z axis, but with a X axis that features self-repetition with rotation.

Ok, you are wondering, what the hell is self-repetition with rotation?

It works this way: Every time you walks a given distance (let's call it $M$) through the X axis (the self-repeating one), you come back to the same YZ plane you were before, but rotated $k$ degrees around the X axis. Here, $k$ may be any rational fraction of 360 degrees which is not an integer multiple of 180 degrees.
Or mathematically, $k = \frac{p}{q} \times 360^\circ | p,q \in \mathbb{Z} \land \frac{2p}{q} \notin \mathbb{Z}$

The result is something similar to a Möbius strip in a 3D space, though it is not exactly that.

For simplicity, I will choose $k = 90^\circ$, but you could choose any other value that satisfies the above restriction as well.

It is hard to understand? So let's visualize that with $k = 90^\circ$:

The bar is the "polyhedron". To see what is happening here, I attached ONE (and just ONE) blue peg in the polyhedron. As you see, space repeats itself after some distance through the X axis with a 90 degrees rotation.

Let's see some properties of this particular polyhedron:

• It has only one face.
  
• Its face has itself as the opposite face.
  
• Its face also has itself as its left and as its right neighbouring faces.
  
• Its face neighbours itself twice with only a single edge.
  
• Its edge, due to the self-repetition of the space, needs no vertexes.
  
• Its face is planar.
  
• Its edge is straight.
  
• The polyhedron is convex.
  
• All its faces have a different number of edges and there are no 2 faces with the same number of edges (because there are not even 2 faces to start with). So, this satisfacts Godfather's wishes!
  
• Nothing in the problem said that normal 3D euclidean space should be assumed, so I am breaking no rules here!
  

Ok, but how could the best jeweller of Puzzovania construct such thing? The jeweller can't make space behave this way!

You would need to think with portals. And with a little help from Apperture Science, it is easily doable using your portal gun. Note the 90 degrees rotation between the portals.

Answer 3

This sounds impossible to me.

Imagine constructing the polyhedron by starting with a triangle (3 sides), and then adding one adjacent polygon at a time. Each additional polygon must have an extra side, and each additional polygon, being flat and having straight edges, can share at most one edge with at most all of the previous polygons (in practice, this is probably not possible, but it is the best-case scenario).

1st polygon:  Triangle -- 3 open edges (not connected to another polygon)    
2nd polygon:  Quadrilateral -- 3 open edges (one shared with the triangle)    
              Total:  5 open edges (3 from the quadrilateral, plus 2 from the triangle)
3rd polygon:  Pentagon -- 3 open edges (one shared with each of the previous polygons)
              Total:  3 + 2 + 1 = 6 open edges
4th polygon:  Hexagon -- 3 open edges
              Total:  3 + 2 + 1 = 6 open edges (triangle's edges are all used up)    
5th polygon:  Heptagon -- 4 open edges (shared with hexagon, pentagon, quadrilateral)
              Total: 4 + 2 + 1 = 7 open edges
6th polygon:  Octagon -- 5 open edges (shared with heptagon, hexagon, pentagon)
              Total:  5 + 3 + 1 = 9 open edges      

As you can see, as you continue to add more, larger polygons, the number of open edges (edges not connected to another polygon) continues to increase. If you started with something other than a triangle, it would just jack the numbers up even higher.

Thus it is evident that there is no way to construct a polyhedron in the way the Godfather is requesting, and you'd better skip town as soon as possible.

Answer 4

It's impossible. Take the dual of the polyhedron's edge graph; every simple graph has at least 2 nodes with the same degree.

---

Appendix:

The polyhedron's edge graph is the graph you get when you start with a set of vertices corresponding to the polyhedron's vertices, and connect every pair of vertices that are connected by a polygon edge in your polyhedron. This can be proven to be a planar graph. Informally, it is the graph you get by unfolding or flattening the polyhedron onto a plane. See https://en.wikipedia.org/wiki/Polyhedral_graph

The dual of a planar graph is the graph you get by swapping the faces and vertices. To build a dual H from a graph G, place a vertex in the middle of each face in G, and connect vertices in H iff the corresponding faces in G are adjacent (share an edge). See https://en.wikipedia.org/wiki/Dual_graph and https://en.wikipedia.org/wiki/Dual_polyhedron

Finally, every simple graph has a pair of vertices with equal degree. We will prove the stronger result that every connected component has such a pair. If the component has n vertices, the degree of each vertex is a number in 1, 2, ..., n-1 so by the pigeonhole principle there is a repeat.

Answer 5

There is an easy solution using Euler's formula, V - E + F = 2, but it's not as elegant as xnor's solution. Suppose there are k faces and that the sum of the sides on all the faces is S. Then E = S/2 and since at least three faces meet at each vertex, V <= S/3. Substituting into Euler's formula gives S/6 <= k-2. S is smallest when the sides are 3,4,5,...,k+2 and it's easy to see that the inequality is never satisfied.

Suppose the requirement is that for each face there is exactly one other face with the same number of sides? Then there are finitely many solutions, and I've constructed one specific polyhedron. Can you find all solutions? Now Euler's formula comes into its own.