On Sat, Nov 21, 2009 at 12:09 PM, Sasha Pachev <[email protected]> wrote: > Now another challenge. A while ago we had the lost sheep problem. For > those who do not remember - we have 10,000 sheep with scannable ID > tags from 1 to 10000. We assume that we are able to quickly scan all > of the tags and do so only once (e.g the sheep go through a revolving > gate that turns only one way and scans them as they go through). > > We have a CPU that is capable of arithmetic operations on 32-bit > integers with no RAM that we can allocate or write to. The > restriction comes, let's say, due to the need to reduce the cost of > the system for the Kenyan farmers. > > When a sheep is lost, if we can quickly identify its number, we are > able to contact its GPS unit, obtain its coordinates, and come to its > rescue. However, if the number of the sheep is not known we are not > able to poll all of the sheep due to prohibitive levels of power > consumption. > > In the original problem only one sheep was lost, and the solution was > to sum the available tags and subtract that from 10001*500, which is > the sum of all numbers from 1 to 10000. > > Now let's through a nasty twist. Our farmers sometimes lose two sheep > instead of one. Suppose two sheep are missing. Can you identify them?
I believe this can be done by introducing a second operation for comparison--I'd suggest a CRC. Just as in the first solution for a single lost sheep, subtracting the observed sum from 10001*500 yields the sum of the two missing sheep's tags. Now what's left is completing the CRC addition at most 9999 times, (each time testing a different pair of potentially lost sheep--the first number chosen constrains the second one because of the sum), and find the pair that results in the CRC being satisfied. /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
