Riddle (not easy)

[kovarex]

There are 100 of bandits taken as prisoners one evening.
The prison manager gave them chance to change their destiny to be executed.
Every prisoner gets a unique number (1- 100), and in the manager office there are 100 numbered drawers. There are 100 number on papers (1-100) randomly inserted in each of the drawers.
The next morning, the manager will take prisoners one by one, and let them open 50 drawers, the prisoner has to find the drawer with his humber or all the bandits get executed.
Once he finds the number, he goes into another rooms and all drawers are closed, he can't say any information to others.

"Oh no, our chance to survive this are 1:2^100, this is practically zero" says the bandit statistic.
The combinatoric bandit tries to calm him down, actually there is chance for us to survive of more than 30%.
How can they do it?

[Holy-Fire]

Are prisoners allowed to shuffle the papers between the drawers they open?

[kovarex]

Are prisoners allowed to shuffle the papers between the drawers they open?

no

[Gammro]

I don't know if this may be a spoiler, so I'll just spoiler it:

Does this have something to do with factorials?

I'll try to work it out when I get home tonight.

[kovarex]

I don't know if this may be a spoiler, so I'll just spoiler it:

Does this have something to do with factorials?

I'll try to work it out when I get home tonight.

It won't help much but:

Almost all combinatorics have something to do with factorioals

[Gammro]

Haha, well I had to look up the term combinatorics to see what it actually means
I have no clue where to begin, and exams coming up. So I better focus on that first

[Nirahiel]

Answer

Let's see, each prisoner take his number, let's say "x" and opens the drawer at slot "x".
If it's not his number, he takes the number in the drawer, say "y", and now opens the drawer at slot "y".
Continue until he opened 50 drawers.
Everyone uses the same strategy.

[kovarex]

I have no clue where to begin, and exams coming up. So I better focus on that first

I think so

[ssilk]

Not understood.
Prisoner 1 takes slot 1 and in the slot, there is (what a luck) the number 2. So he opens slot 2 and there lays 3 ... and so on.
The chances that he finds his number is for the first slot 1:100, for the second 2:100, 3:100 and so on until 50:100.

And now I got lost, because when added the whole, I come to a chance of 12.75.

[wrtlprnft]

[…]

I figured something along these lines might work. Do you have any source as to how high the actual chance will be (

or, equivalently, the chance of a random permutation not containing a 51+-cycle ;-)

)? I did some testing and only got to 29.9%. That might of course have to do with insufficient randomness…

[kovarex]

[…]

I figured something along these lines might work. Do you have any source as to how high the actual chance will be (

or, equivalently, the chance of a random permutation not containing a 51+-cycle

)? I did some testing and only got to 29.9%. That might of course have to do with insufficient randomness…

That is very correct way

Math behind

Here is the math behind the calculation (skip the general way and go to the
"The above computation may be performed in a more simple and direct way"
http://en.wikipedia.org/wiki/Random_per ... _prisoners
So you end up with sum 1/51 + 1/52 ... 1/100 = 0.68.8172 (for the chance of the cycle of length higher than 50), so
31.1828% for them to survive.

[FreeER]

Math behind

I'm not sure i understand this (and I'll try again later since I'm tired anyways), but I think the best answer to this

is not a real answer, or is it

(this is legal as defined by the rules of the game) The answer: is for every prisoner to attempt to kill the prison manager, it is unlikely (though possible and I don't know how I could get an actual number) that the prison manager would be able to win all 100 fights in a row Thus at least 1 person would have a higher than 30% chance of surviving, if there are any others left this person is free to release them (or not). though obviously this lowers the chance for ALL of the prisoners to survive (probably drastically if they are not given the ability to choose who will enter first) they are not exactly the best of humanity to begin with (or are they? perhaps they are merely not pretending to hide the desires that lie within all of humanity?, hmm maybe I should not have reread Ender's Game and it's sequels lol)

[Math3vv]

i think its this : SPOILER !!

isn't it just a 50/50 chance since they only have to find 1 paper and they can open 50 out of 100 drawers

edit :

i ment 1:2 chance

[kovarex]

i think its this : SPOILER !!

isn't it just a 50/50 chance since they only have to find 1 paper and they can open 50 out of 100 drawers

edit :

i ment 1:2 chance

That is even mentioned in the OP. The statistics view of this is the first one has 1:2 chance, so if they all have to be correct, they have 1:2^100 (chance 1 / 2^100), the trick is, that actually there is better way.

[Math3vv]

i think its this : SPOILER !!

isn't it just a 50/50 chance since they only have to find 1 paper and they can open 50 out of 100 drawers

edit :

i ment 1:2 chance

That is even mentioned in the OP. The statistics view of this is the first one has 1:2 chance, so if they all have to be correct, they have 1:2^100 (chance 1 / 2^100), the trick is, that actually there is better way.

they all need to find ther own number in order to not get executed ?

edit :

:/ oke i found the solution : the first one opens 50 drawers and takes all the papers and hands them out this way once everyone went inside ther is an almoste 100% chance everyone has ther number

[Nirahiel]

Dudes, I gave the right answer..
Also Math3vv, no, each prisoner must put the papers back once he's done.

[Math3vv]

Dudes, I gave the right answer..
Also Math3vv, no, each prisoner must put the papers back once he's done.

im trying to find my own solution O_O