bushindo

Sorry, serve advantage is the statistical edge that the player who is serving has over the non-serving player. I'm just saying the chance of each player winning a point is the same regardless of whether is he has the serve or not. That is different from advantage, which happens when a player gets an point after deuce.

By a game, i mean the discrete components of sets. For each game, both players start with 0 points. They then contest for points, which we assume is a binomial process. The first player to get to 4 points wins the game. However, if both players gets to 3 points, it is called a deuce. During a deuce, the first player to score a point gets something called advantage. If the player with advantage wins the next point, he wins the game. If he loses the next point, the game goes back to deuce. And so on.

I'm sure we're all familiar with the rules of tennis scoring. In case you're not, see this link http://en.wikipedia.org/wiki/Tennis_scoring Now, a game in tennis consists of points. According to wikipedia, "a game consists of a sequence of points played with the same player serving, and is won by the first player (or side) to have won at least four points and at least two points more than his or her opponent". Assume that each point being contested is a binomial event, with player A winning with chance .55. Let's assume that there is no such thing as serve advantage. What is the chance for player A to win each game? Don't forgot to account for the possibility of deuces.

I made the problem was working backwards, basically by computing 100C25 and then see what power of 4 would be close enough to it (39, incidentally). The solution i had in mind was along the lines of what I posted in post 33, although I have to say plasmid surprised me with a solution that is actually could be accomplished by the prisoners before the sun burns out. This is why i love posting problem on this board. Time and time again the board members surprised me with a novel solution, or approaches that go deeper than my own. Reading these solutions help me learn a lot. Posting them also helps me clarify concepts in my mind. This problem, for instance, clarified the theoretical framework behind shannon's information theory. If shannon had access to this board, he would have done more with his career, I'm sure.

Some scenarios 1) You turned off your lights when you went into your room. That means your lights were on the whole night. 2) Maybe because your dad was waiting for you downstair the whole night? 3) The toy you tripped over was rigged to a wire, which is connected to an alarm in your parent's room.

James' method is very inventive, I'll have to give him prop for thinking out of the box. However, the method assumes that the prisoners from can communicate with one another. It also fails for cases where the configuration requires more than 23 low or high prisoners. Take the following example Empty, Empty, Ball, Empty, Empty, Ball, Empty, Empty, Ball, Empty, Empty, Ball, .... Basically, repeat (Empty, Empty, Ball) 25 times in a row. And then do all Empty thereafter. That would require 25 low prisoners. However, as James mentioned, there are some redundancy in the last few prisoners (only 34 prisoners are required to cover 100 jars), and you could push some more information there too. Overall, I'd say plasmid got this one in the bag. His method could be done within a reasonable amount of time, and guarantee the survival of all. Well done.

I think the issue here is that an optimal encoding algorithm on average can only compress this down to a 39-digit base-4 number. This limit is specified by the shannon information theory, and only the most optimal compression algorithm can approach it. Less optimal algorithm will result in longer encoded sequence, meaning that we need more than 39 prisoners. The issue is that the "repeat x" approach (also known as run-length encoding) is not an optimal encoding algorithm, and thus generally will require more than 39 prisoners to express the jar configuration. I expect that it will work on some cases, but certainly not all.

That is true. If we simplify James' approach by assuming that each prisoner can carry one more binary bit of information (high or low), then the possible configurations identifiable are 2*439 = 6.04 * 1023, which is still far short of the unrestricted number of configuration 2100, since the approach doens't use the information about the 25 balls. There also is an issue with how this is implemented. Each prisoner is divided into groups of high or low, and then each prisoner takes a group of 3 jars. Assuming the prisoners can go in any order they like, there is an issue of how each prisoner is supposed to convey to prisoner B which 3 jars they cover. Remember that each prisoner does not know the configuration until it is their turn to see the jars.

With any random number of balls in the 100 jars, the possible number of configurations are 2100 = 1.267651 * 1030. If you try to uniquely identify all configurations made by putting any number of balls randomly in 100 jars, it won't be possible since 39 prisoners can only convey 439 = 3.02 * 1023 configurations. The key to this is to use the piece of information that there are 25 balls. That can drastically cut down the possible number of configurations to within the range uniquely identifiable by the 39 prisoners.

You know, this forum has taught me that no matter how tightly you think you worded your problem, someone always manage to find a leak somewhere. It has already been shown that this problem is solvable with only 4 words (no silence allowed). Allowing silence will only make the problem easier. Solve whichever you like.

