10
$\begingroup$

Label the vertices of this graph with positive integers (repetitions allowed) whose sum is 100 in such a way that any pair of vertices are joined by an edge if (and only if) they have labels with a common divisor greater than 1 (i.e. they are not relatively prime).

A partition of 100 and its divisor graph

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Do the pairs not on the same line have to be relatively prime? If not, you can just write 10 on all the dots. $\endgroup$
    – Nautilus
    Commented Apr 15, 2017 at 14:19
  • 1
    $\begingroup$ If I'm interpreting the question right, why can't I just fill all connected vertices with twos, and assign integers to the lone vertices to make the sum 100? $\endgroup$
    – greenturtle3141
    Commented Apr 15, 2017 at 14:19
  • 1
    $\begingroup$ I have clarified the issue. $\endgroup$
    – Bernardo Recamán Santos
    Commented Apr 15, 2017 at 14:25

1 Answer 1

Reset to default
10
$\begingroup$

My solution:

enter image description here

In text, that is represented as:

Starting from the lonely vertices and working clockwise: $1, 1, 42, 30, 7, 6, 5, 3, 3, 2$. For convenience, let us label these vertices A, B, C, D, E, F, G, H, I, J.

Logic

  • For every $K_n$ subgraph (set of n vertices in which all vertices are connected to each other), it's vertices must all share a unique prime factor that no other vertex outside this set has (Edit: OK this isn't always true, but it does help to use each prime to fill in each $K_n$).
  • Notice the $K_5$ subgraph (CDFHI). To minimize the sum, assign a factor of $2$ to each.
  • Then, each vertex of the nearby $K_4$ (CDFJ) can be assigned factor of $3$, and the two $K_2$s (DG, CE) factors of $5$, and $7$, in some order (It won't matter: C and D are both part of the $K_5$ and $K_4$).
  • This gives a sum of $97$, but we cannot get to $100$ with the last two vertices.
  • Trying another path, we give the $K_5$ vertices a factor of $3$ instead, and the $K_4$ a factor of $2$.
  • This bumps the sum to $98$, where we can now assign $1$s to the lone remaining vertices.
Improve this answer
$\endgroup$
3
  • $\begingroup$ "For every K_n subgraph (set of n vertices in which all vertices are connected to each other), it's vertices must all share a unique prime factor that no other vertex outside this set has." is not true. Consider a graph with vertices 6, 10, 15. Each prime generates a clique, but a clique doesn't necessarily share a prime. $\endgroup$
    – Peter Taylor
    Commented Apr 15, 2017 at 23:17
  • $\begingroup$ @Peter Taylor Yeah I forgot to consider that. $\endgroup$
    – greenturtle3141
    Commented Apr 15, 2017 at 23:27
  • $\begingroup$ The only other solution swaps $5\leftrightarrow 7$ and $30\leftrightarrow 42$. $\endgroup$
    – RobPratt
    Commented Dec 22, 2023 at 23:32

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