Follow

Answer to the 100 pots problem

@MutoShack Lets take the pots int he 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.

Answer to the 100 pots problem

@MutoShack Graph theory. In fact it is one of the most understudied math fields that I personally feel is one of the most useful and easiest to understand. Especially for computer/tech people.

Answer to the 100 pots problem

@freemo

Distributed hash tables use similar algorithms to locate data, right?

@MutoShack Graph theory but also category theory.

Answer to the 100 pots problem

@freemo The assumption that my assistant can memorize 100 number pairs or has additional tools like pen & paper available is a bit bold, isn't it?

No hate, No censorship. Be kind, be respectful

We federate with all servers: we don't block any servers.

MutoShackπ½@MutoShack@functional.cafeAnswer to the 100 pots problem

@freemo

Thanks, this is absolutely wild!

By the way, what should one study in order to get better at puzzles like this? I wouldn't mind being a little bit sharper!