# Discrete/n by m prob

• Oct 29th 2006, 11:19 AM
Ideasman
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.
• Oct 29th 2006, 12:23 PM
Quick
now if it weren't password protected that would be nice.
• Oct 29th 2006, 12:38 PM
Ideasman
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.
• Oct 29th 2006, 12:47 PM
CaptainBlack
Quote:

Originally Posted by Ideasman
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
• Oct 29th 2006, 12:53 PM
Quick
Quote:

Originally Posted by Ideasman
I can type it out if need be.

• Oct 29th 2006, 01:22 PM
Ideasman
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.
• Nov 1st 2006, 11:57 PM
Ideasman
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?
• Nov 2nd 2006, 01:02 AM
JakeD
Quote:

Originally Posted by Ideasman
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
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.
• Nov 2nd 2006, 02:59 PM
Ideasman
Um,

LWLWLWLW
WLWLWLWL
...
...
...

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

EDIT: Err, nevermind, every other row is W's?
• Nov 2nd 2006, 04:51 PM
Ideasman
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.
• Nov 2nd 2006, 05:14 PM
Quick
does it have to be m/3, or could it be m/4 or anything the player chooses.
• Nov 2nd 2006, 06:08 PM
Ideasman
Has to be m/3, or at least that's how I interpret the problem.
• Nov 2nd 2006, 08:15 PM
JakeD
Quote:

Originally Posted by Ideasman
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
does it have to be m/3, or could it be m/4 or anything the player chooses.

Quote:

Originally Posted by Ideasman
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.
• Nov 2nd 2006, 08:18 PM
Ideasman
Meh, hard problem. Then I have no clue. And I thought I had it, too :( .
• Nov 3rd 2006, 01:45 AM
JakeD
Quote:

Originally Posted by Ideasman
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
does it have to be m/3, or could it be m/4 or anything the player chooses.

Quote:

Originally Posted by Ideasman
Has to be m/3, or at least that's how I interpret the problem.

Quote:

Originally Posted by JakeD
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
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.