40 prisoners are on the deathrow. The warden gives them a chance to live. He puts 100 empty jars into room A and randomly puts 25 balls under the 100 jars. Each jar is either empty or contains 1 ball. In the other room, call it room B, the warden puts 100 empty jars, and a stack of 25 balls. The warden then divides the group of 40 into two groups of 39 and 1. The group of 39 he puts into room A. The last prisoner goes into room B. Each prisoner from room A will take turn looking under the entire 100 jars, but can not move or rearrange the contents. He then can go to room B and say one of four possible words to the prisoner. The 4 possible words are Brain, Teasers, Forum, Rules. Assume he can not convey any other information besides that word (so no facial expression, tone, body language, hand gestures, etc. ). The prisoner in room B will then have to reconstruct the permutation of the balls in room A. If the prisoner in room B can successfully reconstruct the permutation in room A after the 39 turns, all 40 will live. Otherwise they will die. The night before, the warden tells the prisoners this scheme, so the prisoners know that there will be exactly 25 balls under the 100 jars. They have 1 night to discuss a strategy. 1) Is there a guaranteed strategy for survival? If so, describe it.

Just a note, this approach requires the each of the first four prisoners to memorize 225 = 33,554,432 million combinations. There aren't 33 millions monosyllabic words in the english language, so the prisoners gotta figure something out there too.

Bravo, CaptainEd and Remnar. I was thinking of letting each prisoner memorize a list of 1024 monosyllabic alphabetized words. Each spoken word can then encodes number corresponding to its position in the list. But CaptainEd's solution is deeper and more elegant.

No moving of the balls allowed. Each prisoner is only allowed to look under 25 jars of his choice. The prisoners in room B are supposed to replicate the exact initial arrangement of the balls in room A.

Assume there are 100 balls in room B, but you don't have to use all of them to reconstruct room A's permutation. Assume all 20 prisoners get 1 night to prepare. Assume that prisoners from A can not communicate to his friend from the same room (ie. no modification of any kind to the jar's appearances, orientation, placement, etc.). Prisoners from room B can freely communicate with one another.

This is a fairly easy one. There are 20 prisoners on the death row. The warden implements a simple game. He divides the group into two groups of 10. The first 10 he puts into a room (call it room A) with 100 jars. Each jar either is empty, or has a ball underneath. The other 10 prisoners are put into a different room (call it room B) with 100 empty jars, and a stack of balls. Each prisoner from room A will take turn looking under 25 jars of his choice, away from the sight of his fellow prisoners. He then can go to room B and say 1 monosyllabic word to the prisoners there. Assume he can not convey any other information besides that word (so no facial expression, body language, hand gestures, etc. ). The 10 prisoners in room B will then have to reconstruct the permutation of the balls in room A. If the prisoners in room B can successfully reconstruct the permutation in room A in less than 10 turns, all 20 will live. Otherwise they will die. 1) Describe a strategy to do it, taking less than 10 turns. 2) Assume that the prisoners have limited memory. Describe a strategy to do it that requires the minimum amount of information to be memorized by each prisoner. That is, describe one approach that minimizes the sum of information to be memorized over 20 prisoners.

I'll explain the steps for the answer that was given earlier by krashe and yongsu.

Mr. Smith is your friend. The last time you saw him was at his wedding, where he confided that he wants to have 4 sons. His plan is to have as many children as needed until he gets 4 sons. Upon the birth of his 4th son, he would stop having kids. You lost contact with Mr. Smith, and many years later you happened to meet him again. He tells you that he got the family he wanted. He then offers you a simple chance to make money. If you can correctly guess his total number of children, he would give you 100 dollars. You were about to guess when one of these two scenario happen 1) Two girls walk in and said hi. Mr. Smith introduced them to you as his first and second children. In order words, they are his two eldest children. What is your best guess of the total number of children now? 2) In this scenario, two girls walk in and said hi. Mr. Smith introduced them to you as his children. What is your best guess of the total number of children now?

This approximation approaches the true value very fast. The true number of derangement for n=8 is 14833. yongsu's approximation is 8!/e = 14832.9. Very small difference.

yongsu got it. Well done.

10 friends are going to a party. They check in their hats at the door. The hatchecker lost the receipts for those 10, so upon their leaving, he gave them back the 10 hats, but in a randomly shuffled order. What is the chance that exactly 2 people have the correct hats?

Assume that you always show an empty chess, but not the one picked by the player. Then

Credit goes to CaptainEd

I like this one. I was eating watermelon and this post nearly made me choke with laughter.