my gut feeling about this

im thinking im not going to even try the bonus I just wrote a program and cant think of how to prove it even.

1) Solve the case with 2-players. It is easy to compute the exact survival rates if you have two players with two known accuracy rate and with a given starting position (who has the first shot)

2) RECURSIVE functions

There has to be somebody who can resolve this!!

1 2 3 4 5 6

0 1 1 0 1 1

1 1 1 0 0 1

0 1 0 0 1 0

1 0 0 0 1 0

0 1 1 1 0 1

1

If you take the columns 1 to 5 as though 0=no ball and 1=Ball

The 6th column as error detection for the row (total of appropriate row 1-5 = odd (1) or even (0)).

This can detect an error has occured but only on a specific row. That is unless the error detection signal itself was switched!

The last '1' on row 6 is fine as if no error was detected then it must be that one that was switched.

Now the only way i can see something like this working is if there were error correctors running along the bottom row as well (including column 6 as this will tell us the error lies in the error detection column and that all supplied data is correct).

My theory was to attempt to merge a ball detection and error correction into the same signal for the last full row. Example, at the bottom of row 1 (forget the lonely 26th ball jar result for now) the inmate would total jars 1,6,11,16 & 21 and give the result as odd or even)the signal should be 1 if the total of the column including jar 21 is odd and 0 if even.

I am not sure if i am within a whisker of the right answer or am on a different continent altogether.

Will somebody please put me out of my misery!!!

Hi ReArtemis, sorry for the misery. Your attempt, if I understand it correctly, if to encode the parity (odd, even) of every 5 jars with 1 prisoner. That is a good approach, but it doesn't completely solve the problem. If you want a solution, then you can read the previous posts, especially adiace's post. if you want a hint, here's one

You need 26 prisoners to encode the 26 jars. That's taken for granted. That leaves 5 prisoners to do error correction. Note that 2^5 = 32. That is, using the last 5 prisoners, you can encode up to 32 different states.

But here's a more practical hint, for balance, you should let each of the last 5 prisoner each do the odd-even business on 16 other prisoners. Each of the last 5 should operate on a different set of 16 prisoners though. The details are up to you.

1) A

2)

A = 57.7%

B = 2.2%

C= 12.0%

D= 28.4%

E= 41.7%

Shouldn't the survival probabilities for A-E add up to 1? The game requires that only 1 person survives, so survival probabilities are mutually exclusive.

part one is right for sure.. the worst case is A kills B and C kills D. The chance of E killing A then is 8%. All other cases are less then 8% after the 1st round. So A has a better chance than any one else to survive. If E dies after the 1st round, A starts the next round without being shot at, A has the best advantage.

I think you're missing a 0. E's chance of killing anyone is 16/20 = 80%. A's chance of killing anyone is only 4/20 = 20%. A can't be the best place to be because eventually the game comes down to a 2-people duel. Even if A is among the last two, his low chance of killing makes him lose way too often.

84,934,656? Is that getting closer?

Very close. I have a ballpark estimate, and it's pretty close to yours. How did you do that?

I promised final and adiace a break after their exemplary effort on Prisoner on a death row 8. Well, break's over.

There are 5 prisoners on a death row, call them A, B, C, D, and E. The warden gives them a chance to live. He gives them each a doctored gun and let them engage in a death match. Let's say the guns are modified so that their chances of hitting varies. A's chance of hitting and killing any other player is always 4/20. B's chance is always 7/20, C's is 10/20, D's is 13/20, and E's is 16/20. Assume that every single shot will either miss or kill.

The players shoot in this order, A, B, C, D, and E. Unlike Prisoners on a death row 8, prisoners don't have a choice of shooting anyone they want. Everyone must shoot someone right after him in the sequence. For example, A must shoot B, and if B is already dead, A must shoot C if C is alive, or go on to the next person if C is dead too. The person last in the sequence must shoot someone at the start of the sequence. So for instance, let's say it's E's turn, he must shoot A, or the next alive person at the start of the sequence if A's dead. The game continues until there's only 1 person left. The last person standing earns his freedom.

The warden likes you, so the night before the game he allows you to pick your position as A, B, C, D, or E.

1) What position should you pick?

Super hard bonus: What is the exact chance of survival for A, B, C, D, and E. Any method is allowed, but probabilistic method like simulation is not allowed since simulation provides an estimate of the rate but not the exact numbers. I'm not after the numbers, though. I'm looking for methods that would allow us us to compute the exact chance of survival. You don't have to implement the method, but you must describe it, and it must be doable within a reasonable amount of time.

