100 Pots Puzzle

About a year and a half ago I presented the 100-pots puzzle, which is by far my favorite programming/logic/math problem I have ever come across. It took me a while to solve it the first time I heard it (most of the work day which is where I heard it). I also was at an advantage because the solution comes from a field of math I have particular expertise in, so most people will probably have a harder time solving it.

I don’t think anyone was able to solve it last time I presented it, and had to give the official answer, I could be wrong, I need to dig up the thread. @Absinthe however did write a simulation for it in python after I had posted the answer.

Anyway here is the problem for anyone who wants to take a stab.

All answers or hints must be CW’ed

No tricks

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.

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 that 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?

@math

thinking out loud about a solution (seriously) 

@freemo @Absinthe @math

  1. try to devise a way to split the row into thirds to narrow the possibilities.

  2. each of the pots would have a pair so that each pair would add up to 101. (not sure how that’s useful at the moment…)

  3. the assistant could add up the first N pots in the sequence; or add up pots in sequence until reaching 5050/2 and mark that location by switching; or add up the pots in sequence until reaching some other meaningful number; or a combination of similar techniques.

  4. the switching of papers can communicate both the number that is switched and a position.

  5. an absolute position of switching does not need to be agreed upon with the assistant in advance and could be relative to some other predetermined attribute which is itself based on the position of a predetermined number or attribute that could be found in the row.

I really don’t know anything about statistics other than a very basic required course which has nearly all been forgotten years ago, so I probably won’t be able to get this one, but I think one or more of the techniques described above may be involved in the solution.

thinking out loud about a solution (seriously) 

@Pat

Since the assistant doesnt know the target number going in im not sure how a technique along these lines could work. The flip is at a single pair yet would have to communicate the position of every paper in every pot.

@Absinthe @math

thinking out loud about a solution (seriously) 

@freemo @Absinthe @math
It doesn’t need to communicate every one, it just needs to communicate a characteristic about the distribution so that, say, only the right or left 49 need to be opened when guessing.

thinking out loud about a solution (seriously) 

@Pat

Yes but a statistical solution would need to garuntee 100% of the time you will always get the right answer (not just that its likely).. So even if you can describe the distribution of one half vs the other you could never do so in a way that would describe with 100% accuracy which group a number belongs to.

@Absinthe @math

thinking out loud about a solution (seriously) 

@freemo @Absinthe @math
Ok. Let me ask just one hint…

Does a solution require a knowledge of statistics? Like some formula involving Greek letters?

thinking out loud about a solution (seriously) 

@Pat

No, there is no statistical solution.

@Absinthe @math

thinking out loud about a solution (seriously) 

@freemo @Absinthe @math
Alright, I’ll keep chugging away at it…

Some more thoughts: Maybe the switching of papers doesn’t communicate anything at all, but merely alters the distribution so that a guessing algorithm will find the answer…

Maybe I’ll sleep on it.

thinking out loud about a solution (seriously) 

@Pat

good luck, I will say this, the key to the solution is how you think about and model the data in the jars.

@Absinthe @math

Follow

thinking out loud about a solution (seriously) 

@freemo
yeah, I was already thinking about the minimum and maximum possible sum of the first X jars, or the last Y jars, based on the the first jars, etc…

ยท ยท 0 ยท 0 ยท 0
Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.