Jump to content
BrainDen.com - Brain Teasers

bushindo

VIP
  • Content Count

    719
  • Joined

  • Last visited

  • Days Won

    5

Posts posted by bushindo

  1. it wouldn't be the first time I made a mistake on one of my own problems :dry:, but yes, i derived a slightly different answer.

    I applied witzar's formula to various different N, and I reproduced the same exact table that you gave in here

    The table below shows E(n), correct to four decimal places, for various values of n, from 1 to 50. As expected intuitively, E(n) approaches a number, as n increases.

    Expected values

    n E(n)

    1 3.5

    2 4.4722

    3 4.9583

    4 5.2446

    5 5.4309

    6 5.5603

    7 5.6541

    8 5.7244

    9 5.7782

    10 5.8202

    20 5.9736

    30 5.9958

    40 5.9993

    50 5.9999

  2. Suppose n fair 6-sided dice are rolled simultaneously. What is the expected value of the score on the highest valued die?

    Here's my answer

    Let PN( i ) be the chance of having i as the highest score on simultaneous rolls of N dice. Obviously, PN( 0 ) = 0. The general expression for PN( i ) is

    post-14842-0-38408300-1367210077_thumb.j

    Now that we have PN( i ), the expected value is simply

    E = sum PN( i )* i for i from 1 to 6.

  3. About 402 feet.

    When the dog runs along the sides of the phalanx it runs exactly 200 feet (whatever extra distance it has to cover when it runs in the same direction as the phalanx is regained we it runs in the opposite direction.

    When the dog runs along the front and back of the phalanx, it runs diagonally. Both front and back are exactly the same, so let's consider one of them and then double the result. The distance is the hypotenuse of the triangle with sides of 100ft and X, where X is the distance travelled by the phalanx in the time it took the dog to run from one corner to another. It's about a quarter of the entire journey, so the phalanx moves about 12.5 feet in that time and the dog runs about 101 feet.

    So the total distance is 200 + 101*2 = 402.

    It's just an estimate. Need to think some more to come up with the exact answer.

    I think there's an error here (see part highlighted in red above)

    To make the notation consistent with bonova's, let

    c = dog speed

    v = men marching speed

    x = side of square = 100 feet

    y2 = side where dog is running in the same direction as the men

    y4 = side where dog is running in the opposite direction

    If the total distance is 401.569 feet, then the speed of the dog is approximately 8.031 times the speed of the phalanx, or c/v = 8.031. For simplicity, let's assume v = 1, and c = 8.031.

    y2 = [ x/( c - v ) ] * c = 114.3495

    y4 = [ x/( c + v )] * c = 88.85034

    y2 + y4 = 203.1998

    So the total distance that the dog runs along the two sides of the phalanx (y2 + y4) is not precisely 200.

  4. k-man and TSLF agree on an answer that differs slightly from mine.

    So as it stands I am outvoted.

    But I invite a critique of my solution.

    • Size of square = x
    • cadet speed = v
    • distance cadets move = y
    • dog speed = c
    • distance dog runs = d
    • ratios: v/c = y/d = sin(a)

    The two ratios above follow from the fact that v and c are constant, so the distances traveled by cadets and dog must have the ratio as their speeds. Using an angle a avoids dealing with all those messy square roots of sums and differences of squares.

    Without changing the answer, we can start the dog at the back right corner and have it circle the cadets in a CW direction. There are four legs to the dog's path:

    • sideways (mostly)
    • forward
    • sideways (mostly)
    • backward

    Consider first, only the forward and backward components of the dog's path.

    Call the forward direction the y direction.

    y1 = y3 = x tan(a)

    y2 = x [c/(c-v)] = x [1/(1-sin(a))]

    y4 = x [c/(c+v)] = x [1/(1+sin(a))]

    y1 + y3 = 2x tan(a)

    y2 - y4 = x [2sin(a)/cos2(a)] = 2x tan(a)/cos(a) (y4 is reverse direction)

    y/x = 2 tan(a) [1 + 1/cos(a)]

    In our case, this ratio is 50/100 = 0.5

    Numerical solution gives:

    a = 7.09789o

    Note that this puzzle scales in terms of distance the cadets move.

    There is only one equation to solve: a in terms of y/x.

    Here are solutions for three values of y/x

    y/x .a . . . c/v = d/y = 1/sin(a)

    ---+--------+-------------------+

    0.5 7.09789 8.09291 <== this puzzle

    1.0 13.83756 4.18112

    2.0 25.39026 2.33218

    We can sum similar expressions for d1 d2 d3 and d4:

    d1 = d3 = x/cos(a)

    d2 = x [c/(c-v)] = x [1/(1-sin(a))]

    d4 = x [c/(c+v)] = x [1/(1+sin(a))]

    d1 + d3 = 2x/cos(a)

    d2 + d4 = x [2 / cos2(a)] = 2x/cos(a)[1/cos(a)]

    d/x = 2/cos(a) [1 + 1/cos(a)]

    Which agrees with our ratio: d = y/sin(a)

    Either way, once we know that a = 7.09789, we obtain

    d = 50/sin(7.09789) = 50*8.09291 = 404.645

    Interestingly, k-man and TSLF obtain values close to

    d = 50/tan(7.09789) = 50*8.03089 = 401.544.

    bonanova's work checks out to me. I used k-man and TSLF's answers and worked backward to get a distance of about 50.4 feet moved, so I'm casting a vote for bonanova.

  5. Therefore

    We can now show that, in a triangle with internal angle at least 120°, the ratio of the length of the longest side to the shortest side is at least root3n.gif : 1.

    Without loss of generality, in triangle ABC, let angleC > 120° > angle B > angle A. Let the side opposite angle A have length a, and so on.

    p140s5.gif

    Then, by the cosine rule c2 = a2 + b2 − 2ab cos C > a2 + b2 + ab. (Since cos C < −½.)

    Assuming a < b (by the sine rule) we obtain c2> 3a2.

    Hence c/a > root3n.gif.

    Finally, since M > c and m < a, we conclude that M/m > root3n.gif, as was to be proved.

    I believe there is a subtle error here

    See the part highlighted in red. Let's work backward and see what kind of condition we need to guarantee strict equality.

    From c2 = a2 + b2 − 2ab cos C, we see that if C = 120 and a = b, then c/a = sqrt(3), so far so good.

    Now, let's examine the following critical part

    "since M > c and m < a, we conclude that M/m > root3n.gif"

    If c/a = sqrt(3), then to guarantee M/m = sqrt(3), we need to show that M = c AND m = a. That part wasn't proved anywhere. In fact, I believe that if we go back and look at the problem, then we would see that if we have a sub-triangle with side-ratio c/a = sqrt(3), then either M > c or m < a.

  6. what do you mean by an "even chance" of getting snow or rain?

    never mind, i explained the wrong part. If it rained today then there is a 50% chance of rain again and 50% it won't

    If I'm parsing the probability correctly

    The problem is equivalent to the following. Let A be the matrix

             0    0.2500    0.2500
        0.5000    0.5000    0.2500
        0.5000    0.2500    0.5000
    

    And let b be the vector [1/3 1/3 1/3]', where the elements from left to right correspond to chance of nice day, snow, and rain, respectively. What is the quantity A15 * b?

    Turns out that A15 * b is approximately [1/5 2/5 2/5]. So chance of nice day is 1/5, chance of snow is 2/5, and chance of rain is 2/5.

  7. Calling Dr. Bayes ... Where is Bushindo when you need him?

    being heads biases the probability above 1/2 that she is using the double-headed coin. And more so in the second case of two heads. So the asked probability is greater, in both cases, and more in the second case, than the unbiased probability of 3/4.

    I won't, on principle, plug numbers into B's formula, so I ask myself this question: if she flips it once and says it's heads, what is the likelihood she flipped the double-headed coin? Seems it would be 2/3. Similarly if it was heads twice, it would be 5/6.

    So, if I'm thinking right,

    the first answer would be 1/3 x 1/2 + 2/3 x 1 = 5/6

    and the second answer would be 1/6 x 1/2 + 5/6 x 1 = 11/12.

    On the contrary, I will, on principle, plug the number in Bayes' formula =)

    Applying Bayes' formula, if the first N flips are heads, then the chance of the N+1 flip being head is

    [ (1/2)N+1 + 1]/[ (1/2)N + 1 ]

    So the answer to the first question is 5/6, and the answer to the second is 9/10.

  8. I made a drawing that shows all possibilities for a blue eyed couple (M=Mother and F=Father) to have a daughter (J=Judy) and a grandChild ( C ) of this daughter with a father of type Bg. Each rectangle represents specific genotype of Father, Mother, Judy and Child. Genotype of the Father can be read on horizontal axis, genotype of Mother is written on vertical axis, genotype of Judy and Child can be read inside of the rectangle. For example rectangle labelled "J:Bg;C:BB" says that Judy is Bg and Child is BB. Area of each rectangle divided by area of the whole square equals probability of the event. Black-hatched rectangles indicate cases that should be excluded due to green eyes of Judy or Child. Blue rectangles indicate cases when Father is of type BB. To answer the question #1 it is sufficient to divide (blue area) by (the area of the whole square minus black-hatched area).

    Here is a link to the image:

    http://imageshack.us/photo/my-images/545/blueeyesl.jpg/

    I'm also trying to attach it, since It looks like I'm not allowed to upload images (why?).

    Comments

    The logic is impeccable, and the image above looks right with the relative areas. However, I think there might be some arithmetic mistakes in the calculations, since 65/72 is about 90%, and the (blue areas) divided by (the area of the whole square minus black-hatched area) is nearer to 70% than it is to 90%.

  9. I suppose, blue eyed child also must play part in figuring out question 1. I only took it into account for figuring out question two, so my previous answer is wrong.

    Since blue eyed child reduces Judy's probability of Bg by 1/4, the odds of Judy's parents are as following:

    (BB-BB):(BB-Bg):(Bg-Bg) = 32:28:5 (From the table in post #4).

    Where all BB-BB families and half of BB-Bg have BB type father.

    Therefore:

    1) 46/65 Judy's father is BB.

    2) 3/52 Judy and Jack's second child has green eyes.

    Bingo.

    Somehow, to me this problem seems similar to Bonanova's “Give monkey enough rope.” (Some serious untangling to perform one must.)

    Hey, I resent that =). I spend some time trying to make the wording clear and lucid. There is no way this puzzle can match the sheer genius of grammatical obfuscation in 'Give monkey enough rope'.

    I did not mean to imply any grammatical obfuscation in this puzzle. I meant probability obfuscation with backward refrences, like first child.

    In that case, thank you, I aim to please. Nothing but the best probability obfuscation for my fellow Brainden citizens.

  10. The probability distribution for standard dice can be generated by powers of d(x)=(x+x^2+x^3+x^4+x^5+x^6)^n.

    The coeff of x^k gives the frequency out of 6^n of rolling k.

    Two dice: (x+x^2+x^3+x^4+x^5+x^6)^2 = x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9+3x^10+2x^11+x^12

    An alternate factorization of the polynomial is (x+x^3+x^4+x^5+x^6+x^8)*(x+2x^2+2x^3+x^4)

    The first factor represents a die w faces (1, 3, 4, 5, 6, 8). The other factor, faces (1, 2, 2, 3, 3, 4).

    well done witzar

    Fascinating analysis. Thanks for posting this wonderful problem.

  11. I took a little time to verify my guess.

    Let's construct a proportions table of different union types and their offspring.

    Couple = proportion => Offspring(proportion)

    1) BB-BB = 1/4 ==> BB(1/4)

    2) BB-Bg = 1/4 ==> BB(1/8) + Bg(1/8)

    3) BB-gg = 1/4 ==> Bg(1/4)

    4) Bg-gg = 1/8 ==> Bg(1/16) + gg(1/16)

    5) Bg-Bg = 1/16 => BB(1/64) + Bg(1/32) + gg(1/64)

    6) gg-gg = 1/16 => gg(1/16)

    Judy's parents could be couples (1), (2), or (5), where both parents are blue eyed. The odds that blue-eyed Judy is from one of those families are (1):(2):(5) = 16:16:3. Where all families (1) have BB father, half of the families (2) have BB father, and none of families (3) have BB father. Therefore, the answer to question 1 is (16+8)/35 = 24/35.

    Since one of Jack's parents is green eyed, Jack is Bg type.

    From the above table, Judy's genotype odds of BB:Bg = 5:2.

    Proportions table for Jack and Judy is as following:

    Jack-Judy = probability => Offspring(proportion)

    A) Bg-BB = 5/7 => BB(5/14) + Bg(5/14)

    B) Bg-Bg = 2/7 => BB(1/14) + Bg(2/14) + gg(1/14)

    Thus the odds for Jack-Judy blue eyed kid's family type (A):(B) = 10:3. Meaning, given one blue eyed child, the chance of Jack-Judy union being of type Bg-Bg is 3/13 -- the only type of Jack-Judy family that could produce a green eyed child at the probability of 1/4. Hence, the second child has the green eyes at the probability of (3/13)*(1/4) = 3/52.

    Of course, the above relies on assumption of Judy's faithfulness.

    I did not mean to imply any grammatical obfuscation in this puzzle. I meant probability obfuscation with backward refrences, like first child.

    My analysis uses the first blue eyed child as prior information (highlighted in red here). That's how I got probability 3/13 rather than 2/7 for Judy's genotype Bg.

    I was specifically mentioning that the work for problem 1 (see part highlighted in blue) does not use Child 1's color as prior information. As bonanova said, Reverend Bayes has already entered the room. The answer for part 2 is correct, and does use all the available information.

    1) 65/72

    2) 3/52

    I get the same answer for part 2, but different answer for part 1. I could be wrong, and I frequently am. Could you describe your reasoning for part 1 so that I could follow the logic more closely?

  12. I'm wondering how half the population came to be BB, or how that distribution is sustainable.

    That is, given two parents with those genotype probabilities, does even the first generation of children sustain that distribution?

    Regardless, what do we know immediately?

    • Because of Jack's green Mom and his own blue eyes,

      then regardless of Jack's Dad's type, Jack is type Bg.

    • Corollary: we know only about Jack's Dad's type that it is not gg.

      But that has no bearing on the questions.

    • The type of Child1 is a red herring, I think.

      Because Jack is not BB, and Judy is not necessarily BB, then C1 could have been green: s/he just happens to be Blue.

      Also, each child has the same type probability. Or is has Mr. Bayes already entered the room?

    Question 1: What do we know about Judy's Dad? Indirectly ( because Judy is not green-eyed) we know it is not the case that both he and Judy's Mom are gg. I suspect that makes JD's BB type greater than 50%. By how much? Well, in the normal course of events, Judy could have gg with 25% probability, and that probability has been removed. So she's BB (2/3) or Bg (1/3). What parental genotypes produce that distribution? Seems that eliminating gg-gg makes it a lot more probable than 1/3 that she is Bg. So I will leave this unanswered until I can think more about it.

    Question 2: Because Jack is Bg, also because Child1 is blue, his kids' shots at being green-eyed are no greater than 50%. Can we say Judy's BB probability is now 2/3 (gg having been eliminated)? If so, then children's gg probability are all (1/3)(1/2) = 1/6. I'll go with that answer..

    I'm afraid the case of Child 1 is not a red herring. Reverend Bayes has already entered the room since we gained some additional information by knowing the phenotype of Child 1. For instance, if child 1 is green-eyed, intuition says that would vastly affects the answers to 1 and 2; therefore the fact that the child is blue-eyed should also give some information.

    I took a little time to verify my guess.

    Let's construct a proportions table of different union types and their offspring.

    Couple = proportion => Offspring(proportion)

    1) BB-BB = 1/4 ==> BB(1/4)

    2) BB-Bg = 1/4 ==> BB(1/8) + Bg(1/8)

    3) BB-gg = 1/4 ==> Bg(1/4)

    4) Bg-gg = 1/8 ==> Bg(1/16) + gg(1/16)

    5) Bg-Bg = 1/16 => BB(1/64) + Bg(1/32) + gg(1/64)

    6) gg-gg = 1/16 => gg(1/16)

    Judy's parents could be couples (1), (2), or (5), where both parents are blue eyed. The odds that blue-eyed Judy is from one of those families are (1):(2):(5) = 16:16:3. Where all families (1) have BB father, half of the families (2) have BB father, and none of families (3) have BB father. Therefore, the answer to question 1 is (16+8)/35 = 24/35.

    Since one of Jack's parents is green eyed, Jack is Bg type.

    From the above table, Judy's genotype odds of BB:Bg = 5:2.

    Proportions table for Jack and Judy is as following:

    Jack-Judy = probability => Offspring(proportion)

    A) Bg-BB = 5/7 => BB(5/14) + Bg(5/14)

    B) Bg-Bg = 2/7 => BB(1/14) + Bg(2/14) + gg(1/14)

    Thus the odds for Jack-Judy blue eyed kid's family type (A):(B) = 10:3. Meaning, given one blue eyed child, the chance of Jack-Judy union being of type Bg-Bg is 3/13 -- the only type of Jack-Judy family that could produce a green eyed child at the probability of 1/4. Hence, the second child has the green eyes at the probability of (3/13)*(1/4) = 3/52.

    Of course, the above relies on assumption of Judy's faithfulness.

    The analysis above does not use the phenotype of Child 1 (blue-eyed) as part of the prior information. As per the discussion in bonanova's post, by knowing the phenotype of the child, we gained some additional knowledge about the probabilities of interest. That knowledge should be incorporated in the computation of 1) and 2).

    Somehow, to me this problem seems similar to Bonanova's “Give monkey enough rope.” (Some serious untangling to perform one must.)

    Hey, I resent that =). I spend some time trying to make the wording clear and lucid. There is no way this puzzle can match the sheer genius of grammatical obfuscation in 'Give monkey enough rope'.

  13. Let's say that in a certain country, there are two types of people- blue-eyed and green-eyed.
    Let's assume that eye color are governed by a single gene, which can be in the dominant form (B) or recessive form (g). This means that people in this country have the genotype BB (blue-eyed), Bg (blue-eyed), or gg (green-eyed). The relative frequency of these genotypes in the population is BB (50%), Bg (25%), and gg( 25%).
    Judy (blue-eyed) is married to Jack (blue-eyed). Judy's parents are both blue-eyed; one of Jack's parents is blue-eyed while the other is green-eyed. Judy and Jack's first child has blue eyes.
    1) Given the above, what is the probability that Judy's father has the dominant genotype BB?
    2) What is the chance that Judy and Jack's second child is green-eyed?
  14. ?

    Maybe OP meant non-negative?

    I think I have a proof there is no other solution. Construct the table.

    Missed the point about positive integers. I agree with bonanova, in that case

    The sum distribution is (2,3,4,5,6,7,8,9,10,11,12)

    Since the smallest sum is 2, and the die number are positive integers, then 1 face from each of the 2 die must be a '1'.

    The next sum is 3 with probability 2/36, so you can either have

    1) two '2' on 1 die

    2) one '2' on each of the 2 dice

    If you allow 1), then it quickly becomes clear that it is not possible to get a sum of 4 with probability 3/36. Therefore 1 face from each of the 2 die must have a '2' on it.

    Following the same logic further, we see that the only solution to the constraints in the OP is the case of the standard dice. In other words, there are no other dice arrangement of positive integers such that their sum probability distribution is precisely the same as that of two standard dice.

  15. Assume you have a standard dice with labels 1, 2, 3, 4, 5, 6 on each respectively. Pretend you are playing a simple game where you roll the two dice and add their values together. Is it possible to relabel the dice using positive integers in such a way that if you play the same dice game you would have an equal probability of rolling the same sums?

    Note: What I mean by relabeling is not simply rotating all of the numbers on the dice where by each dice still contains the same six numbers but rather actually making new dice that has a different set of six integers than the original. (e.g. one dice could be 1, 2, 3, 4, 5, 9 and the other could be 1,1,1,1,1,1 ... would this pair produce the same sum probabilities as the original?--in short, no ^_^)

    Here's an answer

    Let i be any integer.

    Label one die with (i + 1, i+2, …, i + 6 ). Label the other die with (-i + 1, -i + 2, …, -i + 6 ). Rolling these two dice together will result in a sum probability distribution that is identical to that of two standard dice.

    Note that the case of two standard die is equivalent to setting i = 0.

  16. I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips m(N) for every N. See below for reason + proof of fairness

    Let's assume there's a method with a maximum flips m(N) for N participants. There are roughly 2m(N) possible outcomes. Since that is a power of 2, it doesn't divide nicely when N includes non-2 factors. There are bound to be events when the method can not select someone, and then we are back to square one.

    As for the fairness issue, the point of the method is to randomly sample (via binary flip) 1 single point Binfinity from 0 to 1. Given infinite random flips, we are guaranteed that Binfinity falls uniformly and randomly within that interval. Since the method picks a persons as soon as Binfinity, or its interval [bN, BN + 2-n ], falls entirely within a subregion, we are then covered with respect to fairness.

    Agree. A fair method cannot guaranty any maximum number of tosses.

    I'd like to enter the following solution and claim the minimum number of throws.

    Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

    I see your 1 and I will raise you a 0 =)

    Arrange the participants into a circle and tell them to simultaneously throw out their hand with the fists made into either a rock, paper, or scissor. That is, let them play N-person paper-rock-scissor. Keep the participants with the least frequent hand-formation. For instance, if there are 12 people, and 4 has rock, 5 has scissor, and 3 has paper, then we keep the party of 3 that made the paper.

    Let the subparty play the modified paper-rock-scissor game again until 1 person remains. If at any point there is a 3-way tie of hand-formation, let them play again. Also, if there are 2 people left at some point, then let them play normal paper-rock-scissor instead of the modified version.

    Oh, the coin? Tip it to the waiter.

    Not acceptable. The winner must be decided by coin toss.

    My interpretation of the OP is that the coin flip is optional rather than mandatory. The OP says "Pick a person out of n with a sequence of coin toss". I submit that it is possible to construct a sequence of length 0.

  17. I'd like to enter the following solution and claim the minimum number of throws.

    Divide the entire table cloth into n rectangles of equal area with a permanent marker. Each participant must be assigned his rectangle. Then ask the waiter to throw the coin onto the table cloth from afar.

    I see your 1 and I will raise you a 0 =)

    Arrange the participants into a circle and tell them to simultaneously throw out their hand with the fists made into either a rock, paper, or scissor. That is, let them play N-person paper-rock-scissor. Keep the participants with the least frequent hand-formation. For instance, if there are 12 people, and 4 has rock, 5 has scissor, and 3 has paper, then we keep the party of 3 that made the paper.

    Let the subparty play the modified paper-rock-scissor game again until 1 person remains. If at any point there is a 3-way tie of hand-formation, let them play again. Also, if there are 2 people left at some point, then let them play normal paper-rock-scissor instead of the modified version.

    Oh, the coin? Tip it to the waiter.

  18. You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

    You have only a fair coin, and the method has to treat everyone equally.

    It must be absolutely fair and unbiased.

    There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

    Pick one person out of n, fairly, with a sequence of fair coin tosses.

    I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

    If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

    Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be BN. The range of values for the binary number Binfinity after the first N flip is [bN,BN + 2-N].

    So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

    The idea is as soon as the possible values [bN,BN + 2-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

    Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

    Awesome. Same problem though no ceiling. And it seems fair, but not in an obvious way. A proof of fairness would be nice.

    I don't think this problem can be decided with a fixed ceiling method. That is, I don't think there exist a method that guarantees a maximum number of fixed maximum flips m(N) for every N. See below for reason + proof of fairness

    Let's assume there's a method with a maximum flips m(N) for N participants. There are roughly 2m(N) possible outcomes. Since that is a power of 2, it doesn't divide nicely when N includes non-2 factors. There are bound to be events when the method can not select someone, and then we are back to square one.

    As for the fairness issue, the point of the method is to randomly sample (via binary flip) 1 single point Binfinity from 0 to 1. Given infinite random flips, we are guaranteed that Binfinity falls uniformly and randomly within that interval. Since the method picks a persons as soon as Binfinity, or its interval [bN, BN + 2-n ], falls entirely within a subregion, we are then covered with respect to fairness.

  19. You're out with friends at Chuck's Steak House and decide to flip a coin to select one person get a free dinner. The bill will be split n-1 ways instead of n ways. Since I was not invited, I don't know how many are in the group. (Maybe next time you'll include me; I love Chuck's place.) So anyway, your selection method has to work for an arbitrary numbers of participants.

    You have only a fair coin, and the method has to treat everyone equally.

    It must be absolutely fair and unbiased.

    There might be many ways; bonus points await methods with originality, flair, and minimization of flips.

    Pick one person out of n, fairly, with a sequence of fair coin tosses.

    I'm trying to go for the minimum expected number of flips here. This is my best attempt so far

    If N is a power of 2, the solution is trivial. Let's assume N is not a power of 2. Divide the interval from 0 to 1 into N sub-intervals. Each person will be assigned a sub-interval. So, if there are 3 participant, the first one would be assigned [0, 1/3), the second [1/3, 2/3), and the third [2/3, 1].

    Flip the coin and treat the resulting string of outcomes as a fractional binary number. For instance, let head = 1 and tail = 0. If we flip head two times in a row, that is the equivalent of .11 in binary or (1/2 + 1/4 = .75 in decimal). Let the fractional binary number we construct after N flip be BN. The range of values for the binary number Binfinity after the first N flip is [bN,BN + 2-N].

    So, let's say after two flips the binary number is .11 in binary or .75 in decimal. The range of possible binary number, assuming an infinite number of continuing flips, in decimal form is [.75, 1].

    The idea is as soon as the possible values [bN,BN + 2-(N) ] is entirely contained within 1 person's subinterval, that person is selected.

    Let's calculate the expected number of flips required. For N participants where N is not a power of 2, we would require ceiling( log2( N ) ) flips to narrow the field down to two people. From there it takes an expected number of 2 further flips to further select one of those two. That gives us an upper bound of ceiling( log2( N ) ) + 2 for the expected number of flips.

  20. Flip the coin 1+floor(log(base2)(n)) times, record a 1 for each heads and a 0 for each tails to get a binary number, also assign each person a number between 1 and n. The person you choose is the one with the number which is equal to the binary number once it has been converted into decimal.

    Question

    Let's say we have 9 participants. The method above says flip a coin 4 times and then convert the 4 flips into a number from 1-16.

    Obviously, chances are about 7/16 that no one gets selected with this methodology. What then? Do we repeat the procedure and flip the coin 4 more times and see whose number gets matched?

  21. Since question 1 was not a part of that problem posted in 2008, let me provide a solution to that one real quick.

    Let's say the probability of 4 darts forming a convex quadrilateral is

    P.

    Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

    Proof:

    Any convex quadrilateral forms a triangle with the 4th point inside, and from any triangle with a point inside 3 different quadrilaterals may be formed.

    Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

    Now, that question 1 is solved, I am inclined to yield the opportunity of solving question 2 to others.

    I think the proof is fine as it is, but I believe there are a few typos. See below

    Quoting Prime:

    ****************

    Let's say the probability of 4 darts not forming a convex quadrilateral is P (i.e., P = probability the four darts form a triangle enclosing 1 point).

    Then probability of the 4th dart hitting inside the triangle formed by the first three is P/4.

    Proof:

    Any convex quadrilateral forms a triangle with the 4th point inside outside, and from any triangle with a point inside outside 3 different quadrilaterals may be formed.

    Any 4 points may be ordered in 4! = 24 ways. Whereas any 3 points may be ordered in 3! = 6 ways. 3!/4! = 1/4.

    Question for bonanova: about question 1- the probability that the 4th point falls within the triangle,

    So the problem is equivalent to finding the area of a triangle given 3 points, and then integrating that area over the distribution of those 3 points.

    We need 2 coordinates to describe a single point in the circle, so we would need 6 coordinates (x1, y1, x2, y2, x3, y3) to describe any distribution of 3 points.

    There is a straight forward formula for computing the area of a triangle given 3 points. As such, we can construct a sextuple integral for compute the solution. (Solving the integral analytically might be a problem, though the integral might be evaluated by numerical means)

    I assume that such a sextuple integral is not acceptable as a solution =)?

  22. Now Bushindo is with Bonanova insisting that Win(shooting air)=Win(shooting Alex) means uncertainty. What's wrong with my tiebreaks?

    A true 3-way duel indeed. But all got the same answer to the problem.

    I can see where my guidlines to Cole in post#4 could be misinterpreted. My intention was to help Cole avoiding computations, where possible. For if he sits down with a calculator in the middle of the duel, the other two guys may get angry and just shoot him out of turn.

    I think I misinterpreted your position. I don't think bononova and I share the same interpretation of 'uncertain', though. Let me see if we have the following positions correct

    bonanova: 'Uncertain' means being unable to tell whether Wshoot_air(b,c) < Wshoot_at_Alex(b,c) or Wshoot_air(b,c) > Wshoot_at_Alex(b,c) without applying those functions. So, Cole is uncertain between .31 < b < .39.

    bushindo: 'Uncertain' means Wshoot_air(b,c) = Wshoot_at_Alex(b,c).

    Prime: 'Uncertain' means being unable to make a decision based on all available information. There is no situation when Cole is uncertain about what to do next. Cole should always choose the strategy that gives higher value between Wshoot_air(b,c) and Wshoot_at_Alex(b,c).

    I agree that under the standard dictionary definition of 'uncertain', Prime's interpretation would be most correct. I thought that bonanova had some different specialized meaning in mind, and apparently he does. It just isn't what I thought it was =).

    The way I see it, Bonanova has made his problem statement/position 100% clear:

    Uncertainty is when Cole's winning chance by shooting in the air = his winning chance by shooting at Alex.

    The question Bonanova wants us to solve is: For what values of b (accuracy of Bobby) such situation is possible?

    And solved it we have:

    And we all (including Bonanova) have found same equation yielding the same answer:

    When b is between 31.8% and 38.2% that "uncertainty" may occur.

    For the values of b outside those boundaries, a situation where Wshoot_air(b,c) = Wshoot_at_Alex(b,c) is impossible.

    Bushindo's view of uncertainty is the same as Bonanova's: Wshoot_air(b,c) = Wshoot_at_Alex(b,c).

    However, there seems to be some uncertainty as to what exactly Bonanova wants us to find.

    Prime picks on the usage of the word uncertain. Does not believe there is any uncertainty here at all. (When chances are equal, Cole must shoot Alex, because he hates him more than he hates Bobby.) Also, Prime promotes (unsuccessfully) an alternative strategy whereby Cole shoots himself in the foot with his very first shot.

    You're right. My view of uncertainty is the same as bonanoba's. It's still too early for me to be senile, *sigh*.

    Good analysis, though. Your analysis definitely deserves the distinction of Best Answer.

  23. Now Bushindo is with Bonanova insisting that Win(shooting air)=Win(shooting Alex) means uncertainty. What's wrong with my tiebreaks?

    A true 3-way duel indeed. But all got the same answer to the problem.

    I can see where my guidlines to Cole in post#4 could be misinterpreted. My intention was to help Cole avoiding computations, where possible. For if he sits down with a calculator in the middle of the duel, the other two guys may get angry and just shoot him out of turn.

    I think I misinterpreted your position. I don't think bononova and I share the same interpretation of 'uncertain', though. Let me see if we have the following positions correct

    bonanova: 'Uncertain' means being unable to tell whether Wshoot_air(b,c) < Wshoot_at_Alex(b,c) or Wshoot_air(b,c) > Wshoot_at_Alex(b,c) without applying those functions. So, Cole is uncertain between .31 < b < .39.

    bushindo: 'Uncertain' means Wshoot_air(b,c) = Wshoot_at_Alex(b,c).

    Prime: 'Uncertain' means being unable to make a decision based on all available information. There is no situation when Cole is uncertain about what to do next. Cole should always choose the strategy that gives higher value between Wshoot_air(b,c) and Wshoot_at_Alex(b,c).

    I agree that under the standard dictionary definition of 'uncertain', Prime's interpretation would be most correct. I thought that bonanova had some different specialized meaning in mind, and apparently he does. It just isn't what I thought it was =).

×
×
  • Create New...