wu :: forums - Print Page


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

        riddles >> medium >> Faulty Combination Lock
        
(Message started by: ThudanBlunder on Jun 11^th, 2008, 5:54am)

Title: Faulty Combination Lock
Post by ThudanBlunder on Jun 11^th, 2008, 5:54am

A combination lock with three dials, each numbered 1 to 8, is defective in that you need to get only two of the numbers right to open the lock.
What is the minimum number of three-number combinations you need to try in order to be sure of opening the lock?

Title: Re: Faulty Combination Lock
Post by SMQ on Jun 11^th, 2008, 6:56am

Well, some bounds to start with: not less than [hide]24, as each trial tests 22 combinations and 512/22 > 23[/hide], and not more than [hide]38, as the following sequence (found by computer program w/ greedy algorithm) will always open the lock: 111 123 132 178 187 213 222 227 228 231 272 282 312 321 333 337 338 373 383 444 456 465 546 555 564 645 654 666 718 722 733 777 781 817 822 833 871 888[/hide], but there's still quite a bit of room for improvement within those bounds.

--SMQ

Title: Re: Faulty Combination Lock
Post by Grimbal on Jun 11^th, 2008, 11:54am

I believe it is the exact same problem as here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1064517916) and was already discussed here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1109913027)

[hide]
The upper bound would be 32 with the sequence:
111 122 133 144 212 223 234 241 313 324 331 342 414 421 432 443
555 566 577 588 656 667 678 685 757 768 775 786 858 865 876 887
[/hide]

Title: Re: Faulty Combination Lock
Post by JohanC on Jun 12^th, 2008, 7:00am

Hi, Grimbal,
It seems our forum only provides upper limits, but no proof of optimality.
In the following forum (http://www.wilmott.com/messageview.cfm?catid=26&threadid=39529&FTVAR_MSGDBTABLE=&STARTPAGE=1) someone seems to know a proof that for the rooks on the nxnxn chess board, the optimal solutions are:
n²/2 for n even
and
(n²+1)/2 for n odd
He states that the sixth question of IMO 1971 (http://www.imo-register.org.uk/1971-report-st.html) is closely related.

It's strange that Neil Sloane (http://www.research.att.com/~njas/sequences/A000982) doesn't mention anything about rooks.