6
$\begingroup$

There are about $9.266 \times 10^{45}$ partitions of 2024, a handful! To each of these partitions corresponds a graph in which the vertices are each of the parts, two of which are joined by an edge if they are not relatively prime (i.e. they have a common factor greater than 1).

i) Find a graph (other than the graph with a single vertex and any other empty graph, that is, with no edges) such that there is a unique partition of 2024 that corresponds (in the above way) to this graph.

ii) What is the least number (greater than 1) of nodes such a graph can have?

Improve this question
$\endgroup$
2
  • $\begingroup$ While not easy, I don't see this as a puzzle. It's a math problem. $\endgroup$
    – Chris Cudmore
    Commented Dec 22, 2023 at 20:10
  • $\begingroup$ @ChrisCudmore Feels more like a math puzzle to me, but that's of course just me assuming that there's a clever way to solve this. $\endgroup$
    – Bass
    Commented Dec 23, 2023 at 1:49

2 Answers 2

Reset to default
5
$\begingroup$

I'm not convinced this is optimal, but I think this satisfies part i:

The partition $2+3+5+7+11+6+10+30+42+66+70+210+330+462+770$ induces a graph with a unique partition. This has 15 nodes.

Why is the partition unique?

This partition consists of the five smallest primes, the two smallest 2-way products of those primes, the four smallest 3-way products of those primes, and the four smallest 4-way products of those primes. Any other partition (even if it is a partition of a different number) that generates this graph, then, would have to use larger primes, larger n-way products, or extra factors; and thus it would sum to something larger than 2024. (It is still possible to be a unique minimum even without using strictly the smallest n-way products in all cases. It is probably possible to omit some of the individual primes in certain cases as well, but these things make the argument more complicated.)

Improve this answer
$\endgroup$
0
2
$\begingroup$

Here is tehtmi's unlabelled graph (courtesy of Freddy Barrera):

enter image description here

And here it is with labels:

enter image description here

Improve this answer
$\endgroup$

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