5,337,446,400 ways.

This is a great number which I hadn't expected. So it may be wrong ???

Did you count symmetries, and did you make sure not to count the order of placement (order is not important)?. This problem should have a large number of solutions, since 8 isn't the maximum number of bishops you can put on the board. The max is 13 or 14, i think. I haven't worked a solution out completely, but maybe post your solution and we'll evaluate the logic?

Just nitpicking with this, but I'm pretty sure -1^(1/2) is not considered positive, and then curious, is it actually considered an integer?

Just to add something, there are infinite real solutions on the real and imaginary plane. Taking the log and re-arranging, you get

x/log(x) = y/log(y)

Here's a graph of x/log(x)

http://www93.wolframalpha.com/input/?i=x%2FLog[x]

Here's the equations for the solution function

http://www93.wolframalpha.com/input/?i=x%2...+%3D+y%2FLog[y]

Wolfram alpha is like the nerdy search engine, sitting in the corner at prom in weird gaudy clothes, while the popular Google is in the middle of the room talking up the ladies.

as i understood the question drops are assumed to be of negligible width and height (if its center is off your body the drop isnt wide enough to possibley hit you no matter how incredibley small the distance from you is) and the 200 drops is per cubic meter (itd be a really bad rain if it was every square meter)

but u might want to wait for bushindo if your gonna do alot of math

yeah, sorry about that. Let's say that the rain density is 200 drops/meter³, or 200 drops per cubic meter. Thanks final.

Who can run 18 miles an hours??????????????????????????????? And at that speed wind turbulence would be a factor I bet

Usain Bolt

I've always wonder whether it is better to run very fast through a constant rain, or simply to walk through it. Intuitively, running leaves you less soaked, but how much of an improvement are we talking about here. This question will settle it once and for all.

Assume that all rain drops are identical in size, and that they are falling at 9m/s straight down vertically. Their density is 200 drops/meter². You'll be walking or running through the rain. Let's make it simple and assume that you are a rectangle, and that all water that hit you will either hit in the head portion, or the chest portion. Let's say that your head portion has a surface area .06 meter², while your chest potion has a surface area of .5 meter². Let's say that water drops from head hits and chest hits count the same.

Now, you are supposed to get across a 200 meter field,

1) Let's say you take your time and walk at 1.5 m/s, how many drop of water would hit you during your walk?

2) suppose you ran across at a speed of 8 m/s, how many drops of water would hit you during the run?

1) 8!

2) 64*(64-8)*(64-2*8)*(64-3*8)*(64-4*8)*(64-5*8)*(64-6*8)*(64-7*8) = 676,457,349,120 ways

For the bishop, you're assuming that each placement of the bishop takes out 8 possible spaces on the board. However, depending on location on the board, bishops take out more than those. Consider the first placement. If the bishop is placed in the center of the board, let say at position (4,4), it would remove 14 positions from the board.

The following questions assume a 8x8 chess board. Starting with an empty chess board,

1) How many different ways can you place 8 rooks so that none can attack another?

2) how many different ways can you place 8 bishops so that none can attack another?

if a shoots at c first then continues as normal

ans 0.23834 0.29741 0.25777 0.16702 0.03946

Copied and pasted from final's work.

A shoots E first: probability of survival A-E (0.241, 0.3076, 0.30339, 0.12824, 0.01977)

A shoots C first: probability of survival A-E (0.23834, 0.29741, 0.25777, 0.16702, 0.0394)

Looks like if A shoots C first, he lowers his own survival rates by about 1 percent, but he will drastically improves D's survival rates (33% increase) at expense of C (16% reduction). It is probably to D's advantage to slip A a couple of cigarattes before the game to bribe him.

also i did 10 million trials and c was still .05% or .0005 lower then b maybe my programming is a lil off somewhere tho

I'll take your results over mine. I only ran the simulation only half a million times. So I guess we'll declare B the best spot to be, since it has a slightly better chance, and because it is not too sensitive to bribing, as we just discussed above. That is, unless adiace comes up with a exact analytical solution to this problem.

