6
$\begingroup$

The devil has suggested a deal to you. You play a game with him, if you win you go to heaven when you die, if you lose you go to hell.

Thinking you can beat him, you take him up on the offer. Here is what you have to do:

You have to get to 0 or 100 using factors of an original number.

To start with you select an original number ($x$). It has to be between 10 and 90.

The Devil can add or subtract the highest factor of $x$ which isn’t the same as $x$, unless the number is prime in which case he can use 1. You can add, subtract, multiply or divide by the smallest factor which isn’t 1, unless the number is prime in which case you can use 1. If you end up with a decimal then you round it up. The Devil always go first. You probably don't want to choose a prime because then you are both stuck with adding or subtracting 1. Numbers can go into negative and past 100, but still works the same.

So an example:

You choose $x$ to be 12

Devil's Number: Highest factor which isn't 12 = 6

Your Number: Smallest factor which isn't 1 = 2

Devils turn: 12-6 = 6

Your turn: 6+2 = 8

Devils turn: 8-6 = 2

Your turn: 2-2 = 0

You Win.

Obviously the Devil wouldn't have done that on his second go, so you need to find a way where whatever he does you still win.

Is there a way you can guarantee that you will win?

Or even better, is there a way to guarantee you win for any number you pick?

$\endgroup$
  • 5
    $\begingroup$ Um... if I pick the number, and I always go first, can't I just pick 50 and multiply by 2? $\endgroup$ – Sconibulus Nov 23 '16 at 18:48
  • $\begingroup$ @Sconibulus good point. I'll change it to devil goes first. $\endgroup$ – Beastly Gerbil Nov 23 '16 at 18:49
  • 1
    $\begingroup$ @BeastlyGerbil I didn't understand that - wouldn't he be subtracting a 1? How does it lead to instant victory even if the number is a prime? $\endgroup$ – GoodDeeds Nov 23 '16 at 19:26
  • 1
    $\begingroup$ I don't see how either player can get a non-integer result anyway. The only operation that could do that is division, and you are only ever allowed to divide by a factor of the current number. $\endgroup$ – Gareth McCaughan Nov 23 '16 at 23:31
  • 1
    $\begingroup$ ... Oh, wait, I'm completely misunderstanding this. The moves available are determined by the factors of the original number, not those of the current number? In that case my comments above are all wrong. $\endgroup$ – Gareth McCaughan Nov 23 '16 at 23:38
8
$\begingroup$

Suppose your initial number has highest nontrivial factor $a$ and smallest nontrivial factor $b$. Then the devil gets to move by $\pm a$ and you get to move by $\pm b$ as well as multiplying and dividing by $b$.

You can certainly arrange

that the devil cannot win. To do this, make $a$ odd and $b$ even, by taking your initial number to be twice an odd number. Then the devil always has to make odd-sized moves and you can always make the number even (by multiplying by $b$, which will in fact be 2) before he does, so he can never move to the even numbers 0 or 100.

However,

