The 100 Pots Logic Puzzle

Some people asked me to share a very difficult yet simple logic puzzle that has stumped my friends. It is also my favorite interview question.

First off some background. The problem is not a trick question, as much as it may seem like one. There is no play on words, no hidden exception. Everything in this problem is exactly how it is presented and the answer doesn’t rely on any slight of hand. Take this puzzle at face value.

Also ALL ANSWERS NEED CONTENT WARNINGS I do not want you spoiling it for others. This goes for questions and hints too.

Now on to the puzzle:

There is a room with 100 jars with lids on them all in a row. There is also a stack of papers, 100 papers each labeled 1 to 100. The papers are shuffled and one paper placed into each pot randomly.

You and your assistant are in an a joining room. Your assistant is allowed to enter the room, look in all 100 pots, and if they wish they can pick any 2 pots and switch the paper in them. They can only do this one time, they do not have to do this they can choose to also do nothing. At this point they leave the room, without talking to you.

Next, someone tells you a random number from 1 to 100. Your goal is to enter the room and open a pot tht has that number in it. You are allowed to open, at most, 50 of the pots.

Whatever process you use to open those pots must guarantee that by the time you open the 50th pot that the number you were given will be found. Obviously your assistant didn’t know what the number is at any point.

What rules do you give your assistant, and what rules do you follow, to ensure you are successful?

Official answer and explanation

[spoiler]
Lets take the pots in the room and arbitrarily (doesnt matter how) number them 1 - 100 (or 0 - 99 depending on how you index), we can use this as an ID. So we have pots numbered 1 - 100 as well as numbers 1 - 100 (no repeats) randomly placed in these pots, as you already know.

Next is where the key to all this comes in, it is a basic realization. If you open a pot, any pot, the index of the pot (lets say 5) will either be the same as the number in the pot, or different (obviously).

If it is a different number, and then you go to the pot that has the ID that matches the number in the current pot, what does that mean? Well if you start by opening ID pot 5 as we said and it contains number 42 in it, then we open 42 , well we can no longer say “it will either have a different number in it than its own ID or the same”. That statement is no longer true. We know it can’t have the number 42 in it at all (since pot ID 5 has that number in it). So we know this next pot must have a number other than 42 in it. It can literally have any number but 42 in it. We can say however “Pot 42 will now have either the number 5 in it, or any number other than 42”. If it has 5 in it then it creates a cycle and just repeats, if it has another number in it then the pattern continues.

If we follow this pattern out, every time opening the next pot in the pattern we can assume a few things. First off when we open a pot one of two things will be true about the number int he pot. Either it will contain a number that is completely unique (And doesnt loop back and create a cycle), or it does create a loop back. Moreover since we know if it contains a loop back that it can not point to any pot other than the pot we started with (because all the other numbers have been taken) we know that eventually when we do encounter a loop it must go back to the pot we started with opening, in this case pot ID 5.

We can also conclude that since every pot contains some number that no matter what pot i start by opening it will be part of a cycle of some size (though that size could be all 100 pots).

So we have an important realization here. If I start at some pot with some ID we call X, and follow the pattern i described above, then eventually somewhere in the cycle you are guaranteed to find your number, X (it will always be the last pot you open before the cycle loops back).

So now consider the problem again. If you are given some number when you enter the room, lets say the number 5 again. As long as you start with the pot with ID 5 (again number them however you want, its arbitrary), and follow the rules above then you are guaranteed to find the number 5. However as i said you might have a cycle of all 100 pots, so this alone wont solve the problem.

So what does your assistant have to do? Look at every pot and draw out all the cycles for all the pots and numbers on a piece of paper (or remember it in their mind). The only time your tactic above would fail is there is a cycle of 51 pots or more. However since 51 pots is a majority of the total number of pots there can only be, at most, 1 cycle of 51 pots or larger. So if your assistant identifies if there is a 51+ pot cycle, and if there is use their one allowed swap to break that cycle into two smaller cycles, then yoru assistant has guaranteed there are no cycles larger than 50 pots.

Now after your assistant has done what I just described, if you start with the pot that has the ID of the number you are given, and follow the cycle until it loops you are guaranteed to find the number assigned to you and you are guaranteed to find it in under 50 pots.
[/spoiler]

I asked for this to be put up for further discussion. I have written some python that demonstrates the swap rule and strategy required to solve the puzzle. For anyone interested here is a link to the repo:

Apparently, there are related puzzles to this. While sharing this one among friends some of the others were told to me. But they have raised a question, and though I am not sure how to make it into a puzzle, the question itself remains an interesting one.

In the puzzle the potential ability to make one swap is instrumental to the guaranteed success. If you were to take that away what are the chances, given attempting the same/similar strategy? So given that as it is you have a 50:50 chance of success by picking any 50 pots, are there any strategies that would increase your odds? For example, if you choose the corresponding pot then follow its permutation chain, then you would succeed 100% of the time where there are no permutation chains longer than 1/2 the total number but you would fail in some % of the time when one chain was longer even by 1.

Short of creating all the different orders and calculating the corresponding chains (and their respective lengths) how does one determine these chances? Is this something that requires brute force calculations or are there formulas to determine the chains?

1 Like