The subtraction game

Question

Alice and Bob play a game that starts by Bob picking a secret integer $N\ge100$. Then the game goes through several rounds.

• In every round, Alice picks an integer $x\ge3$. Every number can be picked at most once (and hence cannot be picked again in later rounds).
• Alice announces $x$ to Bob.
• If $x$ divides Bob's current secret value $N$, then Alice wins and the game ends.
• If $x$ does not divide Bob's current secret value $N$, then Bob subtracts $x$ from $N$ (and thus replaces his old secret value by $N-x$).
• If the secret value ever becomes non-positive, then Bob wins and the game ends.

Question: Can Alice enforce a win? (As usual, we assume that Alice and Bob use optimal strategies.)

Answer 1

If Alice plays [3, 7, 5, 8, 6, 15, 4, 10, 27, 12, 9, 20, 13, 24, 19, 60, 32, 40, 38, 30, 72, 120]

and Bob's integer is greater than 202

then Alice wins.

Proof: check 203 through 203+120. Check that Alice's strategy covers every residue class (mod 120).

Have fun optimizing 202 down.

I found this sequence using a program and this page. Specifically, Erdos discovered that every integer lies in one of the modular residue classes 0 (mod 3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), or 26(120). By inserting numbers between these guesses, Alice can cover all of these residue classes.

Answer 2

This is (surprisingly) actually a win for Alice!

If she chooses [9, 5, 4, 11, 6, 14, 3, 8, 15, 12, 18, 7, 16, 24, 13, 36, 63, 48] she is guaranteed to win for any number greater than 96.

Using the covering system given by Lopsy in the accepted answer I was able to get some slightly better solutions, but all still around 200. This paper gives other covering systems that exclude 2 that are slightly smaller than the one found by Erdos, and I was able to shuffle the numbers around until I got a valid solution.

Edit to give more details:

The covering system used is

{ 1 (mod 3), 2(4), 5(6), 4(8), 0(9), 3(12), 0(16), 15(18), 8(24), 21(36), 24(48) }

These are the bold numbers in the solution above.

Every integer from 1 to 144 is in one (or more) of these residue classes, and since each modulus is a factor of 144, the pattern repeats and every integer above 144 is also captured in the same way. The paper proves that this one of a few distinct (i.e. no repeating moduli) covering systems with 11 residue classes that exclude 2 as a modulus, and there are no such systems with less than 11 classes.

The difficulty was finding a way to order them efficiently, by inserting numbers to fill the gaps (the non bold numbers at the top of the answer) so the residue classes line up properly. I initially created a program to generate valid orderings minimizing the sum of the extra numbers added, but could not get a solution that worked for every number above 100.

There were some "tricky numbers" that evaded capture. For instance, the only residue class that contains 120 in the covering system is 24 (mod 48). Any solution that included 48 near the beginning ended up being too long and missed lots of other numbers, but we can capture it using one of inserted numbers. In this case 15 deals with the problem.

I tried to create a program that intelligently made guesses to capture these "tricky numbers", but in the end got the answer by just generating several million sets of "bad" (i.e. non-optimal) guesses until it found one that worked.

Edit 2: I have tweaked the weights and reduced the bound to 93 with the following set:

{ 9, 5, 4, 7, 3, 8, 12, 21, 18, 14, 6, 10, 11, 24, 16, 33, 36, 27, 48 }

As you can see, instead of just guessing 21 between 6 and 24 to efficiently get the next number, making 2 guesses of 10 and 11 helps capture more of the "tricky numbers".

I've generated over a billion sets and cant find anything better than this - I would be very interested to see if anyone can reduce the bounds lower than 93!

Edit 3:

Reduced down to 87 with the following set of guesses:

{ 16, 3, 7, 4, 9, 5, 8, 13, 6, 10, 24, 18, 12, 11, 14, 17, 23, 48, 37, 36 }

