ISSN:
1439-6912
Keywords:
05 A 17
;
05 D 10
;
11 P 81
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Ifk 1 andk 2 are positive integers, the partitionP = (α1,α2,...,α n ) ofk 1+k 2 is said to be a Ramsey partition for the pairk 1,k 2 if for any sublistL ofP, either there is a sublist ofL which sums tok 1 or a sublist ofP −L which sums tok 2. Properties of Ramsey partitions are discussed. In particular it is shown that there is a unique Ramsey partition fork 1,k 2 having the smallest numbern of terms, and in this casen is one more than the sum of the quotients in the Euclidean algorithm fork 1 andk 2. 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 1∶k 2. This can be done trivially usingk 1+k 2-1 cuts. However, every Ramsey partition ofk 1+k 2 also yields a fair division algorithm. This method yields fewer cuts except whenk 1=1 andk 2=1, 2 or 4.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01204722
Permalink