2 prisoners are on a death row. The warden gives them a chance to live. He shows them a gun that has a cylindrical barrel with slots for bullets (kind of like a six-shooter in old western movies except this gun has more bullet slots). He will slip a bullet into a random position in the gun barrel, and then have the prisoners take turn shooting at each other using the same gun. As you know, the first shot is most likely a blank, since there's only 1 bullet in the gun, thus the chance that the bullets fires on the first shot is low. However, as the prisoners take turn pulling the trigger, the chance that the bullet fires goes up accordingly. The person still standing after the gun fires wins his freedom. If the bullet fires, assume the prisoner the gun is aimed at will die.

On the day of the game, the warden show them two guns- one with 10 bullet slots, and one with 11 bullet slots. He then says that the prisoners will pick from the following two options. If a prisoner picks one option, the other options falls to his fellow prisoner by default.

A) pick a gun (10-bullet slot or 11 bullet slot ) to use during the game

B) choose to go first or second.

1) Suppose that you are prisoner 1, and you are required to pick first. What option do you pick, A or B, and what choices within that option?

2) Suppose that you are prisoner 2, and you get to pick second. Your son-of-a-gun prison-mate made the same choices as the answer in part 1, what would you pick now?

i was better off on my first guess then ever before. d and e are eliminated with great frequency a b c battle it out a and b gang on c to get it out then a just doesnt have the balls to finish the job. I still think A's in something like 90% of the bottom three and 70% of the bottom two but then again im just making that up. Ran a program to 100000 trials and low and behold

the answers above so i dont know y i started spoiler here but here it is

ans 0.241 0.3076 0.30339 0.12824 0.01977

for a through b respectively. I think the problem was we were trying to just use math. The problem was alot easier if you used math till u understand it then use reasonable predictions to help get there. all the math used to justify A B or C was wrong or incomplete tho i guess

there are no gaurentees my programming worked by i traced the first few and they were working. Method for choosing target is aim at the highest guy unless there are only two above you then aim at the guy right below you.

]

i dont know where u get these problems bushindo but my sleep schedule hates u

Your programming is correct. Well done. I have the following slightly different number, but that's because we're running simulations

Percentages for A to E: 23.9412 30.5358 30.5734 12.9128 2.0368. Turns out the best position is either B or C.

I'll tone down the computational aspect in the next couple of questions. I figure you and adiace deserve a rest. I swear you two alone have solved about 90% of my problems.

I know its time i will never get back but.....

I think that clears it up...

Another way if putting all the logic together is:

If there is an odd number of prisoners in front of you - shoot the strongest (shoot E).

If even or zero, shoot the prisoner who would go b4 you (A would shoot E, B would shoot A).

For what it's worth, I got to give you and final props for tackling this problem. These results so far looks right for the number of iterations you have, but the decision tree is pretty deep, and you probably don't want to fully extend down the entire tree.

Another route is to divide and conquer. Consider the case where there are 3 players with their known shooting probabilities, and you can probably derive exact analytical expectation for their survival rates. You'll see then that your game tree becomes a lot more managable since for any node of the tree where 2 player dies,you can substitute the 3-players result in.

An easier route is to do simulation, which is surprisingly easy once you apply the decision rules you derived earlier (the ones in bold). Since the decision rules apply for every single player, you can simulate the game in some short code, assuming that you're using a math-oriented language. Running the game like half a million times should tell you should player has the advantage. that's my prefered route, at least.

The bonus question... the order is still A to E right?

yes, for the bonus question, the game is entirely the same, proceeding in order from A to E. Except that you get to have your choice of position. Good work on part I, by the way.

so i see my mistake if a person has two people above him he doesnt want to take a shot at the highest anymore (a person never wants to chance leaving only one person above him because this means the best shot left in the game will shoot at you) but that is the only reason i see. You want to take out the highest person there is without it making you the next target so i say. A shoots at E. B shoots at E if A missed otherwise he only has two above him so he shoots at A. C shoots at D if E is dead and B (the highest that doesnt make him an immediate target) otherwise. D shoots at E if alive or C if E isnt alive. E shoots at D if e is alive. so D has the best chance for the first round.

ok the reason a shoots a E not C. Think of this as you have your place and people above and below. The only thing that matters to you is that you have at least two people above you or none so the people above you can fight it out or there are none. Now all the people above you are just identical items. The only thing that matters is if you want to kill someone above you or below you. If you kill c the logic for your opponents d and e is the exact same as if you kill e for c and d. They also only care how many are above and below them. So if you(b at the time) kill one aboive you then have one of the people above you has one up two down and one has three down. Thats what determines there new logic. There old spot is mute. So since it doesnt matter who you kill for there logic you might as well take out the best shot of the equals. So if your aiming below yourself aim one below. If your aiming above aim all the way.

