Ramsey partitions of integers and fair divisions

Abstract

Ifk₁ andk₂ are positive integers, the partitionP = (α₁,α₂,...,α_n) ofk₁+k₂ is said to be a Ramsey partition for the pairk₁,k₂ if for any sublistL ofP, either there is a sublist ofL which sums tok₁ or a sublist ofP −L which sums tok₂. Properties of Ramsey partitions are discussed. In particular it is shown that there is a unique Ramsey partition fork₁,k₂ having the smallest numbern of terms, and in this casen is one more than the sum of the quotients in the Euclidean algorithm fork₁ andk₂.

An application of Ramsey partitions to the following fair division problem is also discussed: Suppose two persons are to divide a cake fairly in the ratiok₁∶k₂. This can be done trivially usingk₁+k₂-1 cuts. However, every Ramsey partition ofk₁+k₂ also yields a fair division algorithm. This method yields fewer cuts except whenk₁=1 andk₂=1, 2 or 4.