wu :: forums
« wu :: forums - Broken bike combination lock problem »

Welcome, Guest. Please Login or Register.
Dec 10th, 2024, 12:12pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Grimbal, ThudnBlunder, Icarus, william wu, SMQ, towr)
   Broken bike combination lock problem
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Broken bike combination lock problem  (Read 11106 times)
Ace_T
Guest

Email

Broken bike combination lock problem  
« on: Mar 3rd, 2005, 9:10pm »
Quote Quote Modify Modify Remove Remove

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 3-ring 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.)
IP Logged
markr
Junior Member
**





   


Gender: male
Posts: 90
Re: Broken bike combination lock problem  
« Reply #1 on: Mar 3rd, 2005, 11:42pm »
Quote Quote Modify Modify

Since each combination tried eliminates 3n-2 combinations, the theoretical minimum is ceiling((n^3)/(3n-2)).
 
For the given problem, the minimum is no less than 24.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: Broken bike combination lock problem  
« Reply #2 on: Mar 4th, 2005, 12:44am »
Quote Quote Modify Modify

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/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1064517916
« Last Edit: Mar 10th, 2016, 8:11am by Grimbal » IP Logged
Ace_T
Guest

Email

Re: Broken bike combination lock problem  
« Reply #3 on: Mar 4th, 2005, 8:53am »
Quote Quote Modify Modify Remove Remove

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
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Broken bike combination lock problem  
« Reply #4 on: Mar 4th, 2005, 3:56pm »
Quote Quote Modify Modify

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 = N2/2 for N even
S = (N2 + 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!
« Last Edit: Mar 7th, 2005, 4:52pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Ace_T
Guest

Email

Re: Broken bike combination lock - visualization  
« Reply #5 on: Mar 6th, 2005, 4:44pm »
Quote Quote Modify Modify Remove Remove

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 '3-dimensional 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 '3-dimensional 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 3-dimensional 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? Smiley
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Broken bike combination lock - visualization  
« Reply #6 on: Mar 7th, 2005, 6:22am »
Quote Quote Modify Modify

on Mar 6th, 2005, 4:44pm, Ace_T wrote:
I have a diagram that goes with the description below, but am not sure how to post it (or if it's even possible?)

File attachements were possible before this forum has been upgraded with new software. We all hope this feature will be restored shortly.
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Broken bike combination lock problem  
« Reply #7 on: Mar 7th, 2005, 4:59pm »
Quote Quote Modify Modify

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. Roll Eyes
« Last Edit: Mar 7th, 2005, 5:00pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Ace_T
Guest

Email

Re: Broken bike combination lock problem  
« Reply #8 on: Oct 5th, 2014, 1:02pm »
Quote Quote Modify Modify Remove Remove

Update...you can see the visualization at: http://iantotman.blogspot.ca/2014/09/the-broken-combination-lock-problem .html
IP Logged
Altamira_64
Junior Member
**





   


Posts: 116
Re: Broken bike combination lock problem  
« Reply #9 on: Jan 31st, 2016, 8:59am »
Quote Quote Modify Modify

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?
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: Broken bike combination lock problem  
« Reply #10 on: Feb 28th, 2016, 8:34am »
Quote Quote Modify Modify

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 222 333.
« Last Edit: Mar 1st, 2016, 1:27pm by Grimbal » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2874
Re: Broken bike combination lock problem  
« Reply #11 on: Feb 28th, 2016, 2:18pm »
Quote Quote Modify Modify

on Feb 28th, 2016, 8:34am, Grimbal wrote:
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 222.

 
Or, to actually cover the second case, try 333.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: Broken bike combination lock problem  
« Reply #12 on: Mar 1st, 2016, 1:40pm »
Quote Quote Modify Modify

Er... and this was a demonstration of how peer-review improves the quality of a publication.  Thanks for your collaboration. Embarassed
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Broken bike combination lock problem  
« Reply #13 on: Mar 9th, 2016, 9:20am »
Quote Quote Modify Modify

on Mar 4th, 2005, 12:44am, Grimbal wrote:
and 32 is enough.
 
112 121 134 143
211 224 233 243
314 323 332 341
413 422 413 444
 
556 565 578 587
655 668 677 687
758 767 776 785
857 866 857 888
 
It is linked to the "3D Chessboard Full Control" problem.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1064517916

 
I would replace second 413 with 431 Tongue,
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.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: Broken bike combination lock problem  
« Reply #14 on: Mar 10th, 2016, 8:11am »
Quote Quote Modify Modify

It took you TEN ELEVEN years to notice ? ? ? Cheesy
« Last Edit: Mar 10th, 2016, 8:13am by Grimbal » IP Logged
Altamira_64
Junior Member
**





   


Posts: 116
Re: Broken bike combination lock problem  
« Reply #15 on: Mar 11th, 2016, 12:36am »
Quote Quote Modify Modify

Another one:  
111
122
233
312
321
 
 
on Mar 1st, 2016, 1:40pm, Grimbal wrote:
Er... and this was a demonstration of how peer-review improves the quality of a publication.  Thanks for your collaboration. Embarassed

IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Broken bike combination lock problem  
« Reply #16 on: Mar 11th, 2016, 9:29am »
Quote Quote Modify Modify

on Mar 10th, 2016, 8:11am, Grimbal wrote:
It took you TEN ELEVEN years to notice ? ? ? Cheesy

 
But I was not around several of them Tongue
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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