now i need to rework the second part

Excellent, the answer to part I is entirely satisfactory. Good work to adiace and final. Now there's still the second part.

shoot C. Then B and D will both shoot at E. If E survives he will shoot at B or D before shooting at A. Most likely D. This will all work to A's advantage. If B shoots at D and D does not survive, E will still have to shoot B before shooting A.

How many bullets do they have? Do they continue to get turns if they miss?

Assume unlimited bullets. And players will continue to get turn on the next round if they miss. Players continue shooting until there's only 1 player left.

5 prisoners are on a death row. Let's call them A, B, C, D, and E. The warden gives them a chance of living. He gives them each a doctored gun and let them engage in a death match. Let's say the guns are modified so that their chances of hitting varies. A's chance of hitting and killing any other player is always 1/5. B's chance is always 2/5, C's is 3/5, D's is 4/5, and E's is 5/5. Assume that every single shot will either miss or kill. A player must shoot someone on his turn. Each player knows his gun's accuracy rate and the others' as well.

The players take turn shooting in the following order: A, B, C, D, and E. During his turn, a gun slinger can choose to shoot at anyone he wants. If a player is killed, then the order of shooting will continue in the same sequence but with the dead player skipped. Players take turn shooting until there is only 1 player remaining.

Assume that each player wants to maximize their own chances of living, and that each player knows that the others will do the same. Answer the following

1) What should A do on this first turn?

2) What should B do on the second turn?

3) What should C do on the third turn?

Super hard bonus: Suppose that the warden likes you, so the night before the game he allows you the chance to choose your gun. Essentially he allows you to choose your position as A, B, C, D, or E. Which position should you choose to maximize your chances of living, assuming that everyone plays optimally? Assume that the other prisoners don't know about this so they won't unduly target you out of spite.

How is an avg gun slinger defined? You have not told us that A is an avg gun slinger. For all we know A could be an amateur or the best in the world.

The average gun slinger accuracy function should be defined similar to how you approached it, namely by imagining what a population of gun slinger might look like and then taking some sort of 'average'. The problem with your answer for part II earlier, I think, is that your assumption is way too pessimistic. You allowed the multiplicative constant p to vary from 0 to infinity, but that essentially says that A and B are near the absolute bottom of gun fighting skills spectrum, that piece of information, however, isn't warranted by the original post, though.

In real life, this problem is a bit more intuitive. If a gunslinger has prior encounters with other gunslingers, he can probably estimate how good he is compared to an typical gunslinger. When A meets B, from A's perspective, if he knows nothing about B, he should assume that B is an average gun slinger. A then can compare his accuracy function to the guessed average function for B and decide accordingly. That way, if A is an amateur or the best in the world, he can make good use of that information.

There is a strategy, IF the prisoner in room A who's communication is intercepted is aware of the interception, that prisoner can then report back to the remaining prisoners so they are aware of the prisoners position that has been compromised. Because there are only 26 jars and 31 prisoners, the last 5 prisoners that go can use binary code ( green is one, red is zero) so that they can communicate which prisoner number had been randomly changed and the prisoner in room B can add or remove the ball in that jar. Then they live.

Just a question, what if the interception is in the last 5 prisoners, how do the prisoners handle that? This approach assumes that the each prisoner knows whether their communication has been compromised, and that each prisoner can communicate with his mates afterwards. It is not what I intended but it poses a good question, so please consider it.

Don't forget to work on the harder case too, which assumes that the interception is random, and each prisoner, on his turn, doesn't know whether his communication has been compromised.

There are 32 prisoners on a death row. The warden gives them a chance to live. In one room, call it room A, the warden puts 26 jars and put a unknown number of balls inside the jars. Each jar is either empty or contains 1 ball. In room B, the warden puts 26 jars, and 26 balls in a separate stack. He divides the prisoners into two groups, 1 group of 31 and 1 group of 1. The group of 31 goes inside room A, and the other prisoner goes into room B.

