9
$\begingroup$

The sum of 10 numbers, not necessarily distinct, is 50. When placed appropriately in the circles of this diagram, any two numbers will be joined by a line if, and only if, they have a common divisor greater than 1.

A partition of 50 into ten parts

What are those ten numbers?

How many other partitions of 50 (or, in general, of N) can be uniquely recovered from its corresponding graph of common divisors, that is, the simple graph whose vertex set is the set of parts, two of of which are joined by an edge if, and only if, they have a common factor greater than 1?

$\endgroup$
  • 1
    $\begingroup$ An immediate observation is that the lone vertex must be odd. If it were even, then no other vertex woud be even, so we'd have $9$ odd numbers and a single even number, the sum of which must be odd (and $50$ is even). $\endgroup$ – Fimpellizieri May 8 '17 at 4:59
  • $\begingroup$ @Fimpellizieri How do you know that if the lone vertex were even, the rest are not even? $\endgroup$ – Arby May 8 '17 at 5:05
  • 1
    $\begingroup$ @Arby: Because any even number would share a common factor (namely, $2$) with that vertex and would then be connected by an edge. $\endgroup$ – Brian Tung May 8 '17 at 5:10
  • 1
    $\begingroup$ OP: It might be worth pointing out that the numbers do not have to be distinct (in fact, in this case, cannot be distinct). $\endgroup$ – Brian Tung May 8 '17 at 5:12
  • $\begingroup$ @BrianTung Thanks for being gentle with me in my senior moment. :) $\endgroup$ – Arby May 8 '17 at 5:20
1
$\begingroup$

Try a couple of random assignments of numbers to the graph that satisfy the graph structure. Observe that they tend to sum to greater than $50$. So your strategy should be to use numbers that are as small as possible, repeating the smallest numbers as many times as possible.

Hint 1: Start by determining the only place(s) where you can place a $1$.

Hint 2: In a sum of any $10$ numbers to $50$, there must be an even number of even numbers. Where can they go?

Hint 3: Now apportion the odd primes $3$, $5$, and $7$ greedily, placing the smaller primes in the larger groups. What result do you get?

The generalized question seems very hard. Consider asking for a separate question for upper and lower bounds?

$\endgroup$
  • 1
    $\begingroup$ One of the better answers I've seen on Stackexchange. Gives the answer, but you have to work for it a bit. Very nice. $\endgroup$ – Arby May 8 '17 at 5:16

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.