We created track can be described like this: \ (2 \ to33 \ to13 \ to \ dots \). When such a course

Today I came across the most amazing puzzle emmys 2011 date - probably one of the best riddles I enjoyed sorting out - and I want to share it with the blog. The idea is relatively simple: there is a room with 100 boxes, each box has a numbered from 1 to 100, so that each number appears exactly once in one of the boxes (in other words, we have a permutation on the numbers from 1 to 100). Alice enters the room, looking emmys 2011 date at the notes in any boxes, and if she feels like it - toggles between two notes. Only one change - not allowed to do more than that. Leaves the room, and into Bob. Bob entered the room give it a number emmys 2011 date from 1 to 100, and demand of him he found the box where the number is located. The catch: he is allowed to open only 50 boxes (but allowed him to do it serially, when he decides what he wants next box to open by what he has seen so far).
Probably root of the matter lies in how this method of operation which Alice and Bob have agreed in advance - the method by which Alice decided whether and how to replace the notes is something she agreed to it in advance with Bob. However, once the game starts does not include any communication - Alice can not tell Lviv which is which box, and Bob certainly can not tell Alice what number will ask him to find that he does not know it at the time that Alice enters the room (and in fact, the jury can see a replacement Wallis and choose deliberately performed a number of "bad" if he feels like it).
Okay, so what's the solution? As usual in these matters, to the solution immediately that "no big deal" in the sense that the solution does not reflect all the thinking and direction failed when I tried to solve the riddle, and the ever-improving understanding of what goes slowly there. Present the solution and be done with it that kind of charm, but there is really no escape from it. Just say my first idea was completely different solution - I thought maybe Alice choose the numbers one and put it in a box first, and Bob First of all open the first box, called the number, and will draw from information emmys 2011 date on the composition of the other boxes. The challenge here, of course, is that the information should help in "global" - any question MAY ask Bob. Well, this direction is a dead end - if you play with it a bit (especially for simple cases like 4 boxes) realize very quickly that you can not provide enough information Lviv only that single note. So I gave up on the idea that Alice gradually move Lviv some information, emmys 2011 date or Bob as he could understand - or - How to value it more seems valid. Instead, I began to think about ways in which Bob could discover the number "blind". Maybe he has a search method succeeds not usually bad, and Alice can help with its single replacement and ensure that the system will always work pretty well? It is also exactly emmys 2011 date what happens in the end.
One search method that Bob can take it is just open boxes randomly. Well, it will not lead to anything probably. emmys 2011 date He also can open boxes serially - 1,2,3 and so on. That, quite clearly, will not lead to anything. Next method seemed the most natural, though perhaps not agree with me. The idea is to travel in foreign circles that make up the proceeds. emmys 2011 date What does this mean in practice? Very simple. emmys 2011 date Suppose they say Lvov look for the number 2. He opens the box No. 2. Whether two there, great. Otherwise there's another number, say 33. Currently Bob opens the box 33. Whether two there, great. Otherwise there's another number - say, 13. Then Bob will open the box 13 ... you get the point.
We created track can be described like this: \ (2 \ to33 \ to13 \ to \ dots \). When such a course can be completed? Only when Bob comes to the number of the box already appeared in the past. I argue that this number must be 2. Why? Well, suppose emmys 2011 date it is another number, emmys 2011 date say 33. Then it means that Bob opened a box which was written the number 33 - but he's done it before, at first, when he opened the box number 2! And because -33 is not listed twice in boxes, Bob could not have met him again before he encountered in 2. So Bob comes eventually to 2, but the question is - how fast?
Unfortunately, it may get there very slowly - it may pass over all other boxes until it gets to 2. But here Alice came to his aid. Alice opens all the boxes so you know exactly which all the circuits that make up the proceeds. If you have a long cycle - length of more than 50 - then Alice will replacement to split it into 2. Otherwise, Alice will not do anything. Anyway after Alice finished all circles that make up the proceeds are maximum size 50, so a trip like Bob performs them over in 50 tests at the most, and be done. If so, what Bob does is simple: If they told him to check the number the \ (k \), is just open the box the \ (k \) - home and away he goes under the number he found inside the box opening. The circle will end just as Bob finds the desired number.
Remains only to explain how Alice performs the split, but it's simple. Suppose we have a circle \ (1 \ to2 \ to3 \ to \ dots \ to n \ to n +1 \ to \ dots \ to2n \ to1 \) (the numbers are arranged in ascending order for simplicity). So the length of the circuit is \ (2n \) and we want to split it into 2 different circuits length emmys 2011 date \ (n \) each. Currently the situation is such that the tin number \ (2n \) has the note \ (1 \), and box number \ (n \) has the note \ (n +1 \). Alice just replace these two notes. The result? Circle \ (1 \ to2 \ to3 \ to \ dots \ to n \ to1 \) (the box \ (n \) is currently the number 1) and the circle \ (n +1 \ to \ dots \ to2n \ to n +1 \ () that the box number \ (2n \) is currently in the note \ (n +1 \)). In this way, Alice is able to split any large circle two relatively small circuits, and it has been really the end of the solution.
I find it a great puzzle - has the mystery element of how you can make something that initial feeling is that it is not possible at all, and the elegant solution short, looked like magic. I hope you enjoyed them. This post was posted in games and mathematical puzzles, with tags simplicity is sophistication, changes, riddles, from gadial. You directly to this post with a link has