2
$\begingroup$

In this paper by Ronald Graham, the theorem that every integer greater than 77 has a partition with the property that the sum of the reciprocals of the various "piles" in the partition is 1 (lovely!).

He gives a proof of this which is remarkably short but I find difficult to follow. He demonstrates that all the integers from 78 to 333 inclusive have such a representation and then demonstrates 2 transforms on a sum of reciprocals that add to 1 that retain this property, but which increase the sum of denominators from $U$ to $2U+2$ and $2U+179$.

He then essentially claims that by having a certain property (the above one) hold for all the integers from 78 to 333 and by knowing that the above transforms retain the property, it holds for all integers greater than 77. However, his method of explaining this is quite incomprehensible to me and appears to contain numerous arithmetic errors on top of this!

Can someone either give an alternative proof of the fact using what I've mentioned or simply explain Graham's argument, as it is a wonderful theorem?

$\endgroup$
  • 1
    $\begingroup$ The "piles" in a partition are surprisingly called "parts". $\endgroup$ – Marc van Leeuwen Jan 16 at 14:39
2
$\begingroup$

What a wonderful theorem indeed :)

You can prove this easily by strong induction. The base case of $78\leq n\leq333$ has been handled. Assume the theorem holds for all $78\leq n\leq m$, $m\geq333$. Then $m+1=2k$ or $m+1=2k+1$ for some natural number $k$.

Case $m+1=2k$: Let $U=k-1$. Then $U\leq m$ and $U=(m-1)/2\geq(333-1)/2\geq78$, so the theorem holds for $U$. Hence, the theorem holds for $m+1=2U+2$.

Case $m+1=2k+1$: Let $U=k-89$. Then $U\leq m$ and $U=(m-178)/2\geq(333-178)/2=77\frac12$. Because $U$ is an integer, $U\geq78$, so the theorem holds for $U$. Hence, the theorem holds for $m+1=2U+179$.

$\endgroup$
  • $\begingroup$ Thank you very much! You must agree that Graham's explanation leaves something to be desired... $\endgroup$ – Isky Mathews Jan 4 at 9:47

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.