From: ronnie@cisco.com (Ronnie B. Kon)
Newsgroups: rec.puzzles
Subject: Re: Security Locks
Date: 15 Apr 92 21:59:17 GMT
Organization: cisco Systems, Incorporated

It has been pointed out to me (by Dan Cory, David Karr, and Stig Hemmer) that I 
made a mistake in implementation of my solution when adding the 3rd button. 
While doing the corrected version, I also noticed a mistake that all three
apparantly overlooked in the addition of button 4.  The corrected version follows:


In article <1992Apr15.014613.13729@csl.sri.com>, ronnie@cisco.com (Ronnie B. Kon) writes:

|> |> Question: How many different codes can such a lock have?  (Careful
|> |> when counting not to count an incident twice) If you could try one
|> |> code every 10 seconds how long would it take you to break in to the room?
|> 
|> OK, consider the case of 0 buttons:
|> 	There is 1 solution: x   (x = push no buttons)
|> 
|> Add a button #1:
|> 	There are all previous solutions:
|> 		x
|> 	And one new solution:
|> 		1
|> 
|> 
|> Add a button #2:
|> 	There are all previous solutions:
|> 		x
|> 		1
|> 	And some new solutions.  First, add a 2 in front of all previous
|> 		2,1
|> 	Now after all previous with at least 1 member
|> 		1,2
|> 	Now combine with all previous
|> 		2  (combination of x and 2)
|> 		12
|> 
|> Add a button #3:
|> 	There are all previous solutions (ordered by number of commas)
|> 		x
|> 		1
|> 		2
|> 		12
|> 		1,2
|> 		2,1
|> 	Add a 3 in front of all previous
|> 		3,1
|> 		3,2
|> 		3,12
|> 		3,1,2
|> 		3,2,1
|> 	Add a 3 at end of all previous
|> 		1,3
|> 		2,3
|> 		12,3
|> 		1,2,3
|> 		2,1,3
|> 	Add a 3 between two elements solutions
|> 		1,3,2
|> 		2,3,1
|> 	Combine all with all previous solutions
|> 		3
|> 		13
|> 		23,1
|> 		2,13
|> 		23
|> 		123
		13,2		<<<<<<< I forgot this
		1,23		<<<<<<< and this

|> 
|> 
|> Now we think a little about what is going to happen with button 4:
|> 
|> We look at the previous solutions, and find the following
|> 
|> 1 solution with 0 members (x)
|> 7 solutions with 1 member (1 2 12 3 13 23 123)
  12 solutions with 2 members (1,2 2,1 3,1 3,2 3,12 1,3 2,3 12,3 23,1 2,13 13,2 1,23)
|> 6 solutions with 3 members (3,1,2 3,2,1 1,2,3 2,1,3 1,3,2 2,3,1)
|> 
|> 
|> Add a button #4:
|> 	There are all previous solutions:
|> 		 1 w/ 0
|> 		 7 w/ 1
 		12 w/ 2
|> 		 6 w/ 3
|> 
|> 	Put a 4 in front of all previous:
|> 	Put a 4 at end of all previous:
|> 	Put a 4 between all commas:
|> 			(note that all of these affect all previous solutions
|> 			except the one with 0 members.  Each of the first two
|> 			yields the same number of solutions, but with one more
|> 			member.  The third yields (n-1) new solutions, where n
|> 			is the number of members.  A little analysis shows that
|> 			you only need to multiply the number of solutions by
|> 			(n+1), where n is the number of members in the solution)
|> 		14 w/ 2
 		36 w/ 3
|> 		24 w/ 4
|> 
|> 	Combine with all previous solutions:
|> 			(note that we will always have 1 solution generated by
|> 			combining with x, and one additional solution for every
|> 			member in a given solution)
|> 		 1 w/ 1		(combine with x)
|> 		 7 w/ 1
 		24 w/ 2		<<<<<<< originally forgot to multiply by 2
 		18 w/ 3		<<<<<<< originally forgot to multiply by 3
|> 
|> 	Add all this up and you get:
|> 		 1 w/ 0
|> 		15 w/ 1
		50 w/ 2
		60 w/ 3
|> 		24 w/ 4
|> 
|> 
|> Add button #5:
|> 	We are smart, and generalize:
|> 		 1 w/ 0		(this will always be the case)
|> 		 1 w/ 1		(this is a special case, to add with rest later--
|> 				it represents the solution of the new button alone)
|> 	
|> 	Now we think.  Given a line from a previous solution, we treat
|> 	it as x w/ n, (so x is the number of solutions, and n is the
|> 	number of members).  We know we will get
|> 		x w/ n		(The previous solution)
|> 		x(n+1) w/ (n+1)	(Put the new number in front/at end/betwen prev)
 		xn w/ n		(Combine with all previous solutions)   <<<< This was wrong
|> 	for all n > 0.  We can combine the first and last for a result
 		x(n+1) w/ n		<<<<<< This was wrong
|> 		x(n+1) w/ (n+1)
|> 
|> 	So we calculate:
		 30 w/ 1
		 30 w/ 2
		150 w/ 2
		150 w/ 3
		240 w/ 3
		240 w/ 4
		120 w/ 4
		120 w/ 5
|> 
|> 	Add up everything:
|> 		  1 w/ 0
|> 		 31 w/ 1
		180 w/ 2
		390 w/ 3
		360 w/ 4
|> 		120 w/ 5
|> 
   So the answer to the question is 1082.  (1081 if the null solution doesn't count).
|> If you can try one solution every 10 seconds, how long would it take to break 
|> in?  The flip (and correct) answer is it depends how many wrong solutions 
|> you try before hitting the correct one.  What is the average amount of time?
|> It's trivial to figure out from this, but you can't really expect me to do
|> all you homework for you.
|> 
|> 
|> 
|> 
|> Note that if we wanted to be really clever, we could figure out a non-recursive 
|> formula for the nubmer of buttons.  I shall only note that for a number of 
|> buttons B, there are
|> 		1 solution w/ 0 members
|> 		(2^B)-1 solutions w/ 1 member
|> 		B! solutions w/ B members
|> 
|> 
|> An interesting problem.		

-------------------------------------------------------------------------------
Ronnie B. Kon           |  "If you vote Republican, does that make you
ronnie@cisco.com        |   an accomplice to their crimes?"
(415) 688-4592          |                  -- Bongo, Life in Hell
-------------------------------------------------------------------------------