A game of nim determine value of X,Y [closed]
$begingroup$
Alex and Bob plays a game
A box contains numbers from 1 to 1024
Alex goes first
Alex removes 512 numbers
Bob removes 256 numbers
Alex removes 128 numbers
Bob removes 64 numbers
Alex removes 32 numbers
Bob removes 16 numbers
Alex removes 8 numbers
Bob removes 4 numbers
Alex removes 2 numbers
this goes on until 2 numbers remain in the box x,y
Alex plays to maximize the value of |x-y| in the end
Bob plays to minimize this value
Both play optimally what are the 2 numbers that remain in the box in the end
My work:
I made a program for this such the Alex's task is to remove pairs with least value of |i-j|
And Bob's task is to remove pairs with max value of |i-j|
Answer I got was x=171,Y=854 which isn't correct please help me with this
combinatorics game-theory
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
$endgroup$
closed as off-topic by Davide Giraudo, Paul Frost, mrtaurho, Leucippus, user91500 Jan 6 at 8:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, mrtaurho, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.
|
show 2 more comments
$begingroup$
Alex and Bob plays a game
A box contains numbers from 1 to 1024
Alex goes first
Alex removes 512 numbers
Bob removes 256 numbers
Alex removes 128 numbers
Bob removes 64 numbers
Alex removes 32 numbers
Bob removes 16 numbers
Alex removes 8 numbers
Bob removes 4 numbers
Alex removes 2 numbers
this goes on until 2 numbers remain in the box x,y
Alex plays to maximize the value of |x-y| in the end
Bob plays to minimize this value
Both play optimally what are the 2 numbers that remain in the box in the end
My work:
I made a program for this such the Alex's task is to remove pairs with least value of |i-j|
And Bob's task is to remove pairs with max value of |i-j|
Answer I got was x=171,Y=854 which isn't correct please help me with this
combinatorics game-theory
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
$endgroup$
closed as off-topic by Davide Giraudo, Paul Frost, mrtaurho, Leucippus, user91500 Jan 6 at 8:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, mrtaurho, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05
|
show 2 more comments
$begingroup$
Alex and Bob plays a game
A box contains numbers from 1 to 1024
Alex goes first
Alex removes 512 numbers
Bob removes 256 numbers
Alex removes 128 numbers
Bob removes 64 numbers
Alex removes 32 numbers
Bob removes 16 numbers
Alex removes 8 numbers
Bob removes 4 numbers
Alex removes 2 numbers
this goes on until 2 numbers remain in the box x,y
Alex plays to maximize the value of |x-y| in the end
Bob plays to minimize this value
Both play optimally what are the 2 numbers that remain in the box in the end
My work:
I made a program for this such the Alex's task is to remove pairs with least value of |i-j|
And Bob's task is to remove pairs with max value of |i-j|
Answer I got was x=171,Y=854 which isn't correct please help me with this
combinatorics game-theory
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
$endgroup$
Alex and Bob plays a game
A box contains numbers from 1 to 1024
Alex goes first
Alex removes 512 numbers
Bob removes 256 numbers
Alex removes 128 numbers
Bob removes 64 numbers
Alex removes 32 numbers
Bob removes 16 numbers
Alex removes 8 numbers
Bob removes 4 numbers
Alex removes 2 numbers
this goes on until 2 numbers remain in the box x,y
Alex plays to maximize the value of |x-y| in the end
Bob plays to minimize this value
Both play optimally what are the 2 numbers that remain in the box in the end
My work:
I made a program for this such the Alex's task is to remove pairs with least value of |i-j|
And Bob's task is to remove pairs with max value of |i-j|
Answer I got was x=171,Y=854 which isn't correct please help me with this
combinatorics game-theory
combinatorics game-theory
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
edited Jan 5 at 21:09
Jyrki Lahtonen
108k12166367
108k12166367
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
asked Jan 5 at 18:22
DANK UPLOADERDANK UPLOADER
12
12
closed as off-topic by Davide Giraudo, Paul Frost, mrtaurho, Leucippus, user91500 Jan 6 at 8:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, mrtaurho, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Davide Giraudo, Paul Frost, mrtaurho, Leucippus, user91500 Jan 6 at 8:34
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, mrtaurho, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05
|
show 2 more comments
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.
For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.
Explanation of Alex Method:
After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
$endgroup$
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
add a comment |
$begingroup$
Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)
What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.
So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.
Now generalize this.
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
$endgroup$
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.
For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.
Explanation of Alex Method:
After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
$endgroup$
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
add a comment |
$begingroup$
Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.
For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.
Explanation of Alex Method:
After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
$endgroup$
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
add a comment |
$begingroup$
Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.
For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.
Explanation of Alex Method:
After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
$endgroup$
Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.
For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.
Explanation of Alex Method:
After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
edited Jan 5 at 19:38
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
answered Jan 5 at 19:11
Zachary HunterZachary Hunter
54111
54111
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
add a comment |
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
1
1
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
Alex removes all the odd numbers, which makes the minimum difference $2$. Bob removes $2,4,6,8$ making the maximum difference $6$. Alex in the strategy would remove $10,14$ or $12,16$ but should really remove $12,14$ The remaining ones are $10,16$ with a difference of $6$.
$endgroup$
– Ross Millikan
Jan 5 at 19:51
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
@DANKUPLOADER: I was providing the example you asked for of the strategy in this answer, which (except for Alex's last move) seems reasonable to me. It sounds like you think Alex should take $5-12$ in the $16$ case, but then Bob takes $1-4$ and Alex only gets $13,16$ for a difference of $3$.
$endgroup$
– Ross Millikan
Jan 5 at 19:59
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
$begingroup$
This strategy makes sense to me with Alex's last move being to take the middle two numbers. If there are $2^n$ numbers at the start with $n$ even, one move by each player has us playing the game starting with $2^{n-2}$ numbers and the distances doubled. As Alex gets $3$ if $n=2$ he will get $3cdot 2^{frac {n-2}2}$ for even $n$ this way.
$endgroup$
– Ross Millikan
Jan 5 at 20:02
add a comment |
$begingroup$
Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)
What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.
So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.
Now generalize this.
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
$endgroup$
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
add a comment |
$begingroup$
Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)
What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.
So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.
Now generalize this.
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
$endgroup$
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
add a comment |
$begingroup$
Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)
What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.
So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.
Now generalize this.
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
$endgroup$
Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)
What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.
So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.
Now generalize this.
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
answered Jan 5 at 19:57
saulspatzsaulspatz
14.1k21329
14.1k21329
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
add a comment |
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
$begingroup$
That's what I think the strategy would be, but I haven't proved it. Are you sure about the $24?$ I would have guessed $48$.
$endgroup$
– saulspatz
Jan 5 at 20:11
1
1
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
$begingroup$
I agree with $48$. Alex gets four turns before the last, so can make the spacing $2^4=16$. The last gets two number $3$ places apart.
$endgroup$
– Ross Millikan
Jan 5 at 20:30
add a comment |
$begingroup$
If Alex is simply removing pairs with minimal difference, he should be rather inefficient. In his first move, there's no difference between getting rid of 513-1024, and 257-768... Meanwhile, for Bob, if the final numbers are 1,2,1023,1024, he should not remove 1,1024...
$endgroup$
– Zachary Hunter
Jan 5 at 18:33
$begingroup$
When Alex makes the last move, he removes $2$ of $4$ numbers. Which $2?$
$endgroup$
– saulspatz
Jan 5 at 18:49
$begingroup$
On that note, Alex would also handle 1,2,1023,1024 wrongly. I’ll think on this and provide some heuristics in a bit.
$endgroup$
– Zachary Hunter
Jan 5 at 18:56
$begingroup$
Yes, I know that. I was suggesting that you start with small examples and see if you can detect the pattern. You might write a program to solve the case where there are originally $16$ numbers. I think that's small enough to do completely.
$endgroup$
– saulspatz
Jan 5 at 19:01
$begingroup$
I don't know the answer; I'm just trying to help you work it out for yourself.
$endgroup$
– saulspatz
Jan 5 at 19:05