© Friederike Hofmann, MATH+
Author: Tobias Paul (HU Berlin)
Project: EF 4-7
Challenge
To foster creative freedom in gift-giving, Santa Claus has introduced a new system: each gift consists of individual parts and is intended to be assembled freely by the Christmas elves. At the beginning, each elf receives one component of the large gift. To connect the pieces appropriately, the elves scurry around in a chaotic manner. With n elves present, it takes 1/(n(n-1)) days for two elves with matching parts to find each other. Once two elves have found each other, they immediately assemble their parts. Right after that, one of the two elves collects his wages from Santa Claus and then disappears into a well-deserved evening. The other elf now keeps the larger piece and continues searching in the commotion for matching parts. After that, n-1 elves are left and they repeat the analogous procedure where it takes 1/((n-1)(n-2)) days for some two matching elves to find each other. This process continues until the last two (by now very large) pieces become the finished gift, and the last two elves are allowed to leave.
Of course, Santa Claus must ensure that the gifts are completed on time. Additionally, he needs to know how high his labor costs per gift can be for the budget. According to the collective agreement, a compensation of one cookie per day is agreed upon for each elf, with the amount paid out to the exact crumb. As the demands for the gifts continue to grow, requiring more and more individual parts, he wants to set up a universal framework for gift assembling. Namely, he would like to find numbers d and c such that
(a) any gift, regardless of the number of pieces it is made of, can be assembled in d days
(b) any gift, regardless of the number of pieces it is made of, costs at most c cookies.
At the moment, Santa is not sure if such values d and c exist, but if they do, Santa would like them to be as small as possible. Can you help Santa find the answer, i.e., find the minimal such d and c (if they exist)?
Possible Answers:
- d=0.5 and c=1
- d=0.5 and c=2
- d=0.5 and c can’t be found
- d=1 and c=1
- d=1 and c=2
- d=1 and c can’t be found
- d=2 and c=1
- d=2 and c=2
- d=2 and c can’t be found
- both d and c can’t be found
Project Reference
The described process is called a coalescent process. In this process, two particles merge to form a larger one. In this example, it involves the Kingman coalescent with a slightly adjusted merging rate. In biology, the coalescent describes the genealogy of a subpopulation. The time until the last coalescence is then the time until the most recent common ancestor. In task part (a), we thus observe how long it takes for the most recent common ancestor to be reached for any arbitrarily large subpopulation. Part (b) then deals with the total sum of the so-called branch lengths.