35
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What happens if Bob picks 100 and Alice picks 99? Bob will have N = 1 and Alice can't guess lower than 3. $\endgroup$ – Zikato Mar 10 '15 at 8:53
  • 2
    $\begingroup$ whatever Alice guesses, that will be subtracted from 1 and it will give negative answer and Bob wins $\endgroup$ – user9174 Mar 10 '15 at 8:56
  • 1
    $\begingroup$ A few observations: Alice's stategy consists in a list of numbers (Since the only in-game information alice obtains is whether she has won). All we have to do is use CRT to build a number $N$ that doesn't work for any given sequence. (Notice we only have to consider sequences with sum $N-2$ or less. Clarification: We don't have to build a number that doesn't work for any sequence, for every sequence we have to build a number. $\endgroup$ – Jorge Fernández Mar 10 '15 at 14:34
  • $\begingroup$ @Zikato that would be a loss for Alice. no matter what she guesses (5 for example), she gets a loss at -4. $\endgroup$ – user3453281 Mar 10 '15 at 14:42
  • 1
    $\begingroup$ Alice could have won if x=2 was allowed. The restriction x>=3 makes me feel that she is not going to be able to win. $\endgroup$ – Raziman T V Mar 10 '15 at 20:22
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice one. I tried with 120 and could not find anything. Got one with 144 though, but the limit was way higher than 203. $\endgroup$ – Raziman T V Mar 11 '15 at 13:14
  • 2
    $\begingroup$ While interesting, this doesn't seem to answer the question. If Bob knows this (and he should), he can just pick 202, and Alice loses. Unless there is a single sequence that covers everything n>=100, the answer should be "no" (or at least "probably not, but unproven yet"). $\endgroup$ – Set Big O Mar 11 '15 at 13:15
  • 3
    $\begingroup$ I know that. This is partial progress. Perhaps you can adapt this strategy to make the bound 202 lower. Also, this post may be a good counter to debunk bad 'proofs' that Alice can never force a win. $\endgroup$ – Lopsy Mar 11 '15 at 13:23
  • $\begingroup$ Nice. Did your program verify that this is the optimal way to cover Erdos's residue classes? $\endgroup$ – Julian Rosen Mar 11 '15 at 16:50
  • 2
    $\begingroup$ For anyone curious the only numbers that don't seem to work for are 154 and 202. $\endgroup$ – kaine Mar 11 '15 at 19:25
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Does not work if Bob chooses 191. $\endgroup$ – Raziman T V Mar 11 '15 at 0:03
  • $\begingroup$ @crazyiman Yeah, I realized I made a mistake. I think my strategy will work, but I haven't gone through using the right numbers yet. $\endgroup$ – Rob Watts Mar 11 '15 at 1:48
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think this argument is correct. If Bob's limit was 10000 instead of 100, there exists a sequence of numbers that guarantees a win for Alice. I think your mistake is multiplying 2/3 * 3/4 …. By smartly picking the numbers, you can do better than that. $\endgroup$ – Raziman T V Mar 11 '15 at 12:16
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the number N is gurantee to be non-prime number, could you figure out a 100% algorithm? $\endgroup$ – Alex Mar 10 '15 at 21:35
  • $\begingroup$ Uh.... I'd have to do a lot more calculations... I can't confirm without further testing. $\endgroup$ – Aify Mar 10 '15 at 21:37
  • 1
    $\begingroup$ If 3 can repeat, 3,7,3,13,6,15,4,18,12 is a 100% win strategy. Also, your explanation works even when x=2 is allowed - but there is a 100% win strategy without repetition if 2 is allowed. So your explanation does not work. $\endgroup$ – Raziman T V Mar 10 '15 at 21:37
  • $\begingroup$ @crazyiman My explanation doesn't take into account x = 2. The question explicitly says Alice can only guess 3 or higher. The question also says no repeats, the repeating part in my question is extra and irrelevant to my actual answer. If you can find a no repeating, 3+ strategy that is 100% come back and tell me. $\endgroup$ – Aify Mar 10 '15 at 21:39
  • 3
    $\begingroup$ I would not be surprised if there was a solution. Although you are pretty convinced there isn't. I would say that your arguments are not sufficient proof. And if you're right the next question would be: what strategy has the best win chance? $\endgroup$ – Ivo Beckers Mar 10 '15 at 23:17
-2
$\begingroup$

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     -       -       -       -       -
$\endgroup$
  • 2
    $\begingroup$ Every number can be picked at most once. So as far as I understand the question, you can't repeat 3 or 4. $\endgroup$ – EagleV_Attnam Mar 10 '15 at 9:19
  • $\begingroup$ I did not read this. Did he ninja-edit his post? However, this nullifies my answer. $\endgroup$ – Nephtyz Mar 10 '15 at 9:22
  • $\begingroup$ Nope, that condition was there from the start. $\endgroup$ – Zikato Mar 10 '15 at 9:36
-2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ hate to disprove you but your strategy doesn't work for example with 139. 139 is prime (so not divisble by 7). 132 is not divisble by 32. 100 is not divisble by 8. 92 is not divisble by 6. 86 is not divisble by 4 $\endgroup$ – Ivo Beckers Mar 10 '15 at 18:34
  • $\begingroup$ BTW, 139 is the lowest prime it doesn't work for. 115 is the lowest odd number it doesn't work for. $\endgroup$ – Ivo Beckers Mar 10 '15 at 18:38
  • 3
    $\begingroup$ Can you really depend on Bob's behavior like this? For all you know, he has done the exact same analysis you have, and so he will pick a number that works best against Alice's strategy. A working strategy for Alice will have to win against every integer $\geq$ 100. $\endgroup$ – Lopsy Mar 10 '15 at 18:46
  • $\begingroup$ I already said that Lopsy. It was one scenario. I was trying to find any possible scenario because I initially thought it was impossible. Is worth trying, might have had someone come in with some advice/alterations $\endgroup$ – Ryan Durrant Mar 10 '15 at 19:47
  • $\begingroup$ If you assume N is odd, then N=2M+1 for integer M. If you can create a situation where either you win, or M is not an integer, you can continue under the assumption that N is even. Then you repeat the process. $\endgroup$ – freekvd Mar 10 '15 at 19:48

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.