Social Question

LostInParadise's avatar

Can you solve this diabolical combination lock problem?

Asked by LostInParadise (17934 points ) December 24th, 2012

A lock has four buttons and is opened by a sequence of 6 button presses. Pressing the same button a second time in a row has no effect, which is to say that the combinations cannot have two identical numbers in a row. If we are told that the first and last numbers of the combination are both button 1, how many possible combinations are there?

Small numbers were deliberately chosen to increase the frustration level. You might initially think that since, for each of the 4 unknown numbers, there are 3 numbers different from the preceding number, that the answer is 3×3 x 3×3 = 81. However, the last of the 4 numbers cannot be 1, because of the way the lock works, so the answer is some number less than 81. No fair guessing. You must provide an explanation.

Hint: Try solving the problem if the total number of presses was 3 and then try for 4.

Observing members: 0 Composing members: 0

12 Answers

gasman's avatar

Let’s say the sequence is abcdef, where each letter a-f represents one the digits 1–4. Below I use the ascii codes “element of” and “not equal to” – I hope they render right.

a=1
b ∈ {2,3,4}
c ∈ {1,2,3,4; c≠b}
There are 3 choices for b and 3 for c.
So far that makes 3*3 = 9 permutations for the combo abc

d is more complicated.
We see that c=1 is always one of exactly three choices for c, in which case d=1 is not allowed, whereas for c≠1 then d=1 is allowed. So of the 27 abcd combos, d=1 occurs 9 times, meaning that d≠1 occurs 27–9 = 18 times.

but if d=1 then e ∈ {2,3,4} so de represents 3 combos
while if d=2 then e ∈ {3,4} so de represents 2 combos
if d=3 then e ∈ {2,4} so ” ” 2 ”
if d=4 then e ∈ {2,3} so ” ” 2 ”
In other words, if d≠1 then abcd represents 18 combos.
Multiply each of these by the choices for e to enumerate all abcde, which is the same as abcdef since we know f=1.

So the final answer I get is (9*3 + 18*2) = 27+36 = 61 different combos, which is notably less than 81.

gasman's avatar

lol 27+36 = 63. Cheers.

ragingloli's avatar

Pour thermite on it.

Mariah's avatar

Not looking at the above answers…

Ignore the first and last number. They are fixed and do not add to the number of combinations.

We now say we have as follows:

Second press can be 2, 3, 4
Third press can be 1, 2, 3, 4, but not the same as the second press.
Ditto on fourth press.
Fifth press can be 2, 3, 4 but not the same as the fourth press.

You might be tricked now into saying that there are 3*3*3*2=54 presses. But wait! If the fourth press is a 1, then you have 3 choices for press number 5. In this situation, the two stipulations (not equal to 1 and not equal to fourth press) are combined into one. So let’s consider the two scenarios separately.

Scenario 1: If fourth press is a 1:
We then have x, y, 1, z where x≠1, y≠x, y≠1, and z≠1. This gives us 3*2*3 = 18 combinations.

Scenario 2: If fourth press is not a 1:
We then have a, b, c, d where c≠1. Again, the situation splits into two scenarios. If b=1, there are more possibilities than if it is a different number. This is because c cannot be 1, and a cannot be 1, so making b=1 does not place any new limitations on these two numbers.

Scenario 2a: third press is 1, fourth press is not 1
We have a, 1, c, d. a can be any of 2, 3, 4. c can be any of 2, 3, 4. d cannot be the same as c, nor can it be 1, so it has just 2 options. The number of possibilities is 3*3*2 = 18.

Scenario 2b: third press is not 1, fourth press is not 1.
We have a, b, c, d. In this situation, nothing can be 1! a and d are out because they sit next to the ones on either end stipulated in the original problem. b and c are out because we are cornered into such a narrow scenario in which they are specified as not being 1. This means a has three choices, b has 2 choices (not equal to a or 1), c has 2 choices (not equal to b or 1) and d has 2 choices (not equal to c or 1) 3*2*2*2 = 24.

Now we’ve considered all the scenarios. The answer is the sum of all the situations, or 18+18+24 = 60. I think I made this more difficult than necessary and I’m not wholly convinced I’m right. I’ll look up at the other answers now.

LostInParadise's avatar

@Mariah , That is correct. @gasman, you came real close. Unfortunately, I can’t quite follow what you did.

There is a real slick method of solution. Let f(n) be the number of combinations of length n starting and ending at 1, where n >= 2. There is a recursion formula for f(n), which can be used to create a closed form solution.

The problem was originally stated differently and you may find it more natural in the original. I thought that using a combination lock made it more interesting. The original form was to link 4 points to each other and find the number of paths of length 5 that start at point 1 and end at point 1.

Enjoy the holdiay! I will give the recursion approach tomorrow.

gasman's avatar

I see my mistake—in partitioning the 27 abcd combos into those that end in 1 vs. those that don’t, the split is (6,21), not the (9,18) I arrived at by faulty logic. So the total combos produced after adding in e & f is:
6*3 + 21*2 = 18+42 = 60.

@LostInParadise, a devilishly delightful problem!

BonusQuestion's avatar

The number of all sequences a, b, c, d from the set {1, 2, 3, 4} that no consecutive numbers are the same is 4*3^3.

If a=1 we have 3^3 such sequences.

If d=1 we have 3^3 such sequences.

If a=d=1 we have 3*2 sequences.

So the number of possibilities is 4*3^3–2*3^3+3^2=60.

BonusQuestion's avatar

@LostInParadise

f(2)=0, f(3)=3, f(n)=f(n-2)*3+f(n-1)*2?

f(n)=(-9*(-1)^n+3^n)/12?

gasman's avatar

I think I worked out the recursive relation:

f(n) = 3^(n-2) – f(n-1)

Given f(2) = 0 this generates
f(3) = 3 – f(2) = 3
f(4) = 9 – f(3) = 6
f(5) = 27 – f(4) = 21
f(6) = 81 – f(5) = 60
f(7) = 243 – f(6) = 183
etc.

In effect the formula says to consider all combinations (a power of 3) except those where the next-to-last digit is a 1, i.e., the previous number of combinations.

LostInParadise's avatar

Exactly! Funny how the recursion relationship does such a good job of hiding in plain sight.

If you work with the relationship, you will see that f(6) = 3^4 – 3^3 + 3^2 – 3. This can be turned into a closed form for n using the formula for geometric series on powers of -3.

LostInParadise's avatar

I was curious to see how to compute, over all the combinations, how many button presses there are for a given button for the nth button press. Obviously, for the 2nd and 5th button presses, the number of presses is evenly divided between 2,3, and 4, giving 20 for each. It is not too hard to determine the number of presses at the fourth, and therefore. by symmetry. also the third, press. In these cases, the first button is pressed more often than the others. It is then easy to compute the total number of presses for each button

LostInParadise's avatar

One last comment. The recursion relation works if the first and last buttons are different. We get
g(2) =1
g(n)= 3^(n-2) – g(n-1)
g(3) = 2
g(4) =7
g(5) = 20
g(6) = 61

To find the total number of times a button is pressed, just use combinations of f(n), as defined by @gasman, or g(n).

To find the number of times that the third button pressed is button 1, break the path into the two parts, from the first button to the third, and from the third to the sixth, giving f(3) x f(4) = 3×6 =18. For the third button equal to one of the other numbers, you get g(3) x g(4) = 2×7 =14

Answer this question

Login

or

Join

to answer.
Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther