A game of nim determine value of X,Y [closed]












0












$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










share|cite|improve this question











$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
















0












$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










share|cite|improve this question











$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














0












0








0





$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










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 5 at 21:09









Jyrki Lahtonen

109k13169372




109k13169372










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


















  • $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










2 Answers
2






active

oldest

votes


















1












$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}$.






share|cite|improve this answer











$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



















0












$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.






share|cite|improve this answer









$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


















2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$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}$.






share|cite|improve this answer











$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
















1












$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}$.






share|cite|improve this answer











$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














1












1








1





$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}$.






share|cite|improve this answer











$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}$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 5 at 19:38

























answered Jan 5 at 19:11









Zachary HunterZachary Hunter

57611




57611








  • 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




    $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











0












$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.






share|cite|improve this answer









$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
















0












$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.






share|cite|improve this answer









$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














0












0








0





$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.






share|cite|improve this answer









$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.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 5 at 19:57









saulspatzsaulspatz

14.8k21329




14.8k21329












  • $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






  • 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



Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