3 ms·
> Suppose, for instance, that a kindergartner named Alice has two apples, but she prefers oranges. Fortunately, her classmates have developed a healthy fruit-tr
by itishappy 3y ago
> Suppose, for instance, that a kindergartner named Alice has two apples, but she prefers oranges. Fortunately, her classmates have developed a healthy fruit-trading system with strictly enforced exchange rates: Give up an apple, say, and you can get a banana. Can Alice execute a series of trades, by picking up and offloading bananas or cantaloupes, that gets her to her favorite fruit?
- not2b 3y agoI think the GP was asking for more detail than that. We have a dimension n. We have a set of vectors, each with n integer components. In the fruit-trading problem these represent legal trades. We have a starting state, with n non-negative integers. To do a "trade" we select one of the vectors in the set and add it component by component. The result must be non-negative (each component). The question to answer is whether, from a given starting state, we can reach a given ending state. The result here is that solving this reachability problem can be hellishly complex.