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

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.