Mixing
Alice and Bob picking game
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. Thereafter, in each turn a player must pick at least one stone, but no more stones than were picked in the immediately preceding turn. The player who takes the last stone wins. With what property of $N$, will Alice win? When will Bob win?
For odd $N$ the outcome is quite clear, as Alice will start by picking one stone and will enforce the win. But what then?
game-theory combinatorial-game-theory
asked Jul 17 at 18:18
RandyR
334
add a comment |Â
up vote
6
down vote
favorite
Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. Thereafter, in each turn a player must pick at least one stone, but no more stones than were picked in the immediately preceding turn. The player who takes the last stone wins. With what property of $N$, will Alice win? When will Bob win?
For odd $N$ the outcome is quite clear, as Alice will start by picking one stone and will enforce the win. But what then?
game-theory combinatorial-game-theory
asked Jul 17 at 18:18
RandyR
334
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
2
But he told you the strategy
– greedoid
Jul 17 at 18:46
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. Thereafter, in each turn a player must pick at least one stone, but no more stones than were picked in the immediately preceding turn. The player who takes the last stone wins. With what property of $N$, will Alice win? When will Bob win?
For odd $N$ the outcome is quite clear, as Alice will start by picking one stone and will enforce the win. But what then?
game-theory combinatorial-game-theory
asked Jul 17 at 18:18
RandyR
334
Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. Thereafter, in each turn a player must pick at least one stone, but no more stones than were picked in the immediately preceding turn. The player who takes the last stone wins. With what property of $N$, will Alice win? When will Bob win?
For odd $N$ the outcome is quite clear, as Alice will start by picking one stone and will enforce the win. But what then?
game-theory combinatorial-game-theory
asked Jul 17 at 18:18
RandyR
334
edited Jul 17 at 22:41
asked Jul 17 at 18:18
RandyR
334
asked Jul 17 at 18:18
RandyR
334
asked Jul 17 at 18:18
RandyR
334
334
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
2
But he told you the strategy
– greedoid
Jul 17 at 18:46
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04
add a comment |Â
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
2
But he told you the strategy
– greedoid
Jul 17 at 18:46
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
2
2
But he told you the strategy
– greedoid
Jul 17 at 18:46
But he told you the strategy
– greedoid
Jul 17 at 18:46
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
6
down vote
accepted
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^i(m)$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $bge 2^j$. On the other hand by the rules of the game $ble 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^i(m) le b$. We will do it by showing that $b$ is divisble by $2^i(m)$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $ble 2^j$. Let us show that $i(m) le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $ble 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^j + 1 + m) ge j + 1$.
Thus we have proved that $i(m) le j$. This means $2^j + b + m$ is divisble by $2^i(m)$, as well as $m$. Hence $b$ is also divisble by $2^i(m)$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j le a$.
edited Jul 19 at 14:08
amWhy
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
add a comment |Â
up vote
3
down vote
First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^k+1$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.
If $N neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)
answered Jul 18 at 7:59
Praneet Srivastava
690515
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^i(m)$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $bge 2^j$. On the other hand by the rules of the game $ble 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^i(m) le b$. We will do it by showing that $b$ is divisble by $2^i(m)$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $ble 2^j$. Let us show that $i(m) le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $ble 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^j + 1 + m) ge j + 1$.
Thus we have proved that $i(m) le j$. This means $2^j + b + m$ is divisble by $2^i(m)$, as well as $m$. Hence $b$ is also divisble by $2^i(m)$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j le a$.
edited Jul 19 at 14:08
amWhy
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
add a comment |Â
up vote
6
down vote
accepted
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^i(m)$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $bge 2^j$. On the other hand by the rules of the game $ble 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^i(m) le b$. We will do it by showing that $b$ is divisble by $2^i(m)$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $ble 2^j$. Let us show that $i(m) le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $ble 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^j + 1 + m) ge j + 1$.
Thus we have proved that $i(m) le j$. This means $2^j + b + m$ is divisble by $2^i(m)$, as well as $m$. Hence $b$ is also divisble by $2^i(m)$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j le a$.
edited Jul 19 at 14:08
amWhy
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^i(m)$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $bge 2^j$. On the other hand by the rules of the game $ble 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^i(m) le b$. We will do it by showing that $b$ is divisble by $2^i(m)$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $ble 2^j$. Let us show that $i(m) le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $ble 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^j + 1 + m) ge j + 1$.
Thus we have proved that $i(m) le j$. This means $2^j + b + m$ is divisble by $2^i(m)$, as well as $m$. Hence $b$ is also divisble by $2^i(m)$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j le a$.
edited Jul 19 at 14:08
amWhy
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^i(m)$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $bge 2^j$. On the other hand by the rules of the game $ble 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^i(m) le b$. We will do it by showing that $b$ is divisble by $2^i(m)$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $ble 2^j$. Let us show that $i(m) le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $ble 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^j + 1 + m) ge j + 1$.
Thus we have proved that $i(m) le j$. This means $2^j + b + m$ is divisble by $2^i(m)$, as well as $m$. Hence $b$ is also divisble by $2^i(m)$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j le a$.
edited Jul 19 at 14:08
amWhy
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
edited Jul 19 at 14:08
amWhy
189k25219431
edited Jul 19 at 14:08
amWhy
189k25219431
edited Jul 19 at 14:08
amWhy
189k25219431
189k25219431
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
answered Jul 17 at 18:44
Sasha Kozachinskiy
41018
41018
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
add a comment |Â
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
What if $N=2^i$?
– Steve Kass
Jul 17 at 18:48
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy Consider a case with 4 stones. If Alice picks 3 stones, bob picks the last one and wins. If she takes 2 stones, Bob picks the last 2 and wins. If she takes a single stone, Bob takes the 2nd one, forcing her to take the 3rd stone, which again leaves Bob as the victor, taking the 4th stone.
– Praneet Srivastava
Jul 17 at 18:50
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@Sasha Kozachinskiy: Thank you. The strategy is well explained. But I couldn´t quite follow your proof by induction. Could you explain it in (some) more detail please?
– RandyR
Jul 17 at 23:22
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@RandyR, rewrote the answer to avoid induction.
– Sasha Kozachinskiy
Jul 18 at 7:46
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
@Sasha Kozachinskiy: Thank you so much for taking the extra trouble. I would never have been able to formulate this in such a clear manner!
– RandyR
Jul 18 at 8:22
add a comment |Â
up vote
3
down vote
First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^k+1$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.
If $N neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)
answered Jul 18 at 7:59
Praneet Srivastava
690515
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
add a comment |Â
up vote
3
down vote
First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^k+1$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.
If $N neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)
answered Jul 18 at 7:59
Praneet Srivastava
690515
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
add a comment |Â
up vote
3
down vote
up vote
3
down vote
First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^k+1$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.
If $N neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)
answered Jul 18 at 7:59
Praneet Srivastava
690515
First, we establish that whenever $N = 2^m$, Bob wins. We'll do this by induction. Suppose Bob is guaranteed victory for $2^k$ stones. Consider a game starting with $2^k+1$ stones. These can be grouped into two groups of $2^k$ stones each. Since Bob has a winning strategy for $2^k$ stones, He has a strategy which will allow him to play a move which finishes the first group of $2^k$ stones, forcing Alice to play with $2^k$ stones remaining. This is a situation where Bob wins, by our hypothesis. The base case is easy - If there are only 2 stones, Bob wins.
If $N neq 2^m$ then Alice wins . In such a case, write $N = 2^k +r$, where $2^k$ is the largest power of $2$ which is still smaller than $N$. Alice can then start by taking off $r$ stones. Now, since $r$ < $2^k$, Bob can't take away all the stones that are left. So Bob is forced to play with $2^k$ stones remaining, which Alice now wins (Bob is the one playing the move when $2^k$ stones are left.)
answered Jul 18 at 7:59
Praneet Srivastava
690515
edited Jul 18 at 8:25
answered Jul 18 at 7:59
Praneet Srivastava
690515
answered Jul 18 at 7:59
Praneet Srivastava
690515
answered Jul 18 at 7:59
Praneet Srivastava
690515
690515
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
add a comment |Â
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
Thank you for providing proof via induction - easy to understand and very well written!
– RandyR
Jul 18 at 8:35
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854780%2falice-and-bob-picking-game%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
"uneven" ? I think you mean "odd". Also, show the winning strategy for Alice in the case you mentioned.
– Peter
Jul 17 at 18:20
2
But he told you the strategy
– greedoid
Jul 17 at 18:46
Why did this post even get a close vote? The OP has included some effort.
– Batominovski
Jul 17 at 19:03
Perhaps upvoting will help?
– greedoid
Jul 17 at 19:06
Do you know the so called Nin games?
– Cesareo
Jul 17 at 20:04