Problem of the Week 1239
Uniquely Unique Partitions
Solution
The answer is 15. Every N except 2 and 3 has at least one recoverable partition (22...2 or 22...21). The count of the number of recoverable partitions, starting with 1, is this:
1,0,0,1,1,1,1,1,1,2,1,2,1,2,1,2,3,3,3,3,2,2,3,3,4,4,5,6,4,5,4,5,4
The last 1 occurs at N = 15, and it appears that the last 2 occurs at N = 22, and the last 3 at N = 24. For future investigation: Prove that, for every M, the number of recoverable partition of N is, for sufficiently large N, greater than M.
The idea of the proof is to exhibit, as N rises, two examples of recoverable partitions. The task is aided by first computing a list of the recoverables, but some of the solvers did the entire problem using only hand computation. It is tricky to get a solid proof. Here is a proof that accounts for every detail.
All partitions are of positive integers into positive integers. A "clique" is a complete graph. Here 222 is used for 2 + 2 + 2, etc; B(x) denotes Binomial[x,2] = x(x − 1)/2.
Definition. The "graph" of a partition has the parts as vertices and edges between two when they are not relatively prime; a partition of n is "recoverable" if knowledge of n and of the edge count of its graph determines the partition.
Theorem. (Barrera, Liptak, Recaman, and Wagon)
(a) If n ≥ 4 and n is even, 22...2 is recoverable.
(b) If n ≥ 5 and n is odd, then 22...21 is recoverable (also if n = 1)
(c) If n ≥ 10 and n is even, 3322...2 is recoverable.
(d) If n ≥ 17 and n is odd, then 33322...2 is recoverable.
So if n is even and n ≥ 10, or n is odd and n ≥ 17, there are at least two recoverable partitions. The recoverable count, for evens from 2 to 24, is
0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 2, 3
So this is not monotone (the 2 at n = 22). Similarly for odds it is not monotonic.
Corollary. The largest n having only one recoverable partition is 15. More precisely: The only values of n for which there is a unique recoverable partition are 1, 4, 5, 6, 7, 8, 9, 11, 13, and 15.
Proof. To prove the part of this that does not follow from the Theorem, one can simply compute all the partitions of any n ≤ 15.
Proof of Theorem. We use "trivial" for a partition entry equal to 1, "large" for an entry that is 3 or larger.
(a) The graph of 22...2 using m 2s is complete. No other partition can have m nontrivial entries, so all others have smaller edge count.
(b) The graph of 22...21 using m 2s is complete with an additional isolated vertex. The only other partition with m nontrivial entries is 22...23, with a smaller edge count.
(c) R = 22...233 has m 2s, where 2m + 6 = n (so m + 3 bounds the number of nontrivial entries in any partition), and has edge count B(m) + 1. A partition with clique number larger than m will have more edges than R, because n = 6 and 8 are the only values for which B(m + 1) ≤ B(m) + 1 and we have n ≥ 10. This assertion follows from the identity B(m + 1) − (B(m) + 1) = m − 1.
If p is a partition having the same edge-count as R, then p must have m + 1, m + 2, or m + 3 nontrivial entries.
m + 3: there can be no large entries and 22....2 gives a too-large complete graph.
m + 2: the number of large entries can be only 0, 1, or 2. The first two cases lead to a too-large complete graph. The last case requires a partition of 6 having two entries greater than 2. That must be 3 + 3, which gives R.
m + 1: the number of large entries can be at most 4. Therefore there are at least (m − 3) 2s. This means that 2 + 2 + 2 + 3 + 3 = 12 remains to be distributed, so we will list all the partitions of 12 into 4 nontrivial entries. If the 4 numbers are all even, then we have an m + 1 clique, which is too large. So there are only five relevant partitions of 12, shown below with all 1s deleted as they are irrelevant and also 5s deleted (also singleton 3s) as they are isolated vertices; also any 4 has been replaced by a 2 + 1 + 1 (and the 1s then deleted), since that has no effect on the graph. p is obtained by appending each of these six to (m − 3) 2s.
|
{2,2}, {2,2,3,3}
|
|
smaller number of 2s, so smaller edge count
|
|
{2,2,2}
|
|
no 3s, so smaller edge count
|
|
{3,3,3,3}
|
|
edge difference with B(m) + 1 is 3m − 11, which cannot be 0
|
|
{2,3,3,3}
|
|
edge difference 2m − 5, which cannot be 0
|
For the last two, the edge counts are B(m − 3) + B(4) and B(m − 2) + B(3). For these two, the edge difference from R reduces to 3m − 11 and 2m − 5, respectively, and these cannot vanish.
(d) R = 22...2333 has m 2s, where 2m + 9 = n; so m ≥ 4 and m + 4 is a bound on the nontrivial count of any partition. The edge count of R is B(m) + 3. A partition with clique number larger than m will have more edges than R, because n = 9, 11, 13, and 15 are the only values for which B(m + 1) ≤ B(m) + 3, and we have n ≥ 17. This assertion follows from the identity B(m + 1) − (B(m) + 3) = m − 3.
If p is a partition having the same edge-count as R, then p must have m + 1, m + 2, m + 3 or m + 4 nontrivial entries.
m + 4: there can be no large entries and 22....21 gives a too-large complete graph.
m + 3: the number of large entries can be only 0, 1, 2, or 3. The first three cases lead to a too-large complete graph. The last case requires a partition of 9 with three large entries. That must be 3 + 3 + 3, which gives R.
m + 2: the number of large entries is most 5, so there are at least (m − 3) 2s. This leaves 3 + 3 + 3 + 2 + 2 + 2 = 15 to be distributed among the 7 spots. There are nine relevant partitions of 15, where isolated vertices are deleted, and any 4 or 8 is replaced by a 2; p is obtained by appending each of these to (m − 3) 2s.
|
{2,2,2,2}, {2,2,2,6,3}, {2,2,2,2}
|
|
too-large cliques (m − 3 + 4 = m + 1)
|
|
{2,2,3,3}, {2,2,2}, {2,2,3,3,3}, {2,2,2,3,3}
|
|
fewer 2s or fewer 3s; smaller edge count
|
|
{3,3,3,3,3}
|
|
B[m − 3] + B[5] − (B[m] + 3) = 13 − 3m, which cannot be 0
|
|
{2,3,3,3,3}
|
|
B[m − 2] + B[4] − (B[m] + 3) = 6 − 2m, which vanishes only if m is 3. But we assume m ≥ 4.
|
m + 1: Like the preceding case with 7 replacing 5, m − 6 replacing m − 3, and 21 replacing 15. The relevant partitions of 21 are 19 in number (with deletions as in the other cases) where p is obtained by appending each of these to (m − 6) 2s.
|
{2,2,2,2,2,2}, {2,2,2,2,2,2}, {2,2,2,2,2,3,6}, {2,2,2,2,2,2}, {2,2,2,2,2,6}
|
|
same number evens as R, but fewer edges overall
|
|
{2,2,2,2,2}, {2,2,2,2,3,3,6},{2,2,2,2,2,5,5}, {2,2,2,2,2,3,3}
|
|
five evens, fewer of others
|
|
{2,2,2,2,3,3},,{2,2,2,2,5,5}, {2,2,2,2,3,3,3}
|
|
four evens, fewer or same of others
|
|
{2,2,2,3,3,3}
|
|
three evens, fewer edges
|
These next have more 3s so more analysis is needed. But it works.
|
{2,2,2,3,3,3,3}
|
|
edge count is B(m − 3) + B(4)
|
|
{3,3,3,3,3,3,3}
|
|
edge count is B(m − 6) + B(7)
|
|
{2,3,3,3,3,3,3}
|
|
edge count is B(m − 5) + B(6)
|
|
{2,2,3,3,3,3,3}
|
|
edge count is B(m − 4) + B(5)
|
|
{2,2,3,3,3,3}
|
|
edge count is B(m − 4) + B(4)
|
|
{2,2,2,3,3,3,6}
|
|
edge count is B[m -3] + B[3] + m
|
The difference between the edge counts above and the edge count of R are 3(-3 + m), -39 + 6m, -27 + 5m, -17 + 4m, -13 + 4m, and 2(-3 + m), none of which vanish when m ≥ 4.
Here is complete Mathematica code to generate the recoverable partitions.
edgeCount[p_]:=Length[Select[Subsets[p,{2}],GCD@@# ≥ 2&]]
RecoverableQ[p_]:=(ec=edgeCount[p];1==Length[Select[IntegerPartitions[Total[p]],edgeCount[#]==ec&,2]]);
Column[Table[{n,Select[IntegerPartitions[n],RecoverableQ]},{n,20}]]
[Back to Problem 1239]
© Copyright 2017 Stan Wagon. Reproduced with permission.
|