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

$\endgroup$
  • 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 Apr 15 '17 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 Apr 15 '17 at 14:19
  • 1
    $\begingroup$ I have clarified the issue. $\endgroup$ – Bernardo Recamán Santos Apr 15 '17 at 14:25
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.
$\endgroup$
  • $\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 Apr 15 '17 at 23:17
  • $\begingroup$ @Peter Taylor Yeah I forgot to consider that. $\endgroup$ – greenturtle3141 Apr 15 '17 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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