Ponder This

March 2025 - Challenge

<< February March

This puzzle was suggested by Hugo Pfoertner - thanks Hugo!

Given a finite, nondirected graph (allowing multiple edges between two vertices), we can think of it as an electric network where each vertex is a node, and each edge is a resistor. Assume all edges in the graph have the same resistance R. It is a well-known problem to compute the resistance between any two nodes in the graph.

Given n, we want to find a graph that has n specified vertices, such that all the resistances between those vertices are distinct. Note that the graph can have additional vertices that are not part of those counted in n (but still influence the resistances between vertices). As an example, consider the following graph:

In this graph, the resistances between vertices 1\ldots 5, given R=47, are [19, 20, 31, 33, 35, 39, 40, 45, 46, 52], giving 10=\frac{n(n-1)}{2} distinct values, as required. This graph has one additional node, and a total of 9 edges (which is non-optimal: the optimal number is 8). The graph can be described by the list

[(1, 6), (1,4), (2,5), (2,6), (3,5), (3,5), (3,6), (4,5), (4,5)]    

Where the implicit assumption is that the vertices 1,2,\ldots ,n are the ones whose resistances are measured, and the rest are additional vertices.

We impose on the graph the constraint that no vertex may be connected to only one neighbor.

Your goal: For n=10, find a graph with the minimal number of edges such that between nodes 1,\ldots,10 we have 45 distinct resistances. Supply your result as a list of edges as in the above example.

A bonus "*" will be given for solving the problem for n=12 (66 distinct resistances), finding all 3 solutions to the problem where the graph is planar and also finding one non-planar solution.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com