This month's riddle comes from Oded Margalit, who describes it as
"a well known design problem".
In graph theory, a pair <V,E> is called a graph
if V is a set of vertices and E is a set of edges between
those vertices. An edge is described by the pair of vertices it connects.
A subgraph <V',E'> of a
graph <V,E> is a graph satisfying that V' is a
subset of V and E' is a subset of E.
This month's riddle relates to the following problem:
We do not request a solution for a general <m,n> pair,
but rather want to consider certain specific values of m and n.
The names of solvers who will prove correctly for at least 3 of the 5 pairs will be posted. (They don't necessarily need to be the first three pairs.) Separate lists will be maintained for solvers who proved for 3, 4 and all 5 pairs. As a bonus question, try to give an exact characterization for which n the pair <3,n> can be partitioned. |
List of solvers:Three pairs:Or Sheffet (9 September 17:50)Four pairs:Five pairs:Alon Amit (15 September 16:20) |
Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!