10
$\begingroup$

There are 100 friends and $n$ enemies in a room. In the next room, there are $100+n$ open boxes, and $100+n$ keys, one corresponding to each box. They are numbered for easy identification. A box can be locked without using a key. Upto 2 keys can be placed in a box before locking it. A key cannot be locked inside its own box. The friends and enemies not yet called are allowed to have private chats while the game is in progress.

One by one, people are called into the room. First a friend is called, then an enemy is called, then a friend, then an enemy and so on. If $n<100$, only friends will be called once the enemies have run out. A person can pick up 0,1 or 2 keys lying around and lock them into a single box. Then he comes back and makes a public statement(s) that can be heard by everyone. Then he leaves the game and can not communicate further.

Finally, the king enters the room. He has a lockpick that can be used to break open exactly one box. After this, he will try to open all the boxes. The friends want him to succeed and the enemies want him to fail.

What is the largest value of $n$ for which the friends guarantee a win?

P.S. People can use computers for making decisions beyond human thinking.

Improve this question
$\endgroup$
11
  • $\begingroup$ "makes a public statement(s) that can be heard by everyone" What type of statement do they make? Do they say which keys they have locked? $\endgroup$
    – Rohcana
    Sep 12, 2015 at 17:39
  • 9
    $\begingroup$ If two enemies both lock a key inside its corresponding box, doesn't it become impossible? $\endgroup$
    – f''
    Sep 12, 2015 at 17:47
  • $\begingroup$ @f'' I think it is even possible with only 1 enemy. He can put 2 keys in a box and lock both corresponding boxes. $\endgroup$
    – Sleafar
    Sep 12, 2015 at 17:55
  • $\begingroup$ @Sleafar, one enemy can only lock a single box. The king could use his lockpick on that box. The friends don't have to lock up any keys. $\endgroup$
    – Gordon K
    Sep 12, 2015 at 18:08
  • 1
    $\begingroup$ Can the king hear the public statements? $\endgroup$
    – frodoskywalker
    Sep 13, 2015 at 11:01

2 Answers 2

Reset to default
7
$\begingroup$

The limit for n is

Surprisingly, 101!

Because

On the first turn, the friends will place 2 random keys into box A. This is the box which the king will open. Consider a box openable if it is box A or its key is in an openable box. The goal is to have all locked boxes be openable by the end. This is currently the case.

For the next action by the enemies - putting keys x or (x,y) into box Z - key z must be available or in an openable box. If z is available, place it and random key w into an openable box (otherwise just place v,w). The point of placing w is to always keep at least one unlocked, openable box

If the enemies take the last turn, all boxes except those for the remaining keys are openable, and the enemy may not lock the keys into those boxes. Victory!

The enemies can, however, construct a loop with 2 consecutive turns, so $n$ large enough to allow that is the limit. Since the friends use 2 keys per turn, there must be at least 202 keys to defeat them, hence $n=101$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Didn't see that. Is it possible that you have an off-by-one-error? The OP asks for the number where the king will still win. $\endgroup$
    – Sleafar
    Sep 13, 2015 at 19:59
  • $\begingroup$ Amusingly, the enemy strategy to win with n=102 is to take no action for the first 100 rounds to ensure there are two keys left for the last two enemies to put into each other's boxes $\endgroup$
    – frodoskywalker
    Sep 13, 2015 at 20:24
  • $\begingroup$ +1 for proving $n \geq 101$. I had this idea but I was struggling to write it down, unfortunately. However, how can you be sure that one can cause a loop if keys A,B and boxes C,D are left? (The friends can ensure this) $\endgroup$
    – wythagoras
    Sep 14, 2015 at 14:36
  • $\begingroup$ @frodoskywalker After 100 rounds, there will probably be no keys leftover. I'm yet to understand your solution. $\endgroup$
    – ghosts_in_the_code
    Sep 14, 2015 at 16:02
  • $\begingroup$ @ghosts in the n=102 case, the enemies must take no action as long as the friends follow my strategy above. This means that the friends will use a maximum of 200 keys over 100 rounds, leaving 2 for the last 2 enemies. $\endgroup$
    – frodoskywalker
    Sep 14, 2015 at 17:07
4
$\begingroup$

Partial Start

There are some quick rules I could figure out:

  1. Perfect Information

    Everyone remaining can know what is happening. For example, each friend can make announcement regarding which keys and boxes s/he has locked, and which keys and boxes were locked by previous enemy (based on info of previous friend making announcement). This means everyone know what the current graph structure is.

  2. Winning Conditions

    You win if there exists a directional graph from at least one point when it is possible to traverse all nodes.

  3. Losing Conditions

    There exists two or more graphs which do not share any node with each other, OR [they only share sink nodes with each other AND have at least one other node]

  4. Friend non-move

    No friend must constitute must lock box B with only one key K if box K and key B are still in play. Enemy then can simply lock box K with key B, making it isolated graph with rest of structure.

I will try to come up with some more thinking when I have more than 10 minutes to spare.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.