Challenge

Sasha Pachev sasha at asksasha.com
Sat Nov 21 12:09:14 MST 2009


To clarify, 15 and 17 were decimal numbers, so 0xf and 0x11.

My son (he is 10 and his name is Benjamin) figured out divisibility by
0xf after a hint "What is 16 mod 15?", and then figured out
divisibility by 0x11 on his own having noticed it behaves just like
divisibility by decimal 11 for decimal numbers (some of digits in odd
positions is equal to the some of digits in the even positions in mod
11 ).

I believe Shane gets the award for the solution.

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?

-- 
Sasha Pachev
AskSasha Linux Consulting
http://asksasha.com

Fast Running Blog.
http://fastrunningblog.com
Run. Blog. Improve. Repeat.



More information about the PLUG mailing list