

Title: Broken bike combination lock problem Post by Ace_T on Mar 3^{rd}, 2005, 9:10pm Here's an interesting problem that a friend and I ended up solving more 'visually' than through pure math. You have a combination bike lock of the type which has 3 rings, each with numbers 1 through 8. Normally with this kind of lock you have to line up 3 numbers in the right order along (say) the top of the lock in order to open it. The number of possible combinations is 8x8x8. But, this lock is broken in such a way that you only have to match any 2 of the 3 numbers in order to open it. Obviously you could do it in 64 tries (8x8) by just using any 2 of the rings, but surely you can do better than that. 1. What is the minimum number of combinations you have to try to ensure that you can open the lock? 2. What is the general solution for a 3ring lock 'broken' as above, but with 'n' numbers on each ring a) if 'n' is even? b) if 'n' is odd? (for a basic diagram of what this kind of lock looks like, see http://www.securityworld.com/recreation/NS91569.html for an example.) 

Title: Re: Broken bike combination lock problem Post by markr on Mar 3^{rd}, 2005, 11:42pm Since each combination tried eliminates 3n2 combinations, the theoretical minimum is ceiling((n^3)/(3n2)). For the given problem, the minimum is no less than 24. 

Title: Re: Broken bike combination lock problem Post by Grimbal on Mar 4^{th}, 2005, 12:44am and 32 is enough. 112 121 134 143 211 224 233 242 314 323 332 341 413 422 431 444 556 565 578 587 655 668 677 686 758 767 776 785 857 866 875 888 It is linked to the "3D Chessboard Full Control" problem. http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1064517916 

Title: Re: Broken bike combination lock problem Post by Ace_T on Mar 4^{th}, 2005, 8:53am Yes, looks like the chessboard problem. I see there that someone postulated that the solution is: S = N2/2 for N even S = (N2 + 1)/2 for N odd Not sure of that notation, but the solution I came up with is S = 2(N/2)**2 = (N**2)/2 for N even (I assume that's what was meant above) S = (N**2+1)/2 for N odd 

Title: Re: Broken bike combination lock problem Post by Icarus on Mar 4^{th}, 2005, 3:56pm If you are refering to Barukh's post in the other thread, the problem may be that your browser is not able to show superscripts, because Barukh has the exponents properly superscripted in his post: S = N^{2}/2 for N even S = (N^{2} + 1)/2 for N odd but you have dropped them in your copy. If those two lines look the same to you as the ones you posted, then you need to find a better browser! 

Title: Re: Broken bike combination lock  visualization Post by Ace_T on Mar 6^{th}, 2005, 4:44pm The superscripts show up fine...must have been the settings on my work browser. One thing I found interesting was how to visualize this problem. I have a diagram that goes with the description below, but am not sure how to post it (or if it's even possible?) Basically, you start with an 8 x 8 x 8 cube. Each guess at a combination 'cuts out' a line of 1 x 1 x 1 cubes in each of the 'x', 'y' and 'z' directions from the specific (x, y, z) cube selected. If your guesses have completely covered the volume of the 8 x 8 x 8 cube you have a solution. What is interesting is that when you see this visually, you can see that all guesses where (say) x, y, z <= 4 will carve out a '3dimensional L' shape. Then, you only need to make guesses in the x, y, z >4 quadrant to complete the solution. If you look at a 2 x 2 x 2 cube first it's easier to see this '3dimensional L' shape. So, the number of guesses you need to cover the x, y, z <= 4 quadrant cannot be less than 16 (the area of any 4 x 4 'end' to the 3dimensional L). It's easy to see there are many solutions of 16, so the full solution is 16+16=32. For an n x n x n cube where n is odd, a similar approach gives the solution (noting that the two quadrants you are selecting in should be as near to the median as possible, so for a 9 x 9 x 9 cube you could select 16 guesses in the x, y, z <= 4 quadrant, and 25 guesses in the x, y, z >4 quadrant. So, anyone able to visualize this in one more dimension and get a solution for n x n x n x n? :) 

Title: Re: Broken bike combination lock  visualization Post by Barukh on Mar 7^{th}, 2005, 6:22am on 03/06/05 at 16:44:29, Ace_T wrote:
File attachements were possible before this forum has been upgraded with new software. We all hope this feature will be restored shortly. 

Title: Re: Broken bike combination lock problem Post by Icarus on Mar 7^{th}, 2005, 4:59pm If you have another website you can put the image on, then you can use the img tags: [img]image url here[/img] to post the image here. Unfortunately, the ability to post them here directly is waiting on William to find time to restore it. Having once been a grad student myself, I know that this may be awhile. ::) 

Title: Re: Broken bike combination lock problem Post by Ace_T on Oct 5^{th}, 2014, 1:02pm Update...you can see the visualization at: http://iantotman.blogspot.ca/2014/09/thebrokencombinationlockproblem.html 

Title: Re: Broken bike combination lock problem Post by Altamira_64 on Jan 31^{st}, 2016, 8:59am So if each digit only gets values 1, 2 and 3, the minimum number of tries is 5? How can we pick the right 5 combinations which will open all 27? 

Title: Re: Broken bike combination lock problem Post by Grimbal on Feb 28^{th}, 2016, 8:34am The combination has 3 digits. It either has two digits in the set {1,2} or it has 2 digits in the set {3}. To cover the first case, try 111, 122, 212, 221. To cover the second case, try 

Title: Re: Broken bike combination lock problem Post by rmsgrey on Feb 28^{th}, 2016, 2:18pm on 02/28/16 at 08:34:36, Grimbal wrote:
Or, to actually cover the second case, try 333. 

Title: Re: Broken bike combination lock problem Post by Grimbal on Mar 1^{st}, 2016, 1:40pm Er... and this was a demonstration of how peerreview improves the quality of a publication. Thanks for your collaboration. :[ 

Title: Re: Broken bike combination lock problem Post by Hippo on Mar 9^{th}, 2016, 9:20am on 03/04/05 at 00:44:34, Grimbal wrote:
I would replace second 413 with 431 :P, and 243 should be probably replaced by 242 ... and the same with second 857 and 875, and 687 replaced with 686. But I agree with the posts mentioning 32 as the solution ... and the generalised one. 

Title: Re: Broken bike combination lock problem Post by Grimbal on Mar 10^{th}, 2016, 8:11am It took you 

Title: Re: Broken bike combination lock problem Post by Altamira_64 on Mar 11^{th}, 2016, 12:36am Another one: 111 122 233 312 321 [quote author=Grimbal link=board=riddles_hard;num=1109913027;start=0#12 date=03/01/16 at 13:40:25]Er... and this was a demonstration of how peerreview improves the quality of a publication. Thanks for your collaboration. :[/quote] 

Title: Re: Broken bike combination lock problem Post by Hippo on Mar 11^{th}, 2016, 9:29am on 03/10/16 at 08:11:55, Grimbal wrote:
But I was not around several of them :P 

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