2
$\begingroup$

Alice and Bob play a game, taking turns. Alice starts and writes an integer between 1 to 10 on a blackboard. Then Bob adds any integer between 1 to 10 to this number and writes it on the blackboard. When a three digit number is reached the game ends. During the game the number of positive divisors of each integer written down by Alice are added up, the same applies for Bob. If Alice has more divisors at the end she wins, otherwise Bob wins. The divisors of the three digit number are not counted.

Is there a winning strategy for any of the players?

Example:
Alice 4 20 30 40 53 58 70 82 92 99 (number of divisors: 3+6+8+8+2+4+8+4+6+6=55)
Bob 12 22 31 48 57 68 75 88 96 100 (number of divisors: 6+4+2+10+4+6+6+8+12=58)
and Bob is the winner in this case.

$\endgroup$

1 Answer 1

3
$\begingroup$

After recalculating the table I believe that there is a winning strategy for A, as follows:

If D(i) is the number of divisors of i, and C(i) is the relative benefit of moving to i then C(i) = 0 for i >= 100 and C(i) = D(i) - Max(C(i+1), C(i+2),...C(i+10)) for 1 <= i <= 99. You can use this to move backwards down the list of numbers from 99 to 1, calculating C(i) at each step. Because A moves first they have a choice if 'starting' at any i between 1 and 10. The table of C(i) below confirms that A can win by moving to 1.

A chooses 1 first and ends up winning by 1 point.

See Tables below showing the way an optimal game could progress. Spoiler space added as I cant work out how to hide a table.

enter image description here

An optimal game would progress as follows (Asc and Bsc are the scores for A and B after each move):

    Mov Pl. Num Sum Asc BSc
    1   A   1   1   1   0
    2   B   9   10  1   4
    3   A   2   12  7   4
    4   B   1   13  7   6
    5   A   7   20  13  6
    6   B   4   24  13  14
    7   A   6   30  21  14
    8   B   6   36  21  23
    9   A   6   42  29  23
    10  B   7   49  29  26
    11  A   7   56  37  26
    12  B   4   60  37  38
    13  A   1   61  39  38
    14  B   9   70  39  46
    15  A   2   72  51  46
    16  B   8   80  51  56
    17  A   10  90  63  56
    18  B   9   99  63  62

The above was calculated using the following table showing the relative advantage in moving to any specific position (calculated using the algorithm described above).

Sum Div Adv
1   1   1
2   2   -2
3   2   -2
4   3   -1
5   2   -2
6   4   0
7   2   -2
8   4   0
9   3   -1
10  4   0
11  2   -2
12  6   4
13  2   2
14  4   -2
15  4   -2
16  5   -1
17  2   -4
18  6   0
19  2   -4
20  6   0
21  4   -2
22  4   -2
23  2   -4
24  8   6
25  3   1
26  4   -2
27  4   -2
28  6   0
29  2   -4
30  8   2
31  2   -4
32  6   0
33  4   -2
34  4   -2
35  4   -2
36  9   6
37  2   -1
38  4   -1
39  4   -1
40  8   3
41  2   -3
42  8   3
43  2   -3
44  6   1
45  6   1
46  4   -1
47  2   -3
48  10  5
49  3   5
50  6   -4
51  4   -6
52  6   -4
53  2   -8
54  8   -2
55  4   -6
56  8   -2
57  4   -6
58  4   -6
59  2   -8
60  12  10
61  2   2
62  4   -4
63  6   -2
64  7   -1
65  4   -4
66  8   0
67  2   -6
68  6   -2
69  4   -4
70  8   0
71  2   -6
72  12  8
73  2   -2
74  4   -2
75  6   0
76  6   0
77  4   -2
78  8   2
79  2   -4
80  10  4
81  5   -1
82  4   -2
83  2   -4
84  12  6
85  4   -2
86  4   -2
87  4   -2
88  8   2
89  2   -4
90  12  6
91  4   -2
92  6   0
93  4   -2
94  4   -2
95  4   -2
96  12  6
97  2   -4
98  6   0
99  6   6
$\endgroup$
3
  • $\begingroup$ The advantage in 38 should be -1 instead of 1 since the opponent can go to 48 afterwards. Also the score of A from N=60 should be +4 (N=60 should have A=44), so A wins by 2. This should be the case as the advantage of N=1 is 2. So A should win by 2. $\endgroup$
    – justhalf
    Commented Jun 1, 2021 at 10:02
  • $\begingroup$ @justhalf I had also made a mistake in the table calculation. Corrected table still shows A winning, but now only by 1. $\endgroup$
    – Penguino
    Commented Jun 1, 2021 at 23:16
  • $\begingroup$ Eh? I tried yesterday following your table construction logic and got to the same advantage (2), but I guess I made the same mistake then, haha. $\endgroup$
    – justhalf
    Commented Jun 2, 2021 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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