sudo apt-get purge adobereader-enu
Sunday, August 25, 2013
Saturday, June 22, 2013
a nim-like game
Two players, starting with one pile of n stones. The players take turns. In one move, the current player can pick any pile of stones and split into 2 or 3 new piles with each new pile having at least 1 stone. The player cannot make a move loses. Given n, can you determine the winner, assuming both play optimally?
The answer is deceptively simple, so spend at least one day before you look at the solution below.
Solution:
n = 1, first player loses
n >= 2, if n is even, then the first player can split into two equal piles and mimic the second players move, so the first player wins.
else n is odd, but then the first player can split into 1, k, k, assuming n = 2*k +1. Then the first player can again mimic the second players moves. So the first player wins as well.
In summary, the first player wins for all n >= 2. Simple, huh?
The answer is deceptively simple, so spend at least one day before you look at the solution below.
Solution:
n = 1, first player loses
n >= 2, if n is even, then the first player can split into two equal piles and mimic the second players move, so the first player wins.
else n is odd, but then the first player can split into 1, k, k, assuming n = 2*k +1. Then the first player can again mimic the second players moves. So the first player wins as well.
In summary, the first player wins for all n >= 2. Simple, huh?
Monday, May 13, 2013
GCJ round 1C
This round is full of frustration and nervousness and fear that I cannot advance, and I did not. The plan clearly writes, be patient and focus on the problems. But everything goes chaos when I found myself stuck in problem 1 large.
A. a simple problem but requires some care in implementation. To count the number of pairs, you need to keep track of segments with exactly n consonants and then you can start from prevStart+1 to p1, inclusive, and end with p2 to len-1, inclusive, [p1..p2] marks the current segment of n consonants.
I had an extremely ugly code with lots of if/else and while/for inside of each other. Surprisingly the code is actually correct. But I lost my confidence while waiting for it to finish running large input, and thought I had an infinite loop somewhere. After the contest, I ran the code again and found it takes only 1m24s to finish. On the other hand I have to acknowledge that a properly implemented simpler code runs only a fraction of a second.
B. I figured out the small even when panicking, and so do over 1500 other contestants. For small you can advance to X and Y at increment of 1, by taking -k, then +(k+1) until done.
The large is rather daunting, as you need to finish with minimum number of moves, and algorithms with DP or shortest path do not seem to be viable. You need an EXPLICIT strategy. I hate this as this problem gave those who have seen it before an unfair advantage. This problem falls into the category that when you see it the first time, it takes extreme ingenuity to figure out the strategy, then coding is as simple as write a single for loop.
I think I was close, but not enough to finish.
First you know that sign does not matter, you can assume X and Y being non-negative, and you only need to flip the move accordingly.
Next you try to simplify the problem a bit. What if you have only one number, say X, instead of two numbers, how do you move to get X? One then sees that you can do 1, 2, 3, ..., k such that S[k-1] < X and S[k] >= X. Now if S[k] = X, then you are done. Otherwise S[k] > X. In this case we know we need to flip at least one number in 1, 2, ..., k-1 to make the sum equal X. However there is a catch. Flipping a number j to -j will change S[k] to S[k] - 2*j, in other words, flipping sign can never change the parity of S[k]. So we need S[k] to agree with X in parity, if not we need to get one more number k+1 so that S[k+1] agrees in parity with X.
Now consider two cases:
Case 1: S[k-1] < X and S[k] > X, and S[k] and X agree with parity. Then we can show that (S[k] - X) / 2 <= k. Notice that S[k] - X is even in this case. Simple algebra tells us that this is the same as S[k] <= X + 2k, which is S[k-1] <= X +k, and that obviously holds as we have S[k-1] < X.
Case 2: S[k-1] < X and S[k] > X and S[k] and X disagree with parity. Then we need (S[k+1] - X) / 2 <= k+1 so we can flip the sign of the number j = (S[k+1] - X) / 2. This turns out to be S[k] <= X+k+1, which is S[k-1] <= X+1, and obviously this holds.
Given above, we have actually figured out a way to make X, using minimum number of moves. Now how do we generalize to two numbers, X and Y?
Behold, the trick is.....
NOTHING. You heard it right, nothing, just like the response when Pau, the Panda asks for the secret ingredient. We use the same strategy for two numbers, X and Y.
Well, not quite, but it is close to the truth. Take a step back, and consider what is the necessary number of moves to get X and Y. If we can get X and Y, then we should be able to get |X| + |Y|, just combine the moves into 1 dimension. OK, so now what is necessary to get |X| + |Y|. Our previous discussion tells us that we need k moves such that S[k-1] < |X| + |Y| and S[k] >= |X| + |Y|. In case S[k] and |X| + |Y| disagree in parity, we need one more move, that is k+1. Clearly it is necessary, but why is it sufficient, or rather, is i actually sufficient? The problem setter is clever enough that he/she does not want those who can make only this far to pass, so he/she is asking for the actual moves instead of merely the number of moves, which I would have guessed by going this far.
Now why this k or k+1 moves is sufficient, and what is a strategy and did achieve X and Y simultaneously? There are many false starts for possible proofs, because some claims that one tries to make is simply false. Let's run an example to see what is going on. To make things easier we actually start from X, Y and decrease them to zero. The strategy? Always bring down the larger of the two, of course you take the one with larger abs value.
Let X = 3 and Y = 6, the above tells us that we need at least 1,2,3,4,5 moves.
X Y
1,2,3,4,5 3 6
1,2,3,4 3 1
1,2,3 1 1
1,2 2 1
1 0 1
0 0
OK, so you see it, and some conjectures, or false claims could be dismissed. The X and Y may not going down all the time, they might even go up temporarily. And X and Y could be both smaller than k, the next available move (although you can use move from 1 to k, it seems more reasonable to use move = k). However both X and Y did arrive at 0. Then what is the invariant in the iterations to make this final state eventually achieved?
The claim: at every iteration, S[k] >= |X| + |Y| and S[k] agree in parity with |X| + |Y|.
The corollary: X and Y must go down to 0 eventually, since k will go down to 0.
Proof of the claim: In the beginning it is true, so we have base case covered. After one move, w.l.o.g. we may assume X >= 0 and Y >= 0, and X >= Y. Now our move will update (X,Y) to (X-k, Y). We have two cases:
Case 1: X-k >= 0, then we have X-k, Y as the new X and Y, and our S[k] becomes S[k-1], both X+Y and S[k] decrease by exactly k, so our claim X + Y <= S[k] and agree with parity holds.
Case 2: X-k < 0, in this case we need to show k - X + Y <= S[k-1] and they agree in parity. The parity part is easy, as X + Y and X - Y have same parity with S[k], which is S[k-1] + k, as is S[k-1] - k. Now we show the inequality. We have two subcases.
Subcase 1: S[k-1] < X + Y <= S[k] and X + Y agree in parity with S[k]. Then we need to show k - X + Y <= S[k-1], which is k + Y <= S[k-1] + X. Since X >= Y, for any k >= 3 we know this inequality is true. If k = 2, then we know X + Y <= S[2] = 1+2, then X and Y is either 1,1 or 1,2, both are easy to deal with. Similarly we can deal with k = 1.
Subcase 2: S[k-2] < X + Y <= S[k-1] and X + Y disagree in parity with S[k-1], then our move is (k - X, Y) and we need k - X + Y <= S[k-1]. This is almost the same as Subcase 1.
Whew! We have actually proved that the strategy actually works.
Now the take-home message, in graph theory book, there is an acronym:
The Obvious Necessary Condition Is Also Sufficient, that is TONCIAS.
A. a simple problem but requires some care in implementation. To count the number of pairs, you need to keep track of segments with exactly n consonants and then you can start from prevStart+1 to p1, inclusive, and end with p2 to len-1, inclusive, [p1..p2] marks the current segment of n consonants.
I had an extremely ugly code with lots of if/else and while/for inside of each other. Surprisingly the code is actually correct. But I lost my confidence while waiting for it to finish running large input, and thought I had an infinite loop somewhere. After the contest, I ran the code again and found it takes only 1m24s to finish. On the other hand I have to acknowledge that a properly implemented simpler code runs only a fraction of a second.
B. I figured out the small even when panicking, and so do over 1500 other contestants. For small you can advance to X and Y at increment of 1, by taking -k, then +(k+1) until done.
The large is rather daunting, as you need to finish with minimum number of moves, and algorithms with DP or shortest path do not seem to be viable. You need an EXPLICIT strategy. I hate this as this problem gave those who have seen it before an unfair advantage. This problem falls into the category that when you see it the first time, it takes extreme ingenuity to figure out the strategy, then coding is as simple as write a single for loop.
I think I was close, but not enough to finish.
First you know that sign does not matter, you can assume X and Y being non-negative, and you only need to flip the move accordingly.
Next you try to simplify the problem a bit. What if you have only one number, say X, instead of two numbers, how do you move to get X? One then sees that you can do 1, 2, 3, ..., k such that S[k-1] < X and S[k] >= X. Now if S[k] = X, then you are done. Otherwise S[k] > X. In this case we know we need to flip at least one number in 1, 2, ..., k-1 to make the sum equal X. However there is a catch. Flipping a number j to -j will change S[k] to S[k] - 2*j, in other words, flipping sign can never change the parity of S[k]. So we need S[k] to agree with X in parity, if not we need to get one more number k+1 so that S[k+1] agrees in parity with X.
Now consider two cases:
Case 1: S[k-1] < X and S[k] > X, and S[k] and X agree with parity. Then we can show that (S[k] - X) / 2 <= k. Notice that S[k] - X is even in this case. Simple algebra tells us that this is the same as S[k] <= X + 2k, which is S[k-1] <= X +k, and that obviously holds as we have S[k-1] < X.
Case 2: S[k-1] < X and S[k] > X and S[k] and X disagree with parity. Then we need (S[k+1] - X) / 2 <= k+1 so we can flip the sign of the number j = (S[k+1] - X) / 2. This turns out to be S[k] <= X+k+1, which is S[k-1] <= X+1, and obviously this holds.
Given above, we have actually figured out a way to make X, using minimum number of moves. Now how do we generalize to two numbers, X and Y?
Behold, the trick is.....
NOTHING. You heard it right, nothing, just like the response when Pau, the Panda asks for the secret ingredient. We use the same strategy for two numbers, X and Y.
Well, not quite, but it is close to the truth. Take a step back, and consider what is the necessary number of moves to get X and Y. If we can get X and Y, then we should be able to get |X| + |Y|, just combine the moves into 1 dimension. OK, so now what is necessary to get |X| + |Y|. Our previous discussion tells us that we need k moves such that S[k-1] < |X| + |Y| and S[k] >= |X| + |Y|. In case S[k] and |X| + |Y| disagree in parity, we need one more move, that is k+1. Clearly it is necessary, but why is it sufficient, or rather, is i actually sufficient? The problem setter is clever enough that he/she does not want those who can make only this far to pass, so he/she is asking for the actual moves instead of merely the number of moves, which I would have guessed by going this far.
Now why this k or k+1 moves is sufficient, and what is a strategy and did achieve X and Y simultaneously? There are many false starts for possible proofs, because some claims that one tries to make is simply false. Let's run an example to see what is going on. To make things easier we actually start from X, Y and decrease them to zero. The strategy? Always bring down the larger of the two, of course you take the one with larger abs value.
Let X = 3 and Y = 6, the above tells us that we need at least 1,2,3,4,5 moves.
X Y
1,2,3,4,5 3 6
1,2,3,4 3 1
1,2,3 1 1
1,2 2 1
1 0 1
0 0
OK, so you see it, and some conjectures, or false claims could be dismissed. The X and Y may not going down all the time, they might even go up temporarily. And X and Y could be both smaller than k, the next available move (although you can use move from 1 to k, it seems more reasonable to use move = k). However both X and Y did arrive at 0. Then what is the invariant in the iterations to make this final state eventually achieved?
The claim: at every iteration, S[k] >= |X| + |Y| and S[k] agree in parity with |X| + |Y|.
The corollary: X and Y must go down to 0 eventually, since k will go down to 0.
Proof of the claim: In the beginning it is true, so we have base case covered. After one move, w.l.o.g. we may assume X >= 0 and Y >= 0, and X >= Y. Now our move will update (X,Y) to (X-k, Y). We have two cases:
Case 1: X-k >= 0, then we have X-k, Y as the new X and Y, and our S[k] becomes S[k-1], both X+Y and S[k] decrease by exactly k, so our claim X + Y <= S[k] and agree with parity holds.
Case 2: X-k < 0, in this case we need to show k - X + Y <= S[k-1] and they agree in parity. The parity part is easy, as X + Y and X - Y have same parity with S[k], which is S[k-1] + k, as is S[k-1] - k. Now we show the inequality. We have two subcases.
Subcase 1: S[k-1] < X + Y <= S[k] and X + Y agree in parity with S[k]. Then we need to show k - X + Y <= S[k-1], which is k + Y <= S[k-1] + X. Since X >= Y, for any k >= 3 we know this inequality is true. If k = 2, then we know X + Y <= S[2] = 1+2, then X and Y is either 1,1 or 1,2, both are easy to deal with. Similarly we can deal with k = 1.
Subcase 2: S[k-2] < X + Y <= S[k-1] and X + Y disagree in parity with S[k-1], then our move is (k - X, Y) and we need k - X + Y <= S[k-1]. This is almost the same as Subcase 1.
Whew! We have actually proved that the strategy actually works.
Now the take-home message, in graph theory book, there is an acronym:
The Obvious Necessary Condition Is Also Sufficient, that is TONCIAS.
Monday, May 6, 2013
GCJ round 1B
A. Notice that you always take a prefix after sorting.
B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k
C. DP, although many topcoders use trie.
dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)
dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
cut dict[w] from the end of S[0..i-1]
for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away
One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector for dict is 10 times slower than using char[][], which means a difference of 15min vs 1.5 min
B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k
C. DP, although many topcoders use trie.
dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)
dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
cut dict[w] from the end of S[0..i-1]
for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away
One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector
Thursday, May 2, 2013
TC SRM 578 div1
p250, very similar to a previous tc 250 problem. The first step is to identify components, that is, nodes with L1 distance <= dist with 'v'. Then we have the count of each component. Let odd and even be the number of components with odd and even number of nodes, to get an overall even count, we must choose an even number of odd components and any number of even components.
An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)
A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.
Some contestant even implemented choose[n][r] and do the actual summation.
One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.
p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.
dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.
An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)
A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.
Some contestant even implemented choose[n][r] and do the actual summation.
One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.
p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.
dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.
Friday, April 26, 2013
SRM 577 div2
I solved all 3, and placed 7th in div2.
p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.
First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.
Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)
Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.
Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:
class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1
class b: a+1, b-2, ...
class a: b-1, a+2, ...
Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1
The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.
p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.
First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.
Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)
Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.
Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:
class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1
class b: a+1, b-2, ...
class a: b-1, a+2, ...
Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1
The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.
Sunday, April 7, 2013
SRM 575 div 1
250, had some idea but could not finish. Submitted an obviously faulty version.
The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.
To start, make a table for C = 1 to 16, and this gives some idea.
if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.
and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.
If you have gone this far, an induction proof is all you need, and that's easy.
if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is of the form 2^l * odd, and that is a WIN.
if C is odd, then we need to show every move leads to WIN. An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.
if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.
We are now complete in the induction proof.
The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.
To start, make a table for C = 1 to 16, and this gives some idea.
if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.
and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.
If you have gone this far, an induction proof is all you need, and that's easy.
if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is of the form 2^l * odd, and that is a WIN.
if C is odd, then we need to show every move leads to WIN. An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.
if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.
We are now complete in the induction proof.
Subscribe to:
Posts (Atom)
