Combinations: A lock has four switches (A, B, C, D) and each switch has three positio

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?

Jomo said:

A lock has four switches (A, B, C, D) and each switch has three positions (1, 2, 3).

Click to expand...

Can you clarify that....like, is B321 a possible "password"?
And if B is faulty, then B(123, 132 ... 321) will not work?

Denis said:

Can you clarify that....like, is B321 a possible "password"?
And if B is faulty, then B(123, 132 ... 321) will not work?

Click to expand...

Two of the switches are dummy switches and do nothing, so their position does not matter. For example, if switch A and B are the dummy switches and switch C must be set to position 1 and switch D must be set to position 2, then any combination of the form xx12 will open the lock.

Huh? I'm now MORE confused than I was
Looks like everybody else is also confused: nobody else tried!!

Can you perhaps explain it as being in the lobby of a building
and 7 "buttons" are on wall:
A B C D
1 2 3

What must be "pressed" in order to open main door....????

Denis said:

Huh? I'm now MORE confused than I was
Looks like everybody else is also confused: nobody else tried!!

Can you perhaps explain it as being in the lobby of a building
and 7 "buttons" are on wall:
A B C D
1 2 3

What must be "pressed" in order to open main door....????

Click to expand...

Image you want to turn on a light bulb which requires 4 switches (well actually 2 switches) to be in the correct position before the light turns on. Each switch has three positions (up, center and down). The four switches are all next to one another but two of the switches do not control the light at all (they control the light down the hallway). You MUST have the two (real) switches in the correct setting in order to illuminate the light bulb. How many settings must you try to guarantee the light to turn on.

What seems to be troubling you with the wording? Again 2 of the 4 switches do something and each switch has 3 settings.

Jomo said:

Image you want to turn on a light bulb which requires 4 switches
(well actually 2 switches) to be in the correct position before the light turns on.

Each switch has three positions (up, center and down).

The four switches are all next to one another but two of the switches do not
control the light at all (they control the light down the hallway).

You MUST have the two (real) switches in the correct setting in order to
illuminate the light bulb.

How many settings must you try to guarantee the light to turn on.

Click to expand...

Hmmm...ok, assume A2 (switch A at center position)
and D3 (switch D at down position) is only combo that turns on "the light".

Positions for switches B and C are unimportant, since both are not connected.

A 1 [2] 3
B 1 2 3
C 1 2 3
D 1 2 [3]

So I step up to the "buttons" and try combos; like:
B2 D1 or A3 B3 or B2 C1 or .......

QUESTION: what is minimum number of tries required
in order to turn on the light?

Am I finally "seeing the light"

Jomo said:

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^4 combinations to try?


But 6^4 is just too many to look at. So what is the easy way that I am missing?

Click to expand...

There are too many variables to let me attack this problem generically although I am reasonably confident someone cleverer than I could so.

First point is that although there are 81 settings, 9 of them are useful. Thus there are 72 useless settings.

The second point is that each setting incorporates \(\displaystyle \dbinom{4}{2} = 6\) possible ways to open the lock.

So I am going to indicate that a switch is up by 0, centered by 1, and down by 2.. Thus 2011 means switch A is down, switch B is up, and switches C and D are centered.

Test 1: 0000.

If this works we have one of the nine good settings and are done. If it fails, we know that the way to open the lock is not up and up on the active switches. Furthermore, we need not look at any other settings that contain at least 2 zeroes.

Test 2: 1111.

If this works, we have one of the nine good settings and are done. If it fails, we know that the way to open the lock is not centered and centered on the active switches. Furthermore, we need not look at any other settings with at least 2 ones.

But there are only 0, 1, and 2 as options and 4 switches. So if there are at most 1 zero and at most 1 one, there must be at least 2 twos. The number of settings with no two's is 2^4 = 16. The number of settings with 1 two is 4 times 2^3 = 32. Those sum to 48. Thus there are only 33 settings to test. But 9 of those settings will work. That means that 24 are useless. By bad luck, we might test all 24. Thus, in the worst case, we can open the lock in 2 + 24 + 1 = 27 tries.

