Walking on thin ice

If both players play optimally: A winning number is a number that if chosen, will guarantee a win. A losing number is a number if chosen, will guarantee a loss.

I solved this manually using a spreadsheet. I was then inspired to write the algorithm as a Python code to calculate the winning numbers for the first $n$ positive integers.

To check whether a number $a$ is winning or losing, all perfect squares less than $a$ are subtracted from $a$ one at a time. This gives all the possible outcomes for the second player. If all possible outcomes are winning numbers, then the second player has won. Otherwise, the first player wins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# append function is defined that appends b
# to list a only if it is not already present in a
def append(a, b):
    if b not in a:
        a.append(b)
    return a

def game(n):
    wl = [] # winning list
    ll = [] # losing list
    sl = [] # square list

# adds all perfect square numbers less than n to sl
    x = 1
    while x <= n:
        if x**(0.5) % 1 == 0:
            append(sl, x)
        x += 1

    a = 1
    while a <= n:
        if a in sl:
            append(wl, a)
        else:
            ssl = []  # subtracted square list
            for i in sl:
                append(ssl, a - i)

# ssl with only positive terms retained
            pssl = [item for item in ssl if item >= 0] 

# counts  how many losing numbers in pssl
            m = 0
            for c in pssl:
                if c in ll:
                    m = m + 1

# if there are no losing numbers, then a is a losing number.                    
            if m == 0:
                append(ll, a)
# otherwise a is a winning number
            else:
                append(wl, a)

        a += 1
    return wl

print(game(50))
print(len(game(50)))

Output : [1, 3, 4, 6, 8, 9, 11, 13, 14, 16, 18, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50] 38

Answer: $\boxed{38}$

I did this, manually, i.e number by number. Took less than 18 minutes.