nick at leippe.com
Sat Nov 21 12:26:12 MST 2009
On Sat, Nov 21, 2009 at 12:09 PM, Sasha Pachev <sasha at asksasha.com> 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
> 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
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.
More information about the PLUG