There is a lever in room A, which is connected to two lights in room B. Depending on how one pulls on the lever, it will either make a red light or a green light goes up in room B. The game proceeds as follows. Each prisoner in room A will take turn going up and examine the 26 jars away from the sight of his fellow prisoners. He can not rearrange or modify the jar in any way, shape, or form. He then must pull the level and make either a red light or green light goes up in room B. If he attempts to communicate any other information besides those two bit of information (i.e. waiting a certain amount of time before pulling the lever, pulling the level more than once, not pull the level at all, etc. ) all prisoners will be executed immediately. The order in which the prisoners take their turn at the jar is randomly determined by the warden.

If the prisoner in room B can reconstruct the arrangement of balls inside the jars in room A at the end of 31 turns, all prisoners will live. However, there's a catch. The warden will randomly intercept the communication of 1 prisoner from room A to room B and flip it. For example, suppose that the warden choose to flip prisoner 16's communication. Let's say that number 16 examines the jar and choose to make the green light goes up, the warden would intercept the electronic signal and make the red light goes up instead. Likewise, if number 16 were to choose to make the red light goes up, the warden would make the green light goes up instead.

The 32 prisoners are informed of this game the night before, so they know that the communication of exactly 1 random person will be compromised during the game. They have 1 night to prepare.

Is there a strategy to guarantee the survival of all prisoners? Describe it.

i didnt reply earlier because i thought the question was pretty much answered but heres what i got

i got 44 and the logic used on the first post that got this answer i think is right but i found it by a different yet entirely related method My only assumption to part one is that your opponent would have shot before you if you were both going to shoot on the same step

you motivation to shoot is your chance of killing if you shoot + you chance of dieing if your opponent shoots next turn

and your motivation to not shoot is you chance of dieing if you shoot + your chance of surviving if your opponent shoots next turn

you shoot if your motivation is greater to shoot then to wait therefore

1.25k+(k+1)>(100-1.25k)+(100-(k+1))

2.25k+1>200-2.25k-1

4.5k+2>200

k=44 is the moment that this happens so guy with 1.25k function would fire then.

guy with 1k function knows this but has no better survival chance before this so also 44

now part two is different if you had to hard code a method then shoot at .50 but if you can make some gut calls then thats different

if you assume that your other enemy is ur average guy meaning hell shoot as soon as he has a >50% chance of survival then its quite simple.

if he gets to 50 before you then nothing you could have done. You shooting at this point is <50 so its a better chance if he shoots. If you get to 50 first (which by the assumption is the same as getting to 50 at all) then worst case scenario is losing by a margin slightly smaller the derivative of your probability function (which is reasonable to assume is a constant for reasons i really dont feel like explaining) or even better (50/the turn your on)

so wait untill a significant margin (i would say 10) and thats what you get (so wait till you hit 60)

now if you can guess (accuracy helps but if you have no confidence in your guess then shoot at .50) your skill compared to his and assume he can do the same then shoot at the appropriate time. you think hes twice as good as you shoot at 40ish (33 is break even)

if you think hes half as good shoot at 70 ish (66 is break even)

Well done, final. Your answer to part II is satisfactory. I also like the extension to the case where A or B thinks he's a bit better than the opponent. In general, even though A or B may not know about their opponent's accuracy function, a reasonable approach is to assume that your opponent is an average gun shooter, and base your decision from there.

An interesting extension from here is that if A or B gets an impression about their opponent's skill (better, worse, equal), then they should incorporate it into their consideration, as final have suggested. This allows interesting ramifications. If A and B can communicate together, and if B thinks that he is weaker than A, it is to B's benefit to bluff and pretend to be a stronger shooter than he really is.

For A:

Chance of surviving = Chance of not being shot * Chance of killing

P = x/100 * (1 - x/80)

dP/dx = 1/100 - x/4000

1/100 - x/4000 = 0

x = 40 steps.

For B:

P = x/80 * (1 - x/100)

dP/dx = 1/80 * x/4000

1/80 * x/4000 = 0

x = 50 steps.

Sorry for the double post, i waited too long and the edit function went away. This approach is the answer to this question, "If A and B were to shoot simultaneously at step k, what is the best place for each person to shoot so that he lives and the other one dies?"

Now, let me clarify my statement earlier. If A were to shoot at 44 paces, he is guaranteed minimum chance of living of 44%. If he were to shoot at 40, his minimum chance of living is 40%. See adiace's graph for the proof.

I think you might be missing the key info that there is only 1 bullet in each person's gun, and that if the person who shoots first misses, the second person will have a guaranteed 100% chance of killing, since we assume that it's a closed room and there's nowhere to run.