Saturday, 25 April 2015

logical deduction - 100 Cards with numbers in a room




The scenario is like this:


There's a room, inside the room there are 100 cards with numbers [1,100] on them (No duplications), the cards are ordered randomly.


Two persons stand outside the room, They can decide on a tactic before the following:



  • One person enters the room, he can see the order, he can make one switch between places of two numbers. (e.g: (3,1,2) ---switch 3 and 1---> (1,3,2)).

  • After the switch (Or not switching) the person flips the cards and exits the room. (Other than the switch, the person does not change the order)

  • The second person enters the room, A number between [1,100] is called out of the void, he has 50 guesses to get that number.


A few notes:




  • The cards are in a perfect line, you can't order them vertically or something like that.

  • The cards are identical, There are no particular features for specific cards or something like that.

  • You can't leave anything in the room (items / human parts / ...)

  • The two persons have no idea about the number that will be called.

  • A guess = Flips a particular card.

  • This is not the same as the prisoners, Since the first person doesn't know about the number the second person is supposed to find.



Answer



This is the same as 100 Prisoners' Names in Boxes




The algorithm is... Mentally number the cards 1 to 100 from left to right for example. turn the card with the (mental) number that you are supposed to find. If you found it, you are done.
If not, turn the cart with the (mental) number same as on the card you just turned.
The first person that goes into the room needs to make sure that there are no cycles more than 50 cards.
And this can be done easily since it can be max 1 cycle that is 51 or more. You can just break that cycle by changing 2 cards.
If you make sure there are no 51+ cards cycle you are always sure that you start in the right cycle and get to the card you need in 50 guesses or fewer.



No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...