Unlocking doors

[BMAD]

You were recently hired to be the head of maintenance in a mathematics building. The building has 61 doors but 60 our locked. In your office you have ten keys. Each key unlocks at least 1 door and no two keys unlock the same amount of doors nor the same door. There are ten rooms on a floor, with your office being in the basement (for technically an eleventh floor).

1. Develop an optimal strategy that will quickly tell you how many doors each key unlocks.

2. Develop an optimal strategy that will quickly tell you which door each key unlocks (if different from #1).

[superprismatic]

I have 2 questions:

1. Are we to find keys to open all 61 doors? A door need not be locked for us to test a key to it. Or are we

to find keys for only the 60 locked doors?

2. If the basement is technically the eleventh floor, then there must be 10 floors above it with 10 rooms per floor.

That's a total of 100 rooms plus the office in the basement. Is this correct? If so, shouldn't each above-ground

floor have 6 rooms? Otherwise, there would have to be 40 rooms without doors.

[TimeSpaceLightForce]

[BMAD]

I have 2 questions:

1. Are we to find keys to open all 61 doors? A door need not be locked for us to test a key to it. Or are we

to find keys for only the 60 locked doors?

2. If the basement is technically the eleventh floor, then there must be 10 floors above it with 10 rooms per floor.

That's a total of 100 rooms plus the office in the basement. Is this correct? If so, shouldn't each above-ground

floor have 6 rooms? Otherwise, there would have to be 40 rooms without doors.

Alas, the basics i miss. yes. there are 6 rooms on a floor with the exception of the basement where there is only 1. And yes, you need to find a key for the basement as well.

[bonanova]

What is the relation of the ten floors to optimality?

Is optimal fewest operations or shortest time?

Does it take time to travel between floors?

Are there n elevators ?

Are you initially inside your basement office?

If so can you open its door without first identifying its key and using it to get out?

Your ten keys open at least 55 of the doors, but not necessarily more than that. If you need a key to exit a locked room, and you start out inside a room (your office) and you don't have its key then you're trapped.

This is a nice puzzle.

[BMAD]

What is the relation of the ten floors to optimality?

Is optimal fewest operations or shortest time?

Does it take time to travel between floors?

Are there n elevators ?

Are you initially inside your basement office?

If so can you open its door without first identifying its key and using it to get out?

Your ten keys open at least 55 of the doors, but not necessarily more than that. If you need a key to exit a locked room, and you start out inside a room (your office) and you don't have its key then you're trapped.

This is a nice puzzle.

What is the relation of the ten floors to optimality?

Is optimal fewest operations or shortest time?

optimal in the sense that i want to go to the fewest floors and fewest doors and testing the fewest keys possible.

Does it take time to travel between floors?

Are there n elevators ?

travel time is not a consideration, we could use the exercise

Are you initially inside your basement office?

If so can you open its door without first identifying its key and using it to get out?

you start out in the basement which is unlocked. but you do need to know what unlocks this door.

[phil1882]

clearly number of floors isnt going to be an issue. all doors might as well be on the same floor. i fail to see how skipping doors in any way helps solve the problem.

so we need a two varible equation, number of doors and number of keys.

lets start off with some basics.

if keys = 1, then F(k,d) = d

if doors = 1, then F(k,d) = k.

if keys*(keys+1)/2 >= doors, then F(k,d) = k*d, in the worst case.

since in this case we have 10 keys and 61 doors, we can only do slighty better than 610, since 11 keys would give us the worst case. how much better? i honestly don't know.

[bonanova]

optimal in the sense that i want to go to the fewest floors and fewest doors and testing the fewest keys possible.

So optimal means minimize the sum: floors+doors+ keys.

[TimeSpaceLightForce]

[ P ]
10 [ 01 02 03 04 05 06 ]
9 [ 01 02 03 04 05 06 ]
8 [ 01 02 03 04 05 06 ]
7 [ 01 02 03 04 05 06 ]
6 [ 01 02 03 04 05 06 ]
5 [ 01 02 03 04 05 06 ]
4 [ 01 02 03 04 05 06 ]
3 [ 01 02 03 04 05 06 ]
2 [ 01 02 03 04 05 06 ]
1 [ 01 02 03 04 05 06 ]

Key tagging:
try 9 keys on Penthouse, if any locks it , tag key 1K1, tag the door 1D
else tag last key 1K1 ,tag the door 1D
try 1K1 on 1001,if unlocks,retag 1K1 to 1K2, tag the door 1D
else try the other keys, if unlocks,tag it 2K1,tag the door 2D
try 1K1 on 1002,if unlocks,retag 1K1 to 1K2, tag the door 1D
else try 2K1 on 1002,if unlocks,retag 2K1 to 2K2, tag the door 2D
else try the other keys, if unlocks,tag it 3K1,tag the door 3D
try 1K1 on 1003,if unlocks,retag 1K1 to 1K2, tag the door 1D
else try 2K1 on 1003,if unlocks,retag 2K1 to 2K2, tag the door 2D
else try 3K1 on 1003,if unlocks,retag 3K1 to 3K2, tag the door 3D
else try the other keys, if unlocks,tag it 4K1,tag the door 4D
so on..
at the end we expect key tags bears ( tag no.on room door) K (no. of doors it unlocks/ key no.)

because no 2 keys have same no. of doors it unlocks…
no. on room doors are (1,2,3,4,5,6,7,8,9,10) = 10 keys
no. of doors the keys unlock (1,2,3,4,6,7,8,9,10,11)=61 doors
so,if taging reach K11 we stop trying that key
then next,if tagging reach K10 stop trying that key
so on..

[TimeSpaceLightForce]

no. of room doors the key unlocks

1 2 3 4 6 7 8 9 10 11
1 2 3 4 5 7 8 9 10 12
1 2 3 4 5 6 8 9 10 13
1 2 3 4 5 6 8 9 11 12
1 2 3 4 5 6 7 9 10 14
1 2 3 4 5 6 7 9 11 13
1 2 3 4 5 6 7 10 11 12
1 2 3 4 5 6 7 8 10 15
1 2 3 4 5 6 7 8 11 14
1 2 3 4 5 6 7 8 12 13
1 2 3 4 5 6 7 8 9 16

[BMAD]

optimal in the sense that i want to go to the fewest floors and fewest doors and testing the fewest keys possible.

So optimal means minimize the sum: floors+doors+ keys.

yes.

[superprismatic]

I wasn't sure what floors+doors+keys means. I took the liberty of interpreting

this as [number of visited floors]+[number of overall key-in-doorlock checks]. If this
correct, I realized that the basement floor need not always be checked because
we may have only one key not spoken for by the time we get to consider it. In
this case, we can be sure that that key is the one for the room in the basement.
Similarly, we need only check 9 of the 10 keys in any door. If they don't
unlock it, we can be sure that the key we haven't checked will unlock it.

I used the above reasoning to make two simulations of 1,000,000 trials each.
One simulation, which tried keys in increasing order of how many doors they opened
so far, with ties broken randomly. In this trial, the average score was 385.9.
The second simulation was similar, but tried keys in decreasing order of how many
doors they opened so far. This second one produced an average score of 423.4.
So, my vote goes to my first strategy as the optimal one.