Results 1 to 15 of 15

Math Help - Discrete/n by m prob

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Discrete/n by m prob

    Anyone have any idea how to do #3 on:

    http://www.bioalgorithms.info/moodle...ks/hw0/hw0.pdf

    My professor said she solved it using a checkerboard.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    now if it weren't password protected that would be nice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    221
    Shouldn't be. I certainly did not need a password.

    http://www.bioalgorithms.info/moodle...ks/hw0/hw0.pdf

    Hmm. Not sure why you're getting a password. I can type it out if need be.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Ideasman View Post
    Shouldn't be. I certainly did not need a password.

    http://www.bioalgorithms.info/moodle...ks/hw0/hw0.pdf

    Hmm. Not sure why you're getting a password. I can type it out if need be.
    Because you probably have a cookie set, but you won't get much response
    to your question if we have to create an account and or login to see it.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Ideasman View Post
    I can type it out if need be.
    Please do.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2006
    Posts
    221
    Two players play the following game with two “chromosomes” of length
    n and m nucleotides. At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts. For example, the first player can destroy a chromosome of length n and break another chromosome into two chromosomes of length m/3 and m − m/3 . The player left with two single-nucleotide chromosomes loses.

    Who will win? Describe the winning strategy for each n and m.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2006
    Posts
    221
    I still have no idea where to start with this problem. For any n and m, I am assuming there might be 2 different cases for even/odd?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by Ideasman View Post
    Two players play the following game with two “chromosomes” of length
    n and m nucleotides. At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts. For example, the first player can destroy a chromosome of length n and break another chromosome into two chromosomes of length m/3 and m − m/3 . The player left with two single-nucleotide chromosomes loses.

    Who will win? Describe the winning strategy for each n and m.
    Quote Originally Posted by Ideasman View Post
    I still have no idea where to start with this problem. For any n and m, I am assuming there might be 2 different cases for even/odd?
    Solve the game backwards as in this thread and this one.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2006
    Posts
    221
    Um,

    LWLWLWLW
    WLWLWLWL
    ...
    ...
    ...

    Don't the L's and W's just alternate?

    EDIT: Err, nevermind, every other row is W's?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Sep 2006
    Posts
    221
    I spent some more time looking at the problem. I tried doing a 13 by 13 matrix.

    I got the following:

    Code:
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    ...and the pattern just repeats.

    Assuming this is right, I think the strategy would be to give your opponent a pile of odd # nucleotides and another pile of odd nucleotides; if you give your opponent a pile of even and a pile of odd, they will win (assuming they know the strategy). Player one will always win if he goes first (will win if at least one chromosome pile has an even number of nucleotides). Player 2 will always win if the start piles both have an odd # of nucleotides.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    does it have to be m/3, or could it be m/4 or anything the player chooses.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Sep 2006
    Posts
    221
    Has to be m/3, or at least that's how I interpret the problem.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by Ideasman View Post
    Two players play the following game with two “chromosomes” of length
    n and m nucleotides. At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts. For example, the first player can destroy a chromosome of length n and break another chromosome into two chromosomes of length m/3 and m − m/3 . The player left with two single-nucleotide chromosomes loses.

    Who will win? Describe the winning strategy for each n and m.
    Quote Originally Posted by Quick View Post
    does it have to be m/3, or could it be m/4 or anything the player chooses.
    Quote Originally Posted by Ideasman View Post
    Has to be m/3, or at least that's how I interpret the problem.
    It looks like that is just an example to me. The rule stated was:

    At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts.

    Then came the example with m/3.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Sep 2006
    Posts
    221
    Meh, hard problem. Then I have no clue. And I thought I had it, too .
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by Ideasman View Post
    I spent some more time looking at the problem. I tried doing a 13 by 13 matrix.

    I got the following:

    Code:
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    WWWWWWWWWWWWW
    LWLWLWLWLWLWL
    ...and the pattern just repeats.

    Assuming this is right, I think the strategy would be to give your opponent a pile of odd # nucleotides and another pile of odd nucleotides; if you give your opponent a pile of even and a pile of odd, they will win (assuming they know the strategy). Player one will always win if he goes first (will win if at least one chromosome pile has an even number of nucleotides). Player 2 will always win if the start piles both have an odd # of nucleotides.
    Quote Originally Posted by Quick View Post
    does it have to be m/3, or could it be m/4 or anything the player chooses.
    Quote Originally Posted by Ideasman View Post
    Has to be m/3, or at least that's how I interpret the problem.
    Quote Originally Posted by JakeD View Post
    It looks like that is just an example to me. The rule stated was:

    At every turn a player can destroy one of the chromosomes and break another one into two nonempty parts.

    Then came the example with m/3.
    Quote Originally Posted by Ideasman View Post
    Meh, hard problem. Then I have no clue. And I thought I had it, too .
    I think your solution is correct as is. The m/3 restriction is not needed.

    A simple proof by induction is possible. Establish the base case that a 2-pile is a winning position and a 3-pile is a losing one. Then for n > 3, an n-pile with n even is winning because it breaks into two odd piles, both of which are losing for the opponent. An n-pile with n odd is losing because it must break into an even pile and an odd pile. The even pile is a winning one for the opponent.
    Last edited by JakeD; November 3rd 2006 at 02:03 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Discrete Prob
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 3rd 2011, 01:29 PM
  2. Replies: 2
    Last Post: April 12th 2011, 11:13 AM
  3. prob
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 26th 2009, 04:56 AM
  4. 2 discrete math prob
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2007, 05:24 PM
  5. discrete prob
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 22nd 2007, 02:09 PM

Search Tags


/mathhelpforum @mathhelpforum