A Simple Puzzle

A group of Explorers are traversing a system of Caves when they find a Treasure. In accordance with an agreement that they signed before entering the cave, the Treasure must be divided fairly between them, in such a way that they are each satisfied that they will derive equivalent value from the Treasure.

There are n explorers, where n is greater than 5. The Treasure is composed of a mixed set of jewels (for example 100 rubies, 27 diamonds, and so on) as well as various other items (which will be described later). There are q categories of jewel. The n explorers each have their own unique way of valuing the Treasure, for example, one explorer might be able to sell rubies at $100 per gram, while another explorer might be able to sell rubies at $120 per gram.

Not all of the explorers have reached the chamber in which the Treasure was found, and most of the explorers are still distributed throughout the cave system, which forms a complex network of chambers separated by caves. The explorers who have discovered the Treasure can call back to other explorers, who can then relay their messages to the other explorers in the network. Some explorers are temporarily out of ear shot from other explorers and cannot hear messages or reply to messages. Other explorers can hear messages but cannot reply loudly enough to be heard. No explorers know whether they are hearing all messages that are being transmitted to them, though a simple majority of them assume that they are. Some of the explorers will always transmits their messages perfectly. One of the explorers will always reverse the meaning of any message he receives. Most of the explorers will introduce a small number of errors into the messages they transmit, at a rate of x bits per second. At least 2% of the explorers are capable of using Hamming codes for error correction, but a further 12% of the explorers falsely believe themselves to be capable of using Hamming codes for error correction.

A small prime number of the explorers are using portable radios to listen to radio stations that continually broadcast spot prices for various classes of gems, each in different languages, which the radio holders do not understand, but which can be translated by other explorers within the cave system, and each radio station quotes prices in different currencies. Other explorers are listening to radio stations that continually broadcast international currency exchange rates. One of the radio stations is broadcasting faulty currency prices during the bottom half of each hour.

One of the explorers has decided to visit all other explorers in the network, in order to distribute (and later collect) ballot forms nominating preferences amongst proposed algorithms for distributing the Treasure, but wishes to traverse their locations in an optimal order, without visiting any explorer twice. Most of the explorers are able to estimate their distance to any other explorers they are in contact with, within k percent of the true distance, though a subset of the explorers are boastful and will always report numeric values as being k2 percent larger than their initial estimate, while other explorers are overly humble and will always report numeric values as being k1 percent smaller than their initial estimate.

Included amongst the Treasure is a set of rations, including water, which must be distributed amongst the explorers immediately, if all explorers are to survive. Most explorers want all of the other explorers to survive, although one of the explorers is a psychopath who wishes all of the other explorers to die, leaving the Treasure for her alone, while two of the explorers are nihilists, wishing all of the explorers to die, including the nihilists themselves, and two of the explorers are suicidal, though if they live they will still insist on keeping their share of the Treasure. Some of the rations contain allergens to which it is statistically likely that at least 1 of the explorers will have a possibly-fatal reaction. All of the explorers have flashlights with which they can read the ingredients of the ration packs, though at least p of the rations are mislabelled. The rations can only be consumed by using two forks simultaneously, and the explorers only have a total of three forks between them.

Included amongst the Treasure is a map, divided into a prime number of pieces, which allegedly contains directions to a second, much larger Treasure, located further inside the cave system. Each piece of the map contains, on its obverse, a unique prime number of clues. Due to peculiarities of the way the map and code are constructed, any simple majority of the clues will be sufficient to decode the map, provided the decoder also holds less than three of the diamonds and no rubies. A small prime number of the explorers have sufficient cryptographic knowledge to perform the decoding, while the remainder of the explorers believe they can barter with those who do, and have the decoding performed without giving up more than one third of the second (larger) Treasure. The second Treasure does not exist. Only 1 explorer knows this for sure, though 3 others suspect it with a 20% likelihood.

Also included amongst the Treasure are a set of y personal checks, that can only be cashed by the person they are made out to. The largest check, y1, for yc1 dollars, is made out to Big Jim, who is an acquaintance known to z of the explorers, and they each reason that they can sell the check to Big Jim for a fraction of it's face value (f1...fz). Two of the explorers believe they can conspire together to forge Big Jim's signature. If either conspirator gives up the other, then they will be forgiven while the other conspirator will be cut out of their share of the Treasure (resulting in a bigger share for the everyone, including the confessor). If both conspirators confess then both will be cut out of the Treasure. They have been in this situation many times before and carry forward a lengthy, though unknowable, series of grudges, g1..gj. The remaining y-1 checks are similarly constrained.

Although each explorer is keen to maximise their share of the Treasure, they are all constrained by their respective and varying abilities to remove their share of the Treasure. Each explorer has a unique maximum weight that they can carry (the sum of all maximum weights may not be greater than the total mass of the Treasure) and each explorer will carry their share of the loot distributed in 1 or more knapsacks that each have a unique maximum volume.

Question: What is the most optimal strategy that ensures a maximally satisfactory division of the Treasure, that can be computed in no worse than O(n log n k f z j p q) time, assuming that the only computational device available for the task is a 68HC11 microcontroller, with a faulty Y index register, limited battery life and no apparent input device. You also have two matches.

Addendum

From Dr Richard Mason:

In 2016 Dr Bambrick proposed the first NP-Ridiculous problem. Solving it would end up consuming the remainder of his sanity, though very little of this remained after formulating the problem.

wiki.secretGeek

A Simple Puzzle

Addendum

External links

See also