wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The cursed engineer puzzle
        
(Message started by: Wonderer on Apr 19^th, 2007, 7:39pm)

Title: The cursed engineer puzzle
Post by Wonderer on Apr 19^th, 2007, 7:39pm

I am running a company that mainly produces key-sets (each key-set contains a lock and its key). My engineer recently designed one type of key-sets and here’s the design spec.:
1 Each key-set’s key has exactly 5 teeth
2 Each tooth is given a number (from 1,2,3,4,5,6), represents the hight of the tooth
3 Each key has teeth of at least 3 different hights
4 No two adjacent teeth can have a difference in hight of 5 (i.e. 1 & 6 can not be next to each other)
5 And of course, no two keys are the same
6 A unique lock is then paired to each key to form a key-set. (Because, as one would expect, one key should open one lock only)
7 The key-set is then marked with a symbol that represents its teeth. (e.g. 4 6 3 3 1, or 5 1 4 2 5 …)

After 2 months of hard work, we produced one batch of such key-sets containing ALL POSSIBBLE key-sets that match the design spec.. We randomly packed all these key-sets into boxes, 60 per box. And we put them on sale (we only sell key-sets to big customers who buy whole boxes of them).

Last night my engineer came to me and told me that after some revision, he found a design flaw in this batch of key-sets we just produced. Though I deeply cursed him in my heart, I asked him nicely what the design flaw and the consequence were. To which, he replied that, in this batch, some locks could now be opened by more than one key. ‘Oh, lucky we haven’t sold any of these key-sets yet. But what should I do? Just throw them away?’ I asked. ‘This is not necessary, let me explain’ , My engineer told me that after his careful calculation he found the pattern of different keys unlocking the same lock!

If two keys have 4 corresponding teeth of the same hight and the differing pair of teeth has a difference of 1 in their hight, then both keys can open both locks.
For example 1
Key A has teeth: 5 3 2 1 4 - Opens lock A
Key B has teeth: 5 4 2 1 4 - Opens lock B
Since only the second tooth from each key is different and the difference is only by 1, then Key A can also open lock B and Key B can open lock A!

Example 2:
Key A has teeth: 6 2 5 4 4 - Opens lock A
Key B has teeth: 6 2 5 5 4 - Opens lock B
In this case, only the fourth tooth from each key is different and the difference is 1, then key A can open lock B and key B can open lock A!

After explaining the pattern, my engineer said, ‘All we need to do is design a way to repack these key-sets (still 60 per box), label the boxes and utilise the labelling system when you sell the key-sets. If done properly, will minimise or eliminate (maybe) the possibility of multiple keys opening the same lock. i.e. try not to sell the same customer key-sets that will cause problem.’

‘Well, are you going to help me with it?’ I asked.
‘I am only a lock-smith engineer, boss.’
‘You are fired!’

OK, here comes the questions:
A)How many key-sets were produced in this batch?
B)Design a way, including how to pack (must be 60 per box), how to label the boxes and how to sell the key-sets in order to minimise or, even better, eliminate the possibility of causing problems.
C)According to your design in Question B, what is the maximum number of boxes a customer can buy, that you can guarantee no locks can be opened by more then one key?

(as English is not my first language, please excuse me if the question causes any confusion, I will try my best to explain)

Title: Re: The cursed engineer puzzle
Post by Grimbal on Apr 20^th, 2007, 3:13am

A) [hide] I don't know, 6000+ [/hide]
B) [hide] use parity. Sum the digits, don't pack even sums with odd sums. Label the boxes by parity. Sell only one parity to one customer.[/hide]
C) [hide]Half of the boxes[/hide]