Challenge

Sasha Pachev sasha at asksasha.com
Tue Nov 24 13:36:29 MST 2009


>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.

CRC sum is not commutative. Counter-example:

 mysql> select crc32('ab'),crc32('ba')\G
*************************** 1. row ***************************
crc32('ab'): 2659403885
crc32('ba'): 749160980
1 row in set (0.00 sec)

Thus the CRC sum of the tags will vary when you change the order of scanning.

And, if you were allowed to force the sheep to go through the gate in
tag order, the solution would be trivial - just look for the tag
difference between two adjacent sheep  > 1.

You are on the right track, though. You need a second operator f(x,y)
that has the following properties:

 * commutative: f(a,b) = f(b,a)
 * associative:  f(a,f(b,c)) = f(f(a,b),c)
 * equation f(x,S-x) = P has no more than two solutions. If it does
have two and q is a solution, then S-q is the other solution.
 * computable with a 32-bit processor for all numbers 1 through 10000
without allocating memory

Hint. Multiplication possesses all of the above properties except the
last one. Can we fix it without breaking the other three properties?

-- 
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