wu :: forums « wu :: forums - Faulty Combination Lock » Welcome, Guest. Please Login or Register. Nov 25th, 2024, 2:36am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Grimbal, william wu, Icarus, towr, ThudnBlunder, SMQ, Eigenray)    Faulty Combination Lock « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Faulty Combination Lock  (Read 3040 times) ThudnBlunder wu::riddles Moderator Uberpuzzler The dewdrop slides into the shining Sea     Gender: Posts: 4489 Faulty Combination Lock   « on: Jun 11th, 2008, 5:54am » Quote Modify 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? IP Logged THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you. SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Faulty Combination Lock   « Reply #1 on: Jun 11th, 2008, 6:56am » Quote Modify Well, some bounds to start with: not less than 24, as each trial tests 22 combinations and 512/22 > 23, and not more than 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, but there's still quite a bit of room for improvement within those bounds.   --SMQ IP Logged --SMQ Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Faulty Combination Lock   « Reply #2 on: Jun 11th, 2008, 11:54am » Quote Modify I believe it is the exact same problem as here and was already discussed here   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 « Last Edit: Jun 11th, 2008, 11:58am by Grimbal » IP Logged JohanC Senior Riddler     Posts: 460 Re: Faulty Combination Lock   « Reply #3 on: Jun 12th, 2008, 7:00am » Quote Modify Hi, Grimbal, It seems our forum only provides upper limits, but no proof of optimality. In the following forum someone seems to know a proof that for the rooks on the nxnxn chess board, the optimal solutions are:   n2/2 for n even and   (n2+1)/2 for n odd He states that the sixth question of IMO 1971 is closely related.   It's strange that Neil Sloane doesn't mention anything about rooks. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board