7
$\begingroup$

Inspired by the three utilities puzzle from prog_SAHIL I'm now posting a similar puzzle that makes use of the topology of a cup with a handle:
https://upload.wikimedia.org/wikipedia/commons/2/26/Mug_and_Torus_morph.gif
The question is:

How many distinct points can you draw on the surface of this cup, such that it is possible to connect each point with all other points pairwise without any connections crossing each other (or one of the points)?

For example if you have 4 points the connections could look like this:

$\endgroup$
1
  • 1
    $\begingroup$ I may be getting pretty close spamming, but since the utilities mug in the linked puzzle was from these same guys, here’s another of their mugs that solves this puzzle. $\endgroup$
    – Bass
    Jan 1, 2018 at 11:24

2 Answers 2

7
$\begingroup$

This is topologically equivalent to a torus, and you can go up to 7 points:

enter image description here

as shown by this Math.SE answer.

The diagram for this could look for example like this:


In this picture the lines going "under" the square represent connections going through the cup handle and the lines going "over" the square would go along the handle of the cup.

One can also just look up the answer if you know the question asks for the complete graph $K_n$ of degree $n$ with maximum $n$ such that the graph genus $\gamma (K_n)$ is at most $1$. Then

if you take the equation from Wolfram MathWorld $$ \gamma (K_n) = \left\lceil \frac{(n-3)(n-4)}{12} \right\rceil $$ you see that the genus $\gamma (K_n) \le 1$ as long as $n \le 7$.

$\endgroup$
2
  • $\begingroup$ Wow, now I understand all those people complaining in this meta-post. Could you add some explanation on the image you provided, or eventually a 2D representation of the diagram? It's not that complicated, actually. $\endgroup$
    – A. P.
    Dec 30, 2017 at 22:21
  • $\begingroup$ One might add that it's not so hard to show that this is the best one can do. Let $F$, $E$, and $V$ be the number of faces, edges and vertices determined by the arrangement. In any embedding with a maximal number of edges, one has that every face is a triangle, so $3F=2E$. The Euler characteristic of a torus provides that $F-E+V=0$. Therefore, graphs with a maximal amount of edges satisfy $3V-E=0$; in other words, $E\leq 3V$ for every toroidal graph. However, we are asked to have ${V \choose 2}$ edge, which is greater than $3V$ whenever $V>7$. $\endgroup$ Dec 31, 2017 at 16:22
10
$\begingroup$

Deusovi has already shown why the answer must be what it is, but there's one thing that can still be added to the answer. That is, actually drawing this many points on an actual cup. While I've already done just that (it was years ago), I have no visual proof that I actually did. So, a 3D render will have to do.

left side right side

Here's the same cup without its handle:

no handle

Blender model: https://github.com/honnza/drops/blob/master/K7cup.blend.gz

Background image licensed to http://hdrvfx.com under CC-BY-SA and available for download from http://www.hdrlabs.com/sibl/archive.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.