this is not the same thing as actually winning because maybe the devil can keep the game going on for ever. Suppose he can't. Then you can somehow arrange to reach a position in which the devil's only available moves -- from $t$ to $t\pm a$, say -- are to positions from which you win immediately. (If you can't arrange that with best diabolical play, then the devil can simply always decline to move to a position from which you win immediately.) You can win by moving to $0$ from $\pm b$, or by moving to $100$ from $100\pm b$ or from $100b-\varepsilon$ where $0\leq\varepsilon<b$ or (if $b|100$) from $100/b$.

So, at the very least,

for you to be able to win even against a stupid devil there must be some $t$ for which both $t-a$ and $t+a$ are among these six numbers. We shall see that this is quite a tough condition to meet. Let's first get some boring cases out of the way. If you pick a prime number, so that $a=b=1$, then you can never change the number by more than 1 and so the devil can simply always move away from 0 or 100 if you get near them, and therefore avoid ever losing. (We have seen above that he can't hope to do better if you choose your initial number wisely.) If you pick the square of a prime, so that $a=b=p$, the same is true. (Note that $p^2\pm p$ can't be either 0 or 100.) So let us suppose that your starting number is not of either of these forms; in particular $1<b<a$. Note also that $b\leq9$ because it's the smallest nontrivial factor of a number $\leq90$, and that $a\leq45$ because it's a nontrivial factor of a number $\leq90$. Oh, and their product $ab$ is our original number, which is $\leq90$.

Now

let's suppose there's a $t$ for which both of $t\pm a$ are among those six numbers, and suppose for a moment that $100/b$ isn't one of them. We can put the others into groups I'll call A ($\pm b$), B ($100\pm b$), and C ($100b-\varepsilon$). The two numbers in group A, or the two in group B, can't be $t\pm b$ since $a\neq b$, so $t-a,t+a$ must be in different groups. They differ by $2a\leq90$. Any number in group C is at least 199, and unless $b=2$ is at least 298; this immediately means that group C is too far away from the other two groups. So we must have one number in group A and one in group B. These differ by at least $100-2b$ and therefore $2a\geq100-2b$ or $a+b\geq50$. But this isn't actually possible, because $a\leq45$ then implies $b\geq5$ which implies $a\leq18$ since $ab\leq90$.

It follows that

if such a $t$ exists, one of the numbers $t\pm a$ must be $100/b$ -- and, in particular, the latter must be an integer. So $b$ is one of $2,4,5$. We can't actually have $b=4$ because if $4|x$ then also $2|x$ so 4 wasn't the smallest factor after all. If $b=5$ then $6\leq a\leq18$ and in particular the gap from $100/b=20$ to $100\pm b$ is too large, so our two numbers must be $\pm5$ and 20 ... which differ by an odd number which therefore cannot be $2a$. So we can't have $b=5$ either and must have $b=2$.

So then

those six numbers are $-2, 2, 50, 98, 102, 200$ and we must have $2a\in\{48,52\}$, so either $a=24$ or $a=26$, corresponding to an initial choice of either 48 or 52. In either of these cases it is at least possible for the devil to get into a losing position; and in either case there are in fact exactly two such losing positions: $26,74$ if $a=24$ and $24,76$ if $a=26$.

And in these cases

in fact you can win. If you pick $x=48$ so that $a,b=24,2$ then the devil's first move must be to $24$ or $72$. Then you move to $26$ or $74$ respectively, whereupon the devil has to move to $2$ or $50$ (in the former case) or to $50$ or $98$ (in the latter) and you win. Similarly, if you pick $x=52$ so that $a,b=26,2$ then the devil must begin by moving to $26$ or $78$; then you move to $24$ or $76$ and again he has to move to $2$ or $50$, or to $50$ or $102$ and you win.

In conclusion:

You should begin by choosing either 48 or 52 as your number. In this case you can very quickly and easily force a win. If you choose any other number, then the devil cannot lose provided he never moves to a position from which you can win instantly (and there is no position from which he can't avoid that). But for at least some other numbers, you can keep him playing for ever without any risk of your losing.

$\endgroup$
  • $\begingroup$ "the devil can simply reverse whatever moves you make" - what about multiplication and division? I don't think it changes the answer, but it needs to be addressed somehow. $\endgroup$ – ffao Nov 24 '16 at 11:39
  • $\begingroup$ Also, as long as we're rounding up, group C is 100b - epsilon, right? (Instead of 100b + epsilon) $\endgroup$ – ffao Nov 24 '16 at 11:39
  • $\begingroup$ Quite right on both. (I could have sworn it said to round down, but it never did.) Neither of these changes either the answer or the argument much, unsurprisingly. $\endgroup$ – Gareth McCaughan Nov 24 '16 at 12:30
1
$\begingroup$

Bonus question first:
"Or even better is there a way to guarantee you win for any number you pick?"

No.
For a starting pick of 75, with your lowest factor 3 and Devil's 25, the Devil makes one move:
  75 + 25 = 100
and trivially wins.

That is enough to answer the bonus question. Beyond that, there are only two other quickly decidable games; those are for starting number of 48 and 52...

For the base problem,
"Is there a way you can guarantee that you will win?"

Yes.
As @Gareth demonstrated, by selecting 48 or 52* you can force a win no matter what Devil plays.

For $\mathbf{48}$ your factor 2 and Devil's 24 give these lines of play:

     D   Y   D   Y
 48 +24  +2 +24  +2 = 100 WIN
 48 +24  +2 -24  *2 = 100 WIN
 48 -24  +2 +24  *2 = 100 WIN
 48 -24  +2 -24  -2 = 0   WIN
For $\mathbf{52}$ your factor 2 and Devil's 26 give these lines of play:
     D   Y   D   Y   D   Y   D   Y
 52 +26  -2 +26  -2 = 100 WIN
 52 +26  -2 -26  *2 = 100 WIN
 52 -26  +2 +26  -2 +26  -2 +26  -2 = 100 WIN
 52 -26  +2 +26  -2 +26  -2 -26  *2 = 100 WIN
 52 -26  +2 +26  -2 -26  -2 +26  *2 = 100 WIN
 52 -26  +2 +26  -2 -26  -2 -26  +2 = 0   WIN
 52 -26  +2 -26  -2 = 0   WIN

You can also force a win for $\mathbf{55}$, but it takes quite a bit more doing. Your factor is 5, Devil's is 11.
Here's a few of the lines of play, showing from where they diverge. Listing all play lines is huge; you get the gist of it quickly.
      D   Y   D   Y   D   Y   D   Y   D   Y   D   Y   D   Y   D   Y   D   Y   D   Y
 55  +11  +5 +11  +5 +11  +5 +11  +5 +11  +5 +11  /5 +11  /5 +11  *5 = 100 WIN
                                                             -11  /5 = 0   WIN
                                                     -11  /5 +11  /5 +11  -5 +11  *5 = 100 WIN
                                                                             -11  /5 = 0   WIN
                                                                     -11  /5 = 0   WIN
                                                             -11  /5 = 0   WIN
                                             -11  /5 +11  -5 +11  /5 +11  *5 = 100 WIN
                                                                     -11  /5 = 0   WIN
                                                             -11  *5 = 100 WIN
                                                     -11  -5 +11  *5 = 100 WIN
                                                             -11  /5 = 0   WIN
Basically, get the score to 9 and you win: Devil adds 11 to get you to 20, you multiply by 5 for 100; or Devil subtracts 11 to get you to -2, you divide by 5, rounding up to zero. You win either way.

There are probably no other games in which a win can be forced by either player. Following @Gareth's analysis, there are certainly no other strictly winnable games for you; and with four choices of operation open to you on your turn it is beyond unlikely you can be trapped in a position where you have no non-losing play. Combinatorial explosion makes exhaustive search impractical beyond around the 10th turn for each player, but at least up to that limit there are no other starting number choices that are decidable.

* I had previously excluded 52 because I wasn't properly accounting for subtotals outside the 0..100 range.
  That error has now been fixed. Apologies to Gareth for inadvertently discrediting part of his correct solution.

$\endgroup$
  • $\begingroup$ Gareth McCaughan's answer is easily fixable. I don't know how you did it but it can still be won in 2 moves each. I've placed an edit it the queue. $\endgroup$ – boboquack Nov 24 '16 at 2:38
  • 1
    $\begingroup$ hmmm, I was under the impression that if the number reach 0 or 100 you win, no matter who reach it. Since nowhere was it written that "the first to reach...win". $\endgroup$ – stack reader Nov 24 '16 at 3:02
  • $\begingroup$ So apparently I messed up somewhere. I'll look at this when I am back at my computer. $\endgroup$ – Rubio Nov 24 '16 at 3:09
  • $\begingroup$ My apologies for the typos in my answer that evidently caused confusion. $\endgroup$ – Gareth McCaughan Nov 24 '16 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.