About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
March 2025 - Challenge
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 . It is a well-known problem to compute the resistance between any two nodes in the graph.
Given , we want to find a graph that has
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
(but still influence the resistances between vertices). As an example, consider the following graph:
In this graph, the resistances between vertices , given
, are
, giving
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 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 , find a graph with the minimal number of edges such that between nodes
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 (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
Challenge:
02/03/2025 @ 11:35 AM EST
Solution:
05/04/2025 @ 12:00 AM EST
List Updated:
02/03/2025 @ 17:20 PM EST