bushindo
-
Posts
719 -
Joined
-
Last visited
-
Days Won
5
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by bushindo
-
-
You can do it with 18. In place of each prisoner in the solution to the previous problem, use a pair. It counts as dying only if both prisoners die--otherwise it counts as survival. Now do as before. It may be possible to do with less than 18, but i would not no how.
That's a good start. It is possible to require a few prisoners less than that though.
In any circumstance will the accomplice not take poison to pevert the decision making process?
If selected as a taster, the accomplice will definitely commit suicide by drinking his own supply of poison. However, keep in mind that the emperor has many prisoners, and in the random selection procedure it is very possible that the accomplice is not chosen as a taster.
-
This is a variant of ujjagrawal's excellent puzzle
Suppose that like ujjagrawal's puzzle, an assassin infiltrates a king's cellar and poisons 1 of the king's 500 wine bottles. Upon being detected and cornered, the assassin takes a suicide pill and dies.
Anyone who consumes even the most minute amount of the poisoned wine will die between 12 and 24 hours. Consumers of the poisoned wine exhibit no other symptom besides death, and the poison can not be detected by any other means.
The emperor decides to use some prisoners to taste the wine in order to determine the poisoned bottle. There is one catch, however. It is known that the assassin has precisely one accomplice among the prisoners. The accomplice has access to the same poison that the deceased assassin used to envenom one of the king's bottle. If the accomplice is chosen as one of the tasters, he will surreptitiously consume the poison regardless of which bottle he is given to drink in the hope of corrupting the deduction process.
The emperor does not know which of his prisoners is the assassin's accomplice. The emperor is intrigued by this logical puzzle, and he figures that he can simply use some extra prisoners to compensate for this unknown unreliable taster. What is the minimum number of prisoners (and the tasting procedure) that he would need to use in order to correctly find the poisoned bottle among the 500 bottles within 24 hours?
-
Perpetuating the puzzle propagation:
There are 5 bags, of which one contains 4 blue balls, one contains 3 blue balls and 1 red ball, one contains 2 blue balls and 2 red balls, one contains 1 blue ball and 3 red balls, and the last contains 4 red balls. You do not know which bag has which distribution.
You will be allowed 10 draws, each from any bag of your choosing, and your goal is to draw as many of the same colored balls as possible.
What is your play (by which, I am assuming you're a probabilistic optimalist, like me
)?Here's a play,
We first need to develop some notations to represent any state of the game. Let Bi represent bag i, where i goes from 1 to 5. Let ci represent the color on the i-th draw, and let mi contain information about which bag was chosen on the i-th draw. For instance, if we choose bag 2 on turn 1 and it turned out that we got a blue ball, then c1 = Blue and m1 = B2. The state of the game at turn i can be represented by
Ci = [ ci, …, c2, c1 ]
Mi = [ mi, …, m2, m1 ]
What we need to do next is to develop a function for evaluating the chance of drawing a particular color from bag j at turn i given the game state Ci and Mi. That is, we want the probability function
P( Bj = color | Ci, Mi )
For example, at the beginning of the game, P( Bj = Blue | C0, M0 ) is obviously equal to 1/2 for all bags. If we choose bag 1 on the first turn and got a Blue, then
P( B1 = Blue | C1 = {Blue}, M1 = {B1} ) = 0.6666667
P( Bj = Blue | C1 = {Blue}, M2 = {B1} ) = 0.4375 for j = 2, 3, 4, 5
So, let's assume we have the probability function for now (see the end for derivation), the algorithm is as follows
1) At the first turn, obviously just pick any random bag.
2) At turn i, we look at the drawn colors so far, and we want to pick the color = mode(Ci), i.e., the color that has appeared most often. We evaluate the probability function above for each bag and the most frequent color. That is, we evaluate
P( Bj = mode(Ci) | Ci, Mi ) for j = 1, 2, …, 5
3) Pick the bag that has the highest probability of drawing the most frequent color. Repeat until the end of the game.
**********************************************
Computation of P( Bj = color | Ci, Mi )
So, let's talk about the computation of the probability function. The main idea is as follows, we have 120 possible permutations of the 5 bags. We will simply keep track of a probability estimate of each of those 120 states, and update the likelihood of each permutations when we get new information. The following is going to be done in pseudo code,
Let A be a 120x5 matrix of permutations, where the bags are labelled from 1 to 5. For instance, the first 3 permutations may be represented as
[,1] [,2] [,3] [,4] [,5] [1,] 1 2 3 4 5 [2,] 1 2 3 5 4 [3,] 1 2 4 3 5
Let Pi be a 120x1 vector of the probability of the permutations at time i. For instance, at the beginning of the game, it is easy to see that P0 is a constant vector with each element being equal to 1/120 (all permutations are equally likely). Let Ri be a 120x5 matrix of the number of Red balls within each bag and within each permutation at turn i, and let Bi be a 120x5 matrix of the number of Blue balls. For instance, at the beginning of the game, the first 3 rows of R0 and B0 corresponding to the 3 permutations of A above areRed matrix [,1] [,2] [,3] [,4] [,5] [1,] 0 1 2 3 4 [2,] 0 1 2 4 3 [3,] 0 1 3 2 4
Blue matrix [,1] [,2] [,3] [,4] [,5] [1,] 4 3 2 1 0 [2,] 4 3 2 0 1 [3,] 4 3 1 2 0
At turn i, without loss of generality let's assume that ci = Blue, we can update the parameters Pi, Ri, and Bi as follows,
T = Pi-1 * Bi-1[ , mi ]/ ( Bi-1[ , mi ] + Ri-1[ , mi ] )
Pi = T/sum(T)
Note that the above vector multiplications and division are done element-wise. We then need to update the Ri-1 and Bi-1 matrix to reflect the fact that we took out one blue ball
Ri[ , mi ] = Ri-1[ , mi ]
Bi[ , mi ] = Bi-1[ , mi ] - 1
If we get negative values in Bi, we'll have to set those to 0.
Finally, the probability function can be computed as
P( Bj = Blue | Ci, Mi ) = sum( Pi * B[ , mi ]/ ( B[ , mi ] + R[ , mi ] ) ).
The case for Red color being drawn can be computed analogously.
-
I'm trying to see where my thinking has gone astray:
p(other is girl) =
p(other is girl if Ned spoke) x p(Ned spoke) +
p(other is girl if Red spoke) x p(Red spoke) +
p(other is girl if Ted spoke) x p(Ted spoke) +
p(other is girl if Zed spoke) x p(Zed spoke).
If the reporter had worn a name tag, we're done: we know p(other is girl if x spoke) for each x.
We're only uncertain about the name tag, it seems. Jed makes each tag probability 25.
Bushindo, I perceive an extra level of conditionals.
You're right, there is an extra layer of conditionals. We need to incorporate the information about what was said ("One of the kids is a girl") into the calculations as well.
The equation that you wrote below in green is correct mathematically. (I replaced your 'If' with 'Given' since it fits better into the Bayesian framework)
p(Other is girl) =
p(Other is girl Given Ned spoke) x p(Ned spoke) +
p(Other is girl Given Red spoke) x p(Red spoke) +
p(Other is girl Given Ted spoke) x p(Ted spoke) +
p(Other is girl Given Zed spoke) x p(Zed spoke).
However, the left hand side, P(Other is a girl), is not the solution to this puzzle. The probability that we want is the probability that "Other is a girl" given that a reporter (we don't know which one) said 'One kid is a girl'. That is, we want P( 'Other is a girl' Given 'One kid is a girl').
From my derivations in we can see that P( 'Other is a girl' Given 'One kid is a girl') can be expressed as
P('Other is a girl' Given 'One kid is a girl' ) =
p('Other is girl' Given [ Ned spoke and 'One kid is a girl' ]) x p(Ned spoke Given 'One kid is a girl')
p('Other is girl' Given [ Red spoke and 'One kid is a girl' ]) x p(Red spoke Given 'One kid is a girl')
p('Other is girl' Given [ Ted spoke and 'One kid is a girl' ]) x p(Ted spoke Given 'One kid is a girl')
p('Other is girl' Given [ Zed spoke and 'One kid is a girl' ]) x p(Zed spoke Given 'One kid is a girl').
Essentially, we don't know which reporter is the speaker, so take a weighted average over all reporters based on the conditional probabilities P( Reporter Given 'One kid is a girl'). Now let's examine values of these probabilities
Since uncle Jed drew the names out of the hat, we have
p(Ned spoke) = p(Red spoke) = p(Ted spoke) = p(Zed spoke) = 1/4
From Yoruichi-san's analysis, we have
p(Ned spoke Given 'One kid is a girl') = 1/7
p(Red spoke Given 'One kid is a girl') = 3/7
p(Ted spoke Given 'One kid is a girl') = 2/7
p(Zed spoke Given 'One kid is a girl') = 1/7
From the equation in green above, it seems that was solving for p(Other is girl Given Ned spoke) and p(Other is girl Given Red spoke) and so on. However, those probabilities are actually different conditionals. They actually are
p('Other is girl' Given [ Ned spoke and 'One kid is a girl' ]) = 1
p('Other is girl' Given [ Red spoke and 'One kid is a girl' ]) = 1/3
p('Other is girl' Given [ Ted spoke and 'One kid is a girl' ]) = 1/2
p('Other is girl' Given [ Zed spoke and 'One kid is a girl' ]) = 1
So I believe the mistakes in are as follows
1) It solves for a different quantity, P(Other is a girl) versus P(Other is a girl Given 'One kid is a girl'), with respect to the solution
2) It actually computed p('Other is girl' Given [ Ned spoke and 'One kid is a girl' ]) instead of p('Other is girl' Given Ned spoke) and so on.
-
Did I forget to mention that uncle Jed had put their names in a hat and drew one of them to speak?
More interestingly, does the "One Boy, One Girl" thread any longer have a definitive answer?
If Ned said it, probability is 1 that it is GG;
If Red said it, it is either BG, GB, or GG, probability is 1/3 it is GG
If Ted said it, you know the older child is G, probability is 1/2 it is GG
If Zed said it, you know the coin selected child is G. He mentions sex of other child (G) so probability of GG is 1
1/4*1+1/4*1/3+1/4*1/2+1/4*1=17/24 = probability that it is GG.
Regarding these answers
-
The OP intended to deny bias among reporters, since each can comment on any two-child family,
Even tho some statements are denied to some reporters for some families.
However ...
The greater intent of this puzzle was to cool the debate somewhat, housed in the Teanchi-Beanchi thread.
We don't know the algorithm used by the reporter, and now we understand that it matters.
Most of us "1/3" zealots assume the reporter was like Red.
But there is no basis for that [or any other] assumption.
Ned:
BB BG GB one is a boy
GG one is a girl
1
Red:
GG GB BG one is a girl
BB one is a boy
1/3
Ted: first-mentioned is older child.
BB BG one is a boy
GB GG one is a girl
1/2
Zed: first-mentioned is coin-selected child.
BB BG one is a boy
GB one is a boy
GG one is a girl
1
Avg = (6+2+3+6)/6/4 = 17/24 = .7083
Some comments
Let A be the spoken statement "One of the children is a girl",
Let S stand for speaker,
The calculation highlighted in red (see quoted post) implicitly assumes that given the statement A, all speakers have the same chance of being the one who said it. In other words, the implicit assumption is
P( S = Ned | A ) == P( S = Red | A ) == P( S = Ted | A ) == P( S = Zed | A )
If we put in the proper conditional probabilities, the equation becomes
1 * P( S = Ned | A ) + (1/3) * P( S = Red | A ) + (1/2) * P( S = Ted | A ) + 1* P( S = Zed | A )
= 1 * (1/7) + (1/3)* (3/7) + (1/2)*(2/7) + 1 * 1/7 = 4/7
-
Thought I had a question, but it turned out to be unnecessary. Agree with Yoruichi-San on the answer. Nice puzzle!
-
Hi jim, welcome to the Den.
Sorry I didn't see your post earlier.
Yes, that question would do it.
I had in mind the idea inthe previous post,
and now three others have been given.
Nice!
Thought I had a nice question based on Fermat's last theorem, but turned out I was mistaken. Nice solutions, bonanova, Eventhorizon, and jim.
-
I just thought of a positive integer less than 4
said Alex to his friends Davie and Jaimie last
night at Morty's while idly tossing darts in the
back corner of the room.
It was a slow night, and Alex loved to keep things
interesting, as best he could. Now if I were to
give you two questions of the standard Yes/No
variety, I have no doubt that even you two geniuses
could deduce what my number is. So, I'll raise
the challenge a bit, and buy the next round of
beer, if you can tell me my number - with absolute
certainty - after asking me a single Yes/No question.
Davie didn't even bother to stroke his beard.
Can't be done, pure and simple. A waste of time,
If you ask me, agreed Jaimie. Neither of them
noticed the twinkle in Alex's eye as he continued
to reel them in. All right, I'll turn it around. You
pick the number and I'll ask the question. And if
you can't answer it, you'll have to say so. But it
will cost you to play. If I get it right, with certainty,
you buy. If I get it wrong, I'll buy. Either of you
up to that?
Jaimie Just walked away, muttering something
quietly about complexity. This time Davey did
stroke his beard and after a minute said, OK,
you're on.
Who bought the next round?
Here's one approach
Let x be the positive integer less than 4. Is ( [ -1/(x - 3 ) * 2 ] modulo 2 ) > .5 ?
-
1
-
-
Case 1: No Mixed
WBB (2) - Seat 1
BWB (2) - Seat 2
BBW (2) - Seat 3
(Person in the seat can see four black stamps, so both of his must be white)
Case 2: 1 Mixed
BWM (8) - Seat 3
MBW (8) - Seat 1 (on second turn)
BMW (8) - Seat 2 (on second turn)
(If his were White or Black one of the other would of know, since no other person spoke it must be mixed.)
Case 3: 2 Mixed
MBM (8) - Seat 1 (on second turn)
(If seat 1 were black or white, player three would have know that his was mixed, therefore seat 1 has to be mixed.)
BMM (8) - Seat 2 (on second turn)
MMB (8) - Seat 2 (on second turn)
(Seat 2 can see a person with black stamps, since the other person did not know, then the other person can't see two black or one black and one white, therefore seat 2 must be mixed.)
Case 4: All Mixed
MMM (16) - Seat 2 (on second turn)
(For seat 2 the only other possiblilty would be MBM (or MWM), if that was the case then seat 1 would have known (see above), therefore seat 2 has to be mixed.)
Seat 1 - 18
Seat 2 - 42
Seat 3 - 10
So seat 2 would be the best to choice he would have 42/70 chance that the stamp you laid out in a combination that he could work out.
Nice work! I think you have the correct answer.
This is a nice analysis to maximize probability that your answer is correct. I had understood the puzzle to require that when you answer you must be certain that your answer is correct. Then, each chair gives you a particular probability of being the first to be able to answer with certainty of your color.
If the student cannot logically deduce the colors, she will move on to the second chair, then the third chair. If that does not decide the issue, she will continue around the circle of chairs until one of you gives the correct response, with correct reasoning, based on the stamps that are visible and the other students' answers.
That was an attempt to think outside the box. It definitely doesn't fit the constraint of the OP unless we considerably relax the definition of 'logically deduce'
-
Also, I believe that if there are 3 students with mixed stamps, then the third chair would win.
Oops, upon second thoughts, I'll revise the claim I made here
It seems that bonanova was right. If there are 3 students with mixed stamps, then the second chair would win.
-
Personally I find it bizarre. I've noted that the "signal to noise ratio" (if signal means correct/true/good reasoning/answer/process, noise means bad/incorrect/false) on brainden is worse than most ad hoc forums or messages, even for the trivially easy puzzles. One of these forms is where people give answers that don't mean a thing to anyone else; the words and logic is practically gibberish in English. How does this happen? Even for most people to acknowledge a correct logical answer seems to be impossible here. If this place lacks common sense, you have to wonder what "communal" value there is given the objectives of contributing here.
In this case, the fact that we have completely different solutions means most of us are completely wrong, and yet believe we are all on the right track.
I have no problem accepting I could be wrong, but I'm the only one who has given a proof, and I have implicitly disproved all other answers. But in my experience, proofs and disproofs mean nothing to most people.
I understand your frustration of receiving no feedback after a well-reasoned and meticulous post of the solution. It is obvious from your post that you are quite smart, and I think you would fit right in this community. Personally, I generally find puzzles here to be excellent (this topic is an perfect example), and the community here includes some very fastidious, clever, and brilliant logicians. I have found myself more than once awed and humbled by the creativity and the sheer elegance of some puzzles and solutions that the Denizens come up with. I hope you will give Brainden some more time to change your opinion of its worth.
I'll have to admit that sometimes it is hard to get some feedback on this board. In this case, however, you could probably initiate some discussions about the correctness of the solution by examining other solutions (bonanova's in for instance) to see whether it is incorrect or whether you missed anything. I have examined both of your solutions, and I believe both have some errors. I may be wrong, and I often am, but I'll include those possible errors here
bonanova's solution
- Exactly two students have mixed stamps. [24] For example, bmm [wherechair 2 would win.]
Here the chair that would win case 2 can't know he is mixed [he sees another mixed student] so he passes.
That second mixed student thus knows it's not case 2. So she know she is mixed, and wins.
There is no chair preference for this case. Eight for each chair.
The possible error is highlighted in red. I find that there is indeed a chair preference here in that the third 3rd chair can not win if there are two students with mixed stamps. Consider the two states bmm and mmb, my calculations show that they both give will the win to the second chair.
Also, I believe that if there are 3 students with mixed stamps, then the third chair would win.
voider's solution (the spoiler tags are added by me)
Third chair: 24 left.
So I think there are 2 or 3 mixed pairs. Second chair would have won if one of 1st or 3rd pair was not mixed, therefore they must both be mixed.
I believe possibilities left are MMMMMM or MMXXMM. This would mewan third must have XY no matter what.
Can check this by seeing how many possibilities MMMMMM and MMXXMM form:
MMXXMM: 2x for XY or YX on third pair, 2x for XY/YX on 1st pair, 2x for identify of X, 1x for the rest must be YY. 8 ways.
MMMMMM: 8x for three pairs XY/YX. Remaining is also a pair, 2x for that. 16 ways.
Totals 24 so correct.
The possible error is highlighted in green. If the states are MMXXMM, then the 3rd chair would say 'No' on turn 3, allowing the 1st chair to rule out the state XX and YY for his own state. The 1st chair would then win on turn 4.
Having said that, I'll contribute a solution of my own. This solution will give a winning chance of 42/70 or 60%.
Choose the 1st chair. During the first turn, count the number of black stamps you see on the other two students. Then raise your hand and choose your state among the following table
0 black: BB
1 black: MM
2 black: MM
3 black: MM
4 black: WW
The chance of getting (0, 1, 2, 3, 4) blacks are (1/70, 16/70, 36/70, 16/70, 1/70), respectively. The chance of winning using the table above for (0, 1, 2, 3, 4) blacks are (1, 1/2, 2/3, 1/2, 1). So that gives us an expected value of 42/70.
-
1
- Exactly two students have mixed stamps. [24] For example, bmm [wherechair 2 would win.]
-
You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.
However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.
If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.
What is your play?
Bonus: Generalize to a case of n objects, k of which have the property M.
Here's an approximative strategy,
At every point of the game, we can summarize the current state of the game with the number of remaining objects (R), the number of unopened chosen objects (c), and the k number of objects with property M.
We define a function for the probability of winning at state (R, c, k) as
The strategy now is as follows,
1) At the beginning of N phase (before we choose an object), we calculate the chance we would win if we were to call stop at that N phase. Call this S0, which is defined as
S0 = W( R, c + 1, k )
2) We then calculate the chance we would win if we go through one more round and then stop at the next N phase. Call this S1, which is defined as
S1 = ( 1 - k/R ) * [ [ ( c + 1 )/R ] * W( R - 1, c + 1, k ) + [ 1 - (c+1)/R ]* W( R - 1, c + 2, k ) ]
3) If S1 > S0, then continue the game. Otherwise, stop the game.
Back to the example where R = 12 and k = 4. At the first turn where c = 0, which means the game state is (12, 0, 4), we get
S0 = .3333
S1 = .398
Which means that we should continue the game. If the opponent does not win the game during next turn, then there are two possible next states, which are
(11, 1, 4) - The opponent did not open your chosen door - The strategy above says that we should stop at this N phase.
(11, 0, 4) - The opponent did open your chosen door (essentially a new game with R = 11) - The strategy above says we should continue the game.
Continue until the strategy calls for a stop.
-
A while ago that asked whether
how wet you get moving a fixed distance in the rain
depends on whether you walk or run.
Let's assume there is a speed that keeps you the driest,
but you don't have the stamina for it. My question is what
speed should you run to get only twice as wet as optimal?
Assumptions you can make:
- You are [a rather squarish] 6 feet tall, 2 feet wide and 6 inches thick.
- You always move in a standing position, i.e you never lean.
- Shelter is 1000 feet away, on level ground.
- The rain is falling at a speed of 10 feet per second.
- At any given place or time there are 1000 raindrops per cubic foot.
Enjoy!
My take on this
Assuming infinite speed, then the lowest number of rain hits is 12,000,000.
We want to get twice as wet, so we want the head drop counts to be 12,000,000. The rain is falling at the rate of 10,000 drops/sec/ft2. That means we need to get across the 1000 ft field in 12,000,000/10,000 = 1,200 seconds.
That works out to be 5/6 ft/sec, which is probably should be called a strolling pace rather than a running pace =)
- You are [a rather squarish] 6 feet tall, 2 feet wide and 6 inches thick.
-
After safely landing and partially thawing in Yellowknife, the logicians returning from the ACofL Fresh Air/Fresh Ideas annual seminar began to settle their nerves as they settled down in the airport bar before continuing onto the next leg of their journey. As would be expected, not too many drinks later, one of the logicians pulled out their deck of complimentary playing cards. She cut the deck exactly in half, and proposed to the others: "Tell me the color of each of these twenty-six cards in succession. For each try, I'll tell you how many you have gotten correct. What is the fewest number of trials before I'm guaranteed to say, 'twenty-six'"?
I'd like some clarification for the part in bold. My understanding of the trial is the following
Each trial consists of the player specifying a binary sequence of length 26 (each element is either Red or Black). The host then tells the player how many elements of the sequence are correct.
The player then repeats the trials, with the goal of minimizing the number of trials required in order to arrive at the correct sequence. Is this correct?
-
Seeing as how every 8th grader with a math counts trophy knows the optimal play to his game, ol' Monty decided to shake things up.
He added two more doors, for a total of 5 instead of 3, behind which 4 held a goat, and 1 held a brand spanking new electric car (hey, gotta keep up with the times, eh?).
In the first round, the player chooses two doors instead of one. Then Monty opens up one of the other three doors and reveals a goat. Then the player may choose one of his two original doors or switch to one of the unchosen doors. Monty then releases one more goat (gotta give the first goat some company or else it'll eat Monty's brand new trousers), and the player is then given a final choice of the remaining three doors.
What is your play, if:
1) The second door Monty opens is random?
2) He is purposely playing against you, trying to keep that new car for himself?
And 3) If you weren't sure, how much would you have to suspect dear old Monty's honorable intentions to make either play?
Here's a play
The following play applies equally well to question 1) and question 2). I assume that when Monty opens a door, he will not open a door that is currently chosen by the player, and that he would not open a door that contains a car.
The algorithm for the player is as follows
1) After Monty opens the first door, randomly (with equal probability) choose 1 door among the remaining 4 doors.
2) After Monty opens the second door, we would have 3 doors left. Let's label those doors (R1, R2, C), where R1 and R2 are two of the remaining doors, and C is the currently chosen door. For the final choice, randomly pick between R1 and R2.
The chance of getting a car is 3/8, regardless of whatever strategy Monty uses.
-
You can guess a number between 1 and 1,000,000 with 20 yes/no questions.
This owes to the fact that any positive integer not greater than one million can
be represented using 20 binary digits, and you can determine them, one per
question. In general, N questions will determine any positive integer not larger
than 2N.
Better results can be had if it is known that some numbers are more likely than
others to be the target to be guessed. If nines and higher are removed from
a deck of cards [counting Aces low] 3 guesses would determine the value
[1-8] of a randomly chosen card. [but not the suit.] If the nines were added,
a 4th guess would be needed.
But suppose the numbers had different likelihoods of being chosen. This
would be the case if the deck [ignoring suits] comprised 1 Ace, 2 deuces,
3 treys ... 8 eights and 9 nines. Can you determine a guessing strategy
[a series of yes/no questions] that on average would determine the
value of a card chosen at random from such a deck, in three guesses?
Here's one that gives an expected value of 3
The questions that you need to ask are illustrated in the image below. For every node of the tree, a vertical bar ( | ) separates the available choices into 2 groups. For instance, for the first node, the question you can ask is: "Is the number equal to 7, 8, or 9?". An answer of 'Yes' would then take you to the right branch, and 'No' would take you to the left. Repeat the process until we reach a terminal node.
-
well it seems i've been pigeonholed as an overzealous OP. had adapted this puzzle from another which used the first two cards to define what the second logician guessed on half of those remaining plus the half then definable. with the fifty-two playing card format, figured one could do a little better by combining plasmid's described endplay and including the second card in what EventHorizon described as cards 3-26 guaranteeing seven of those twenty five. did not think that thirty three would necessarily be best. did expect it would take some long complicated algorithm to do better rather than such a simple and elegant solution. (though bushindo has not yet chimed in...) brilliant plasmid, kudos!
This is a superb puzzle, plaingazed. My attempts at a solution were frustrated early due to some tunnel vision, but I did gain a lot from watching the evolution of the solution. I am in particular humbled and inspired by the plasmid's creativity and ingenuity. Thank you both for this educational experience.
-
On the return journey from the Arctic Circle of Logicians Fresh Air/Fresh Ideas annual seminar, each pair of logicians received a complimentary pack of fifty two standard playing cards. These particular playing cards featured an image of the mighty de Havilland C-6 Twin Otter; the very aircraft they were currently shivering in. As such, each face down card would have one of two different orientations. The plane would either be pointing straight up against a sunless grey sky in an apparent death stall or, because of the slight tilt of its wings, would appear to be stuck in a sustained tailspin. Due to the logicians nervous desire for any distraction from the umhh, cold; they developed the following challenge: If a pair works together where only one knows the order of a shuffled deck and pre-arranges the direction of the plane on each card (without changing the order of the deck) and the other predicts the suit of each card, one at a time, from the evenly stacked face down deck, what scheme yields the maximum guaranteed correct number of suit predictions?
I'd some some clarification. In the bold part, does it mean that the second logician predicts a card, the card is revealed, and then the logician makes the next guess, and so on?
-
yes indeed, bushindo. well done.
all 8 logicians could perform your step 3) above. Then every digit of each logician will appear exactly once on each of the seven other logicians step 3). And each logician can already see six of those seven digits.
for example:
logician(1) step 3)-->d8(a8)+d7(a7)+…+d2(a2) and logician(8) can see d7(a7)+d6(a6)+…+d2(a2) so knowing the parity of logician(1)'s step 3), logician(8) can easily figure her eighth digit, etc.
That alternative solution is a lot more compact and elegant. Thanks for sharing this problem.
-
Nice job
. Thanks for the compliment, although I think it took me longer to design it than for you to solve it...in two ways...*whistling*The first solution was really just a clumsy variant of the canonical solution. After that first solution I thought this is a pretty neat puzzle, but it turns out the puzzle is even more elegant than I thought. Thanks a lot for sharing this gem.
-
I just want to come back and say that this is a really well designed puzzle. I didn't explain the rationale behind the solution before, and so here it is
The rationale of the solution is that we want to use the logicians 1-7 to convey (in binary digits) to the 8th logician his number. We need 7 binary digits to describe a number between 1 and 100, hence the 7 logicians.
The procedure that we did above will also allow each of logician 1 to 7 to determine six of his seven binary digits. We then simply used the 8th logician to convey this information back to the previous 6.
-
Each of eight logicians has a unique positive integer less than 100 stapled to their foreheads. They stand in a circle facing one another so every logician can see everyone's number, save for their own. Each logician must discern their number and raise their hand. After all logicians have raised a hand, they must then all declare their number in unison. What strategy (within the assumed spirit of these types of puzzles) might they employ such that all are correct?
EDIT
Here's an attempt.
Let the logicians be indexed by numbers going from 1 to 8. Let aj represent the positive integer of logician j. Let di( b ) represent the i-th digit from the right in the binary expansion of b. For instance, if b = 99 (which is 1100011 in binary), then d2( b) = 1, d3( b ) = 0, d4(b) = 0, and so on.
The general strategy is as follows.
1) For each logician i, where 1<= i <=7, look around and sum up the remaining hats. Let's call this sum Ti. The logician i is then supposed to raise his hand if di( Ti) = 1. Otherwise the logician should not raise his hand.
2) After logician 1 to 7 have done the previous procedure, then logician 8 should be able to figure out his number.
3) Logician 8 then calculates the sum ( d1( a1) + d2( a2) + ... + d7(a7) ). He then should raise his hand if this sum is odd. The remaining 7 logicians should be able to figure out his number as well.
-
1
-
-
I thought for sure I mentioned in the OP that they were attending the Arctic Circle of Logicians annual Fresh Air/Fresh Ideas Seminar and were all wearing mittens. Apparantly not, so your answer does indeed fit within the constraints of the OP, Time Out. But for grins, let's do assume the logicians are all wearing plain white mittens.
When you say 'numbers less than 100', do you mean 'integers less than 100 but larger than 0'? Also, can a number be repeated?
Emperor, wines, and accomplice- with a nod to meciless emperor
in New Logic/Math Puzzles
Posted
I'll just note that the intent of the puzzle is that all prisoners have to sample the wine at the same time. Since the deadline is 24 hours and the poison will take effect randomly between 12 and 24 hours after consumption, it is not possible to wait and see the effects of one wave of wine drinking before applying another.