Again, instead of just adding 17 between guessing 12 and 48 (which would give us a solution that doesn't work for 168 and 216) we can make a bunch of extra guesses to capture these numbers. I'm just generating millions of these sets relatively randomly. After each guess it it picks a random modulus from the covering system if the residue will be correct, and if not I choose a random moduli and add either the residue difference or some valid amount less than this. I'm sure someone cleverer than me can come up with a better way to do this!

This set was also generated with an affine equivalent covering set based on the description given in the paper. I generated all possible valid covering sets and the covering set below seemed to give the best sets of guesses with my algorithm:

{ 1 (mod 3), 0(4), 5(6), 6(8), 6(9), 9(12), 2(16), 9(18), 18(24), 3(36), 26(48) }

I am going to retry writing an algorithm that actually searches the solution space properly, but the randomness of the residue sets makes pruning out bad guesses pretty difficult.

Answer 3

Alice has a very simple starting strategy that guarantees a win at least one-third of the time regardless of Bob's strategy.

Randomly choose one of 3, 4, and 5. If she chooses 4 or 5, choose 3 next.

Why this works:

All integers are either $3x$, $3x+1$, or $3x+2$ for some integer $x$. If Bob chooses a multiple of 3 there is a 1 in 3 chance Alice will choose 3 and win right away. If Bob chooses a number that's one more than a multiple of 3, Alice has a 1 in 3 chance of choosing 4 first, so $3x+1-4=3x-3=3(x-1)$ which is a multiple of 3, which is what Alice will choose second. If Bob chooses $3x+2$, then if Alice chooses 5 first $3x+2-5=3(x-1)$ and Alice will get it when she chooses 3 second. So because Bob (nor Alice) knows what Alice will choose first, Bob has no way to defend against Alice's strategy.

I believe that there is a strategy under which Alice can always win by choosing the a certain series of numbers in order, however I have not yet found the right series. My reasoning is as follows:

My strategy for trying to determine the series is similar to how the sliding bolt puzzle works. If you look at this in terms of modular arithmetic, we are simply trying to eliminate possible states and force the solution to move to a single state regardless of where it started from.

The way to analyze a particular series of numbers is to look at in terms of the modulo of the least common multiple of all the numbers. For example, let's look at if 2 were allowed, but the only numbers we could use were 2, 3, 4, 6, 8, and 9. The least common multiple of these numbers is 72, so we are interested in X mod 72. Initially, X mod 72 could be any number between 0 and 71. If we choose 2 first and it's not a multiple of 2, then X-2 mod 72 could be any odd number between 1 and 71. If we then choose 3, then X-2 mod 72 could not be 3, 9, etc. so X-5 mod 72 could not be an odd number or 0, 6, 12, etc. There are many more states than in the sliding bolt puzzle, but I feel like there should be a way to whittle away the possibilities until it has been forced into a single state.

Answer 4

Edited:

This is wrong - see Lopsy's answer. The hole in the proof is the claim that Alice removes at most 1/n numbers with a pick of n. Because of the existence of covering systems, she starts off with a lot more information than I thought, and so she can remove more numbers.

It turns out that Erdos is smarter than me...

---

No, Alice can't force a win, because she doesn't get enough information from each turn to improve her choices.

Any time Alice picks a number n, she removes at most 1/n numbers from the pool of Bob's possible picks (less than that if she picks badly). She can't repeat, so after k picks the best she could have done is to leave $\frac{2}{3}.\frac{3}{4}...\frac{k+1}{k+2}$ of the entries still in the pool.

The log of $\frac{k-1}{k}$ approximates to $-\frac{1}{k}$, so the log of the entire fraction will be more than $-\frac{1}{3} - \frac{1}{4} - ... - \frac{1}{k+2}$, which is more than $-(ln(k+2) + 1)$, since it's a subset of the harmonic series. Therefore the fraction of the original numbers that remain is larger than $\frac{1}{e.(k+2)}$.

But the sum of those k picks must be at least $\frac{k(k+1)}{2}$. Multiplying those two numbers together we get $\frac{k(k+1)}{2e(k+2)}$ which will be larger than 1 for k > 6, and converges on $\frac{k}{2e}$, a steadily increasing number. This means there are at least some numbers which Alice can't eliminate and which will win for Bob.

Therefore, if Bob knows what Alice's numbers will be, he can win - so there can't be a forcing strategy for Alice. She can win (her odds are clearly at least 1/3), but can't guarantee it. The chances of a particular number winning will converge on $\frac{1}{ek}$, so the bigger the number Bob picks, the worse his chances. He'll do best with a randomly chosen number near 100.

Answer 5

Alice can enforce a win.

Bob picks a number, which is always in the form of 100 + 12*m + n, with m >= 0 and n from 0 to 11. By dividing/substracting alternating by 3 and 4, Alice can enforce a win in turn 5 the latest. As we only divide by 3 and 4, the pattern repeats itself every 12 numbers.

Base    Div 3   Div 4   Div 3   Div 4   Div 3
100     97      93      -       -       -
101     98      94      91      87      -
102     -       -       -       -       -
103     100     -       -       -       -
104     101     97      94      90      -
105     -       -       -       -       -
106     103     99      -       -       -
107     104     -       -       -       -
108     -       -       -       -       -
109     106     102     -       -       -
110     107     103     100     -       -
111     -       -       -       -       -

Answer 6

With the restrictions imposed in the question, it's not possible for Alice to guarantee win.

Using "optimal strategy", Alice must not guess using any number larger than 100 - the reasoning behind this is that if Bob picks the number 100, 101, 102, or 103, and Alice picked a larger number than 100 (and didn't win), Bob would automatically win; in order for Alice's strategy to be "optimal", it must encompass the ability to derive a win no matter the number (including numbers 100 - 103). (In other words, it's not optimal to pick anything higher than 100).

The problem comes when she starts using small numbers. Because Alice cannot repeat numbers, and she doesn't want to go into the negatives, she further limits her usable number set - she can't use anything that's higher than 51 (51 included). If she picks 51 and Bob picked 100, she now has to derive from 49; but what if Bob picked 101? or 102? Now she has to derive from x - 51, and if that just so happened to be a prime number that's higher than what she has left, well, she's screwed (As in it's just not optimal).

There are three ways for Alice tolook at this: Starting small, starting big (relatively large numbers, eg 50 - 75 ish), or going at random.

Because the OP said "assume optimal strategies are used", Alice will not go at random. (Clearly not optimal).

If she starts big, she runs the risk of going under - as in, if she starts big, she could instantly throw herself under the bus and drop into a negative value, thus losing the game. This has the second largest risk out of the 3 approaches, and is not optimal.

If she starts small, eventually Alice runs out of small factors for what's left at the end of the spectrum. Using up all the numbers from 3 to 12 really quickly will destroy her chances at solving the problem if bob's number was relatively big.

eg: Starting at base case of 100, since Alice must allow for the chance of 100 to be chosen.

100 % 3 leaves 97; 97 is instantly a prime number, so this cannot be the optimal strategy.

100 % 4 works; 101 % 4 = 97; prime number, uh oh.

100 % 5 works; 101 % 5 = 96 -> 96 % (lowest of the following factors  1,2,3,4,6,8,12,16,24,32,48,96, which is 3) = works.
We can follow the pattern and every time, at some point you'll end up with a prime number. (If you could suddenly guess the prime number, it wouldn't be optimal - it would only work for specific case).

I personally spent hours coding different variants of patterns to try and devise an optimal strategy, all of which lead to one inevitable result - Eventually, you hit a number that is a prime number that is too high. The moment you use that prime number, at some point in the list of possible numbers (which again I must remind you is infinite), you will hit a new prime number for which you will need another specific use case.

(Note that I also considered and tried variants of subtracting numbers from the prime numbers and then continuing. Keep reading for those algorithms, but at the end of the day you can't achieve 100% winrate.)

Because there are an infinite number of primes (See Euclids proof: https://primes.utm.edu/notes/proofs/infinite/euclids.html), there is no optimal strategy that works for ALL numbers.

Basically, whether Alice wins or not comes down to blind luck.

Best algorithm with no repeats that I could find (to give highest winrate for Alice) (This algorithm could be extended but you will always have those numbers where you miss and go negative...) (13.6% failrate out of 9900 tests (numbers 100 to 10000)) Here, Alice wins 86.4% of the time (which is decent in a universe of infinite numbers). Even when increasing the number of test cases by a factor of 10, the failrate stays about the same.

old - fairly consistent 13.6% failrate:

(20);(3);(9);(10);(12);(6);(4);(5);(17);(8);(11);(12);(13);(15);(17);

edit: new Algorithm, 10% failrate ramping up towards 13.1% at 99900 tests!

(5);(6);(4);(3);(8);(9);(7);(12);(10);(15);(49);(14);

Now, if the conditions were changed to say.. allow a single repeat.... that would be a different story and a different set of calculations.

I did manage to find an algorithm (If we were allowed to repeat the number "3" just one time) that only fails 40 out of 400 tries. Upon further testing, it fails 90 out of 900 tries. 990 fails out of 9900 tries. (10% failrate overall, which IMO in a universe of infinite numbers is pretty good for Alice. She wins 90% of the time) Woah! 3 flipping percent with half the length of the other algorithms from the ability to repeat one number? I wonder what adding more repeats would allow... ;)

The said algorithm if you're inclined to try it:

20, 3, 9, 5, 12, 6, 4, 10, 7, 14, 3

edit: Crayziman's algorithm (95% winrate at 99900 test cases)

! 3,7,3,13,6,15,4,18,12

edit: Crayziman's 100% algorithm with one repeating number:

3,7,4,14,3,16,6,15,12

TLDR for original question There will always be those numbers that fail. There is NO 100% winrate strategy for Alice. However, Alice can maximize her winrate by starting small and adding numbers to the ends of the algorithm. It'll only increase her chances by a bit, but hey, a bit is better than nothing.

Answer 7

I might be wrong but:

If we assume that Bob uses an optimal strategy, then that will actually give us information on the number he selects. Below are a few basic optimal strategies and their implications that I can think of.

If I were Bob then the best selection would be a prime number, as it is the only 100% guarantee that it will not be guessed on the first go. This informs us that the number is odd at this point. From here, however, Alice can assume that the number is odd.

This allows Alice:

To keep the number even by first asking an odd number, which is arbitrary but lets keep it low to maximise the number of guesses. So lets say 7 for instance (3 and 5 are useful). And then maintaining even guesses.

Alice then needs to:

Make the number divisible by 4. This can be done by using larger numbers to reduce the number. If we know that N is gerater than 100, it has to be divisible not by 4 on every other even number, meaning if we tried 32 first, and followed that up with 8. Then if it fails both times, the originial number was not divisible by 4. (I think I'm not 100% on this logic but I think it is correct don't be too harsh) This means that whatever N is now, it is not divisible by 4 but is even, so we try 6 and then 4 which should then work.

Attempted logical proof:

This took a lot of pages in my notebook, but:

Lets write N = 100 + y + z. (Where z is the arbitrary odd number we have removed from the equation in the first step). As we have decided one way to win is to force N to become divisible by 4. As 100 is divisible by 4 it makes the sum much easier. Trying to use 3 would fail because 100 is not divisible by 3. We are therefore trying to make y divisible by 4.

If new N is divisible by 32 then we have already won.

If not, then the new N=N-32 is also not div by 32. Otherwise N would have been originally. Therefore we know there exists an m between N-32 and N s.t. m is divisible by 32 although this is not that helpful. We then try 8 (being 32/4).

If N-32 is divisible by 8 then we have already won.

If not, N-40 is not divisible by 8. This can be written as N - (8*5) meaning N is not divisible by 8 (as we know for the same reason N-32 is not divisible by 32 anyway). This can be expanded to say that N - (4*10) is also not an integer, proving that N is not divisible by 4.

This tells us that if we assume an odd starting number, that N-40 is not now divisible by 4. We can therefore attempt 6 (2*3) to move across an even number and make sure that N is divisible by 4.

If N-40 is divisible by 6 then we win.

Otherwise, N-46 must be divisible by 4 as N-46 is even, every other even number is divisible by 4 and N-40 is not divisible by 4 (so N-42 is, N-44 is not and N-46 is). We have forced a victory and only subtracted 4 + 6 + 8 + 32 + 7 = 57 < 100 so we cannot go broke. It doesn't matter how large or small N is to start as even numbers repeat.

So:

It is possible assuming that Bob starts on a prime number to force a victory

However, this strategy relies on a prime (or just odd) number being chosen first, which is only optimal if Bob decides it is important to have a 100% success rate on the first question and goes with a prime number. Bob will therefore know not to start with a prime number every time. This could therefore end up very much like a game of chess.

If we take the optimum strategy as being to chose an even number every time (Being that this would confuse the oponent by not starting on a prime) Then the same steps work without the initial odd number. Although that relies on Alice calling Bob's bluff with regard to strategy.

I have yet to generalise this to work for any starting number. I need to discover whether it is odd or even somehow. I will think a bit more on it.