Now I have a suspicion that we can get below that, but it is late, and I am tired. Be back tomorrow.

Denis said:

Hmmm...ok, assume A2 (switch A at center position)
and D3 (switch D at down position) is only combo that turns on "the light".

Positions for switches B and C are unimportant, since both are not connected.

A 1 [2] 3
B 1 2 3
C 1 2 3
D 1 2 [3]

So I step up to the "buttons" and try combos; like:
B2 D1 or A3 B3 or B2 C1 or .......

QUESTION: what is minimum number of tries required
in order to turn on the light?

Am I finally "seeing the light"

Click to expand...

Yes, you finally got it.

JeffM said:

There are too many variables to let me attack this problem generically although I am reasonably confident someone cleverer than I could so.

First point is that although there are 81 settings, 9 of them are useful. Thus there are 72 useless settings.

The second point is that each setting incorporates \(\displaystyle \dbinom{4}{2} = 6\) possible ways to open the lock.

So I am going to indicate that a switch is up by 0, centered by 1, and down by 2.. Thus 2011 means switch A is down, switch B is up, and switches C and D are centered.

Test 1: 0000.

If this works we have one of the nine good settings and are done. If it fails, we know that the way to open the lock is not up and up on the active switches. Furthermore, we need not look at any other settings that contain at least 2 zeroes.

Test 2: 1111.

If this works, we have one of the nine good settings and are done. If it fails, we know that the way to open the lock is not centered and centered on the active switches. Furthermore, we need not look at any other settings with at least 2 ones.

But there are only 0, 1, and 2 as options and 4 switches. So if there are at most 1 zero and at most 1 one, there must be at least 2 twos. The number of settings with no two's is 2^4 = 16. The number of settings with 1 two is 4 times 2^3 = 32. Those sum to 48. Thus there are only 33 settings to test. But 9 of those settings will work. That means that 24 are useless. By bad luck, we might test all 24. Thus, in the worst case, we can open the lock in 2 + 24 + 1 = 27 tries.

Now I have a suspicion that we can get below that, but it is late, and I am tired. Be back tomorrow.

Click to expand...

I can demonstrate that the correct "combination" can be found in no more than 15 attempts.

Trial 1: 0000 gets 6 possibilities: any of the 6 pairs of active switches, both up.

Trial 2: 1111 gets 6 possibilities: any of the 6 pairs of active switches, both centered.

Trial 3: 2222 gets 6 possibilities: any of the 6 pairs of active switches, both down.

Thus trials 1 through 3 account for the 18 possible "combinations" where the active switches have the same setting. That leaves 36 to go.

Consider the possible "combinations" that consist of active switches set to up (0) or centered (1). But we have already accounted for "combinations" that are both up or both centered. Each active pair can have 2 possible settings and there are 6 possible active pairs, giving 12 possible "combinations."

Trial 4: 0101 gets 4 possibilities not captured by trials 1 through 3, (namely A up / B centered, A up / D centered, B centered / C up, and C up D centered).

Trial 5: 1010 gets 4 possibilities not captured by trials 1 through 4, (namely A centered / B up, A centered / D up, B up / C centered, and C centered D up).

That leaves 4 possibilities that exclude down still untested, namely the two where A and C differ and the two where B and D differ.

Trial 6: 0110 captures A up / C centered and B centered / D up.

Trial 7: 1001 captures A centered / C up and B up / D centered.

Thus the four trials numbered 4 through 7 capture all 12 combinations involving up and centered on the active switches. But the same logic will apply to up and down and to centered and down. So

Trial 8: 0202.

Trial 9: 2020.

Trial 10: 0220.

Trial 11: 2002.

Trial 12: 1212.

Trial 13: 2121.

Trial 14: 1221.

Trial 15: 2112.

I have not found a proof that the maximum number of trials potentially needed is less than 15. I can prove that the maximum number of trials potentially needed exceeds 8 and does not exceed 15.