[Guest]

An interesting puzzle I came by:

Two prisoners are given a chance at freedom (as always) by being given a riddle, there is a room, inside that room are 100 cards numbers from 1-100 and turned on their backs, they are in a row in random order, the first prisoners is let in the room and he is allowed to look on all the cards and then he can switch only two, he exits the room and the second prisoners is let in, the second prisoner is given a random number and he is only allowed to flip 50 cards and find the number he was given...

The two prisoners cannot communicate with each other during the test, the first prisoner is only allowed to switch places of two cards and no more (no leaving hints by tilting a card or whatnot)...

[unreality]

a few questions:

the random number is 1 to 100 inclusive right?

and

when you say "switch two", does that mean he can make 2 total swaps, or just 1 swap (involving switching the locations of 2 cards)?

Also, can he choose to do zero swaps?

[wolfgang]

An interesting puzzle I came by:

Two prisoners are given a chance at freedom (as always) by being given a riddle, there is a room, inside that room are 100 cards numbers from 1-100 and turned on their backs, they are in a row in random order, the first prisoners is let in the room and he is allowed to look on all the cards and then he can switch only two, he exits the room and the second prisoners is let in, the second prisoner is given a random number and he is only allowed to flip 50 cards and find the number he was given...

The two prisoners cannot communicate with each other during the test, the first prisoner is only allowed to switch places of two cards and no more (no leaving hints by tilting a card or whatnot)...

You said,the cards are in a row in random order,that means,switching between two of them means nothing!

Am I right?

[superprismatic]

Solution based on cycles of a permutation:

Let's say player 2 got N as his number. He does the following:

1. Let X=N.

2. Pick up the Xth card.

3. If the card he just picked up in step 2 has the number N on it, he is done.

4. If the card he picked up in step 2 has Y(≠N) on it, let X=Y and go to step 2

He will always find his number within 50 card picks as long as

there are no cycles greater than 50 of this algorithm in the deck.

But player 1 can always insure this by using his single card swap to

split the largest cycle in the deck in half (or most nearly so, if the

cycle length is odd). The sum of all cycle lengths must be 100, so

the worst case happens when the deck has a single cycle of 100.

In this case, the first player would have split this into 2 cycles of 50.

In the event that all cycles are of length 1 to start with, player 1

can just create a single 2-cycle with his swap, leaving the 98 other

1-cycles alone.

Edited December 27, 2010 by superprismatic

[Guest]

superprismatic solved it, good job...

For those who wanna solve it themselves:

a few questions:

the random number is 1 to 100 inclusive right?

and

when you say "switch two", does that mean he can make 2 total swaps, or just 1 swap (involving switching the locations of 2 cards)?

Also, can he choose to do zero swaps?

You have all cards from 1 to 100 and they are randomly ordered in a row, as in they are shuffled then placed on the table with their backs turned...

Swap the location of 2 cards, as in if the cards were 123456 the prisoner could decide to switch 312456...

0 swaps won't matter, you could say he swapped a card and itself...

You said,the cards are in a row in random order,that means,switching between two of them means nothing!

Am I right?

No it does mean something...

Edited December 27, 2010 by Anza Power

[Guest]

... "turned on their backs" (i.e. face up) for the 1st prisoner. Cards were not re-arranged for the 2nd prisoner, who enters the room, also sees the cards face up, and easily locates the card per the chosen numeral.

[wolfgang]

superprismatic solved it, good job...

For those who wanna solve it themselves:

You have all cards from 1 to 100 and they are randomly ordered in a row, as in they are shuffled then placed on the table with their backs turned...

Swap the location of 2 cards, as in if the cards were 123456 the prisoner could decide to switch 312456...

0 swaps won't matter, you could say he swapped a card and itself...

No it does mean something...

Sorry,I disagree with you !see this arrengement and tell me which card I switched: 4127536

[Guest]

Sorry,I disagree with you !see this arrengement and tell me which card I switched: 4127536

Well you need an even number of cards, let's say 8 was at the end (cause the 2nd prisoner will have to pick exactly half)

Now you see this makes a graph of three series:

4 -> 7 -> 6 -> 3 -> 2 -> 1

5

8

(4th card reads 7, 7th card reads 6...etc, and 5th card reads 5 and 8th card reads 8)

Now you see if the second prisoner had to find number 5 or 8 he'd instantly find them, but let's say he had to find number 3, he'd go to the 3rd card: 3 -> 2 -> 1 -> 4 and he'll run out of cards (he's only allowed to look in 4)

So what the first prisoner does for him, he "breaks" the large chain into smaller <4 chains, one way to do it is like this:

So now any number that the second prisoner gets he'll surely find it in 4 or less tries...