Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,397
A lock has four switches (A, B, C, D) and each switch has three positions (1, 2, 3).
The lock is a cheap brand and two switches do absolutely nothing (so just the correct settings on the other two switches will open the lock).
What is the minimum number of combination one must check to ensure that the lock opens?
I can not do this one. Here is my work so far.
There are 3^4 = 81 combinations. 4C2 = 6 ways to choose the two switches that work. There are 3*3 = 9 ways to try for the 2 good switches. This tells that the answer to the question is 6*9 = 54 or lower. It turns out it is lower.
So I decided to look at what happens if there are only 3 switches, each with 3 positions.
There are 27 possible settings. Let's see if we can do better.
Suppose the 1st two work. Then we need to just check: 11x 12x 13x 21x 22x 23x 31x 32x 33x.
Can we use these 9 if the last two switches only work?
111 122 133 212 223 231 313 321 332 and the answer is yes. What about if the 1st and 3rd switch only works? This same combination works.
So can we modify these 9, by adding a 4th entry, that will work for 4 switches? So we can look at 6^3 combinations to try?
But 6^3 is just too many to look at. So what is the easy way that I am missing?
The lock is a cheap brand and two switches do absolutely nothing (so just the correct settings on the other two switches will open the lock).
What is the minimum number of combination one must check to ensure that the lock opens?
I can not do this one. Here is my work so far.
There are 3^4 = 81 combinations. 4C2 = 6 ways to choose the two switches that work. There are 3*3 = 9 ways to try for the 2 good switches. This tells that the answer to the question is 6*9 = 54 or lower. It turns out it is lower.
So I decided to look at what happens if there are only 3 switches, each with 3 positions.
There are 27 possible settings. Let's see if we can do better.
Suppose the 1st two work. Then we need to just check: 11x 12x 13x 21x 22x 23x 31x 32x 33x.
Can we use these 9 if the last two switches only work?
111 122 133 212 223 231 313 321 332 and the answer is yes. What about if the 1st and 3rd switch only works? This same combination works.
So can we modify these 9, by adding a 4th entry, that will work for 4 switches? So we can look at 6^3 combinations to try?
But 6^3 is just too many to look at. So what is the easy way that I am missing?
Last edited: