## Christmas Ornaments

```Given a collection of Christmas ornaments in the shape of arbitrary
polyhedra (such as, but not limited to cubes, tetrahedra, icosahedra,
etc), suppose each face of each polyhedron is colored depending on
the number of edges of the face.  For example, every four-sided face
(such as a face of a cube) has color number 4, and every triangular
face has color number 3, and in general every n-sided face has color
number n.  Can there be a Christmas Ornament with all sides painted
a different color?

If we assume that two faces share no more than one common edge, and
that there are a finite number of faces, then the answer is easily
seen to be no.  Simply list, in order, the numbers of neighbors for
the n faces, so we have a list of n strictly increasing positive
integers (because no two faces have the same number of neighbors).
Thus at least one of the n faces must border on at least n other
faces, which is impossible because there are only n-1 other faces.

On the other hand, if we remove the restriction to finite-faced
polyhedra, the answer is yes, because we can define a fractal
structure that has no two surfaces with the same number of "sides".
To illustrate this, consider a regular tetrahedron, each of whose
four triangular faces has 3 sides.  Now draw a triangle on one face,
a square on another, a pentagon on another, and a 9-sided polygon
on the remaining face.  If we exclude these polygonal regions from
their respective faces, then the original faces of the tetrahedron
have 6, 7, 8, and 12 edges, and the excluded regions have 3, 4, 5,
and 9 edges.

Needless to say, these "excluded regions" aren't really distinct
faces, because they reside entirely within the planes of the original
faces.  However, we can fix this by building little pyramids on each
of those drawn polygons.  This creates a large number of new
triangular faces, each of which obviously has three sides.  Now we
can repeat the trick, drawing a 10-sided polygon on one of those
little triangular faces, an 11-sided polygon on another, a 15-sided
polygon on another, and so on.  Then we build little pyramids on
these polygonal bases and repeat the process.

Thus, defining a solid as the limit of this construction process
carried on indefinitely, we have a fractal ornament with infinitely
many faces, no two of which has the same number of edges.  Notice
that, even though each face shares only one edge with each of its
neighbors, this construction evades the earlier proof simply because
it's not a finite construction, i.e., there is no finite integer n
equal to the number of faces.

So, in order for the answer to be no, we need to restrict our
polyhedra to those with a finite number of faces.  The question is
whether there exists a finite polyhedron such that no two faces
have the same number of edges - where "edge" is defined as a maximal
*contiguuous* line segment contained in two specific faces.  Thus,
two faces can share more than one edge.  (Note that a contiguous
line segment counts as more than one edge for a given face if it
intersects more than one other face.)  I'll also assume the surface
has genus 2 for the moment.

Let's say a face is "normal" if it shares exactly one edge with
each of its neighboring faces.  We've seen that if all the faces
of a solid are normal, it's impossible for all of them to have a
different number of edges.  Now let's consider a solid with one or
more non-normal face(s), (as suggested by David Einstein) such as

the same face of neighbor
___    ____
\  \  /   /
\  \/   /
\_____/

This implies the existence of two faces X and Y that are adjacent
over (at least) two separate segments of their common line, as
illustrated below:

Face X

e_________f
c ___/         \
/   d          \
A_______B/                \C__________D
\_______      j__/
l      g\     /  k
\___/
h   i

Face Y

Faces X and Y share the common edges AB and CD, but they do not
connect to each other on the segment BC.  Instead, within the region
bounded by the cycle of vertices BcdefCkjihglB we have a set of
other surfaces.  Let's call a region like this an "anomaly" (borrowed
from crystalography).

Suppose all the surfaces enclosed by X and Y in this anomaly are
normal.  We can then apply our original argument (strengthened by the
fact that no face can have fewer than 3 edges) to show that at least
one of the n faces in this anomaly must have at least n+2 neighbors,
which is impossible because even counting X and Y there are only n+1
available neighbors.

Therefore, we conclude that not all the faces in this anomaly can be
normal, i.e., there must be two faces that share more than one common
edge.  In other words, there must be a (strictly smaller) anomaly
within the anomaly.  We can now repeat the above argument to prove
that THIS smaller anomaly must also contain an anomaly, and so on

This shows again that if we allow the polyhedron to have infinitely
many faces the proof doesn't work - fortunately - because the
theorem is false in that case.  On the other hand, if we consider
only polyhedra with a FINITE number of faces, then we must at some
stage reach an anomaly that is filled with only normal faces, and
so those faces cannot all have a different number of edges.

What about the restriction to surfaces of genus 2?  I imposed that
because of the possibility that for a surface of higher genus an
anomaly might "enclose itself", and thereby allow a finite solution,
if the anomaly contains a "wormhole".  There may be some way to close
this loophole (literally!) for surfaces of higher genus, but I don't
see it at the moment.
"God hath given you one face,
and you make yourself another."
```