Jump to content
BrainDen.com - Brain Teasers
  • 1

Code to the safe


BMAD
 Share

Question

You have 7 generals and a safe with many locks. You assign the generals keys in such a way that EVERY set of four generals has enough keys between them to open ALL the locks; however, NO set of three generals is able to open ALL the locks. How many locks do you need, and list how many keys does the first general get, the second, … Is there more than one way that works?

Link to comment
Share on other sites

4 answers to this question

Recommended Posts

  • 2

I'm coming up with…

Spoiler

35 locks, with each general receiving a set of 20 keys.

It must be that any group of 3 generals is short by (at least) one type of key, and furthermore that all four of the generals not in this trio must possess a copy of that missing key. There are 35 distinct ways to choose a trio from among seven generals, and for each of those combinations, four copies of a unique key must exist to be held by each of the remaining four generals. That means there must be 140 keys altogether, four each of 35 distinct patterns, to be distributed amongst the seven generals. Each general receives one unique key for every unique grouping of 3 out of the other 6 generals.

 

Link to comment
Share on other sites

  • 1

I see, I found the solution for 8 generals, confused by range() in Python. The distribution for 7 generals:

Spoiler

1               ++++++++++++++++++++
2     ++++++++++          ++++++++++
3 ++++    ++++++    ++++++      ++++
4+ +++ +++   +++ +++   +++   +++   +
5++ +++ ++ ++  ++ ++ ++  + ++  +  +
6+++ +++ ++ + + ++ ++ + + + + +  +  
7++++ +++ ++ +  +++ ++ +  ++ +  + 

Link to comment
Share on other sites

  • 0
Spoiler

We need a lock that cannot be opened by generals 1 2 3
We need a lock that cannot be opened by generals 1 2 4
We need a lock that cannot be opened by generals 1 2 5
...
We need a lock that cannot be opened by generals 6 7 8

=> 8*7*6 = 336
As order does not matter, divide by 3!=6, giving 56 locks.

The hard part is to generate the lock numbers from the generals, the formulas are quite complicated:

Spoiler

for i1 in range(1,7):
  x=6-i1
  j1=int(35-x*(x+1)*(x+2)/6)
  for i2 in range(i1+1,8):
    x=7-i2
    j2=int(15-x*(x+1)/2)
    for i3 in range(i2+1,9):
      k1=j1+j2+i3-2
      print(str(k1).rjust(3,' '),i1,i2,i3)
print()

There is a way to cheat:

Spoiler

k1=0
for i1 in range(1,7):
  for i2 in range(i1+1,8):
    for i3 in range(i2+1,9):
      k1=k1+1
      print(str(k1).rjust(3,' '),i1,i2,i3)
print()

Both programs give the same list:

Spoiler

  1 1 2 3
  2 1 2 4
  3 1 2 5
  4 1 2 6
  5 1 2 7
  6 1 2 8
  7 1 3 4
  8 1 3 5
  9 1 3 6
 10 1 3 7
 11 1 3 8
 12 1 4 5
 13 1 4 6
 14 1 4 7
 15 1 4 8
 16 1 5 6
 17 1 5 7
 18 1 5 8
 19 1 6 7
 20 1 6 8
 21 1 7 8
 22 2 3 4
 23 2 3 5
 24 2 3 6
 25 2 3 7
 26 2 3 8
 27 2 4 5
 28 2 4 6
 29 2 4 7
 30 2 4 8
 31 2 5 6
 32 2 5 7
 33 2 5 8
 34 2 6 7
 35 2 6 8
 36 2 7 8
 37 3 4 5
 38 3 4 6
 39 3 4 7
 40 3 4 8
 41 3 5 6
 42 3 5 7
 43 3 5 8
 44 3 6 7
 45 3 6 8
 46 3 7 8
 47 4 5 6
 48 4 5 7
 49 4 5 8
 50 4 6 7
 51 4 6 8
 52 4 7 8
 53 5 6 7
 54 5 6 8
 55 5 7 8
 56 6 7 8

Spoiler

If 123 do not have the key to the lock 1, 4-7 must have a key to this lock. It could be made by hand, but...

Spoiler

keys=[]
for general in range(1,9):
  key=['*' for key in range(57)]
  key[0]=general
  keys.append(key)

k1=0
for i1 in range(1,7):
  for i2 in range(i1+1,8):
    for i3 in range(i2+1,9):
      k1=k1+1
      keys[i1-1][k1]=' '
      keys[i2-1][k1]=' '
      keys[i3-1][k1]=' '

for general in range(8):
  for lock in range(57):
    print(keys[general][lock],end='')
  print()

The distribution:

Spoiler

1                     ***********************************
2      ***************               ********************
3 *****     **********     **********          **********
4* **** ****    ****** ****    ******    ******      ****
5** **** *** ***   **** *** ***   *** ***   ***   ***   *
6*** **** *** ** **  *** *** ** **  ** ** **  * **  *  *
7**** **** *** ** * * *** *** ** * * ** ** * * * * *  *  
8***** **** *** ** *  **** *** ** *  *** ** *  ** *  *  

The solution sure is not unique, various combinations are possible. Not talking about the possibility that the lock 1 has to be unlocked to unlock locks 2 and 3.

Edited by harey
Some cosmetics
Link to comment
Share on other sites

  • 0

Is it allowable to design a key that can open multiple different locks?

If each lock has multiple positions where a subset of the pins at each position (potentially at different positions for each lock) need to be raised to the correct height in order to be opened, then it would be fairly straightforward to design one key for each general while still using the total number of locks in the answers above.

If you're limited in how many positions the pins of a lock can be in, then things might get complicated.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...