Jump to content
BrainDen.com - Brain Teasers

superprismatic

Moderator
  • Content Count

    1267
  • Joined

  • Last visited

  • Days Won

    3

Posts posted by superprismatic


  1. If P(x)= a0 xn +a1 xn-1+...+an-2 x2+an-1 x + an

    then Q(x)= an xn + an-1 xn-1 + ... + a2 x2 + a1 x1 + a0 with reversed coefficients

    Let x=1/y

    then P(x)= a0 1/yn +a1 1/yn-1+...+an-2 1/y2+an-1 1/y + an

    P(x)= 1/yn ( a0 +a1 y1+...+an-2 yn-2+an-1 yn-1 + an yn)

    P(x)= 1/yn Q(y)

    If x1 is a root for P(x), then P(x1) = 0

    but y1=1/x1 will also give Q(y1) = 0

    For every root of P there is a reciprocal of Q

    One possibility you hadn't addressed: What about roots which are 0, and possibly with multiplicity?


  2. Does "combined score" mean the total number of chips Moe and Joe have together after 10 rounds?

    If so, then the answer is 520, but where is the puzzle?

    I'm sure that's not the right answer, so I'm not hiding it in the spoiler.

    520 is not the answer because neither Joe nor Moe gets a chip if they turn over cards of the same rank (which, you'll have to admit, will sometimes happen).


  3. Let n be your position in the line, there are n-1 people ahead of you. Let A be the event that the people ahead of you all have different birthdays, and let B be the event that you have the same birthday as someone ahead of you. You will win iff both A and B happens. So P(win) = P(A and B) = P(A)*P(B|A). We know that P(A) = 365*364*...*(365-n+2)/365

    n-1, and it's easily seen that P(B|A) = (n-1)/365. So P(win) = 365*364*...*(365-n+2)*(n-1)/365n. Consider the function f(n) as being your probability of winning in position n. We seek the value for n which maximizes f(n).

    If we compare f(n+1) to f(n), most factors will fortunately cancel out.

    f(n+1)/f(n) = 365*364*...*(365-n+2)*(365-n+1)*n/365n+1/(365*364*...*(365-n+2)*(n-1)/365n) = (365-n+1)*n/(365(n-1)) = (365n-n2+n)/(365n-365)

    As long as this is greater than 1, the function f(n) keeps growing. Solving:

    1 < (365n-n2+n)/(365n-365)

    365n-365 < 365n-n2+n

    -365 < -n2+n

    365 > n2-n

    Since n can only be positive integers, the inequality holds exactly for 0 < n < 20. So f(n+1) > f(n) as long as n < 20, and f(n+1) < f(n) as long as n > 19. Hence n = 20 yields the maximum value for f(n), as hinted by superprismatic's simulation. Entering f(20) into the calculator on my computer yields ~0.0323198575490432954774, which is not far from what the simulation yielded.

    Nice analysis! I wish I had thought of that.


  4. Here are two such octagons for n=8. I believe there are no others


    up to symmetries.
    ....18..20....
    ......10......
    21..19..22..15
    ..11......14..
    17..24..23..13
    ......09......
    ....16..12....
    ....20..21....
    ......09......
    17..19..23..18
    ..12......10..
    16..24..22..15
    ......13......
    ....14..11....

    • Upvote 1

  5. Here's a solution for the maximum


    common sum (41) using the integers
    from 1 to 16:
    ....13..07....
    ......09......
    04..11..14..12
    ..06......03..
    08..16..15..02
    ......10......
    ....01..05....

    I've found 8 distinct solutions (up
    to symmetries) for a common sum of 41.

    Proof that 41 is maximal:
    Let S be the common sum and let C
    be the sum of the four closest
    numbers to the center of the octagon.
    Then, since the numbers making C
    are used in three of the sums, whereas
    all the other numbers are in only two
    of the sums,
    8*S - C = 32*n + 16*17
    (n comes from the consecutive integers
    being n+1, n+2, n+3, ..., n+16).
    In this case, n=0. Now, we rearrange
    to solve for S to get
    S = 4*n + 34 + (C/8)
    which means that C must be divisible
    by 8. The largest C possible by
    adding four different numbers in the
    set {1,2,3,...,16} is 56. This makes
    S in our case to be 41.


  6. I wasn't sure what floors+doors+keys means. I took the liberty of interpreting


    this as [number of visited floors]+[number of overall key-in-doorlock checks]. If this
    correct, I realized that the basement floor need not always be checked because
    we may have only one key not spoken for by the time we get to consider it. In
    this case, we can be sure that that key is the one for the room in the basement.
    Similarly, we need only check 9 of the 10 keys in any door. If they don't
    unlock it, we can be sure that the key we haven't checked will unlock it.

    I used the above reasoning to make two simulations of 1,000,000 trials each.
    One simulation, which tried keys in increasing order of how many doors they opened
    so far, with ties broken randomly. In this trial, the average score was 385.9.
    The second simulation was similar, but tried keys in decreasing order of how many
    doors they opened so far. This second one produced an average score of 423.4.
    So, my vote goes to my first strategy as the optimal one.

  7. I have 2 questions:

    1. Are we to find keys to open all 61 doors? A door need not be locked for us to test a key to it. Or are we

    to find keys for only the 60 locked doors?

    2. If the basement is technically the eleventh floor, then there must be 10 floors above it with 10 rooms per floor.

    That's a total of 100 rooms plus the office in the basement. Is this correct? If so, shouldn't each above-ground

    floor have 6 rooms? Otherwise, there would have to be 40 rooms without doors.


  8. Most mathematically minded people know that if P(x) is a polynomial in x


    then r is a root of P if and only if x-r is a factor of P(x). More generally,
    replacing every instance of xn in P(x) by r results in creating the trivial
    polynomial 0 if and only if xn-r is a factor of P(x).



    Since we wish to annihilate that pesky constant term 1 when we replace things in P(x), it's natural to look to roots of -1 thusly:

    Let P(x)=x7+x6+x5+x4+x3+x2+x+1. If x were equal to -1, then P(x) becomes
    -1+1-1+1-1+1-1+1 which is identically 0. This means that x-(-1), i.e. x+1, is a factor.

    Now, P(x)=x·(x2)3+(x2)3+x·(x2)2+(x2)2+x·(x2)+x2+x+1. So if x2 were to equal -1, then P(x)
    would simplify to -x-1+x+1-x-1+x+1 which is 0. So x2-(-1), i.e. x2+1, is another factor.

    For x3=-1, we get P(x)=x·(x3)2+(x3)2+x2·x3+x·x3+x3+x2+x+1 which simplifies to
    -x+1-x2-x-1+x2+x+1 or 1-x which is not identically 0, so x3+1 is not a factor.

    For x4=-1, we get P(x)=-x3-x2-x-1+x3+x2+x+1 which is identically 0, so x4+1 is another factor.

    Since the product of these three factors is of degree 7, we are done.

    So, x7+x6+x5+x4+x3+x2+x+1 = (x+1)·(x2+1)·(x4+1)

  9. If there is only one unfaithful wife, the husband would know


    on the first night because there is a least one but he knows that
    none of the other men's wives are unfaithful.
    If there are two, then each man reasons thusly: If my wife is
    faithful, then the husband of the unfaithful wife would know that
    his wife is unfaithful (using the reasoning of the preceeding
    paragraph) on the first night. Since he didn't write her name
    on the first night, my wife must be unfaithful. So, on the second
    night both men will write their wives name on the board and the
    sequence of numbers of names on the board would be 0,2 and no more
    names would be added after that.
    It's an easy induction argument to show that for N unfaithful
    wives the sequence of numbers of names on the board would be
    N-1 nights of 0 followed by nights of the same N names on the board
    thereafter.

  10. This type of game is widely known as "Penney's Game". The Penney is Walter Penny who made quite a few puzzles in the 60's and 70's.

    I posted nearly 50 of his puzzles (from unpublished papers of his) a few years ago on this forum. You can look at some of them if you search

    for Penney on this site. They are quite clever puzzles!


  11. If, by the problem you mean that, if we pick subsets in such a way that every subset


    is equally likely to be chosen as any other subset, and we label them A and B randomly,
    then you have Bonanova's case where a=b=1/2 for the probability that A⊆ B which,
    I agree with Bonanova, is (0.75)n.

    If, on the other hand, you mean that, if we pick subsets in such a way that every subset
    is equally likely to be chosen as any other subset, and we label them A and B and we ask
    what is the probability that A⊆ B or B⊆ A (in other words, whether the smaller subset is
    a subset of the larger), then the probability is (3n-2n-1)/22n-1.
×
×
  • Create New...