Математические байки

Forwarded from Компьютерная математика Weekly (Grigory Merzon)

нравится сюжет Конвея про аналогию между играми и числами

например, игры (скажем, в которых роли противников симметричны, а проигрывает тот, кто не может сделать ход) можно складывать: в G+H играют на двух столах, на одном столе позиция в игре G, на другом — в игре H, каждый раз можно выбрать один из столов и сделать за ним ход

если в H выигрывает второй игрок, то результат у G+H такой же как и в G — это мотивирует объявить все выигрышные для второго игрока игры нулевыми

а вот игры, в которых выигрывает первый, бывают очень разными

если «ним-число» *n — это глуповатая игра «есть кучка из n камней, за ход можно взять любое количество камней из кучки», то *0 действительно нулевая игра, а все остальные *n — различные… и ненулевые )

и игра в четыре кучки камней *1+*3+*5+*7 уже не очень простая (не все персонажи фильма L'Année dernière à Marienbad справились), чтобы научиться в нее играть, хорошо бы изучить таблицу операций с ним-числами

вот такой, например, листок про это: https://dev.mccme.ru/~merzon/v14/pscache/5d-nim.pdf

написал код, который выписывает таблицы сложения и умножения для ним-чисел

def mex(N,arr):
    for a in range(N):
        if (a not in arr):
            return a
    return None

N = 2**(2**2)

t_sum = [list(range(N))]
for m in range(1,N):
    newline = []
    for i in range(N):
        # *m+*i = mex{*j+*i,*m+*i'|j<m,i'<i}
        arr = [line[i] for line in t_sum] + newline
        newline.append(mex(N,arr))
    t_sum.append(newline)
print(*t_sum,sep="\n")

t_mul = [[0]*N]
for m in range(1,N):
    newline = []
    for i in range(N):
        # *m.*i = mex{*j.(*i+*i')+*m.*i'|j<m,i'<i}
        arr = []
        for i1,mi1 in enumerate(newline):
            ii1 = t_sum[i][i1]
            for line in t_mul:
                jii1 = line[ii1] #*j.(*i+*i')
                arr.append(t_sum[jii1][mi1])
        newline.append(mex(N,arr))
    t_mul.append(newline)
print()
print(*t_mul,sep="\n")

можно заметить, а потом и доказать, что ним-сложение — это, на самом деле, просто побитовое сложение

а вот для ним-умножения настолько простого описания, кажется, нет

( определение — можно прочитать в https://en.wikipedia.org/wiki/Nimber#Multiplication )

но операция оч. хорошая — в частности, ним-числа, меньшие *(2^(2^k)), образуют конечное поле

www.group-telegram.com/sg/mathtabletalks.com/4724

2.2K viewsVictor Kleptsyn, Mar 19 at 15:53

нравится сюжет Конвея про аналогию между играми и числами

например, игры (скажем, в которых роли противников симметричны, а проигрывает тот, кто не может сделать ход) можно складывать: в G+H играют на двух столах, на одном столе позиция в игре G, на другом — в игре H, каждый раз можно выбрать один из столов и сделать за ним ход

если в H выигрывает второй игрок, то результат у G+H такой же как и в G — это мотивирует объявить все выигрышные для второго игрока игры нулевыми

а вот игры, в которых выигрывает первый, бывают очень разными

если «ним-число» *n — это глуповатая игра «есть кучка из n камней, за ход можно взять любое количество камней из кучки», то *0 действительно нулевая игра, а все остальные *n — различные… и ненулевые )

и игра в четыре кучки камней *1+*3+*5+*7 уже не очень простая (не все персонажи фильма L'Année dernière à Marienbad справились), чтобы научиться в нее играть, хорошо бы изучить таблицу операций с ним-числами

вот такой, например, листок про это: https://dev.mccme.ru/~merzon/v14/pscache/5d-nim.pdf

написал код, который выписывает таблицы сложения и умножения для ним-чисел

def mex(N,arr):
    for a in range(N):
        if (a not in arr):
            return a
    return None

N = 2**(2**2)

t_sum = [list(range(N))]
for m in range(1,N):
    newline = []
    for i in range(N):
        # *m+*i = mex{*j+*i,*m+*i'|j<m,i'<i}
        arr = [line[i] for line in t_sum] + newline
        newline.append(mex(N,arr))
    t_sum.append(newline)
print(*t_sum,sep="\n")

t_mul = [[0]*N]
for m in range(1,N):
    newline = []
    for i in range(N):
        # *m.*i = mex{*j.(*i+*i')+*m.*i'|j<m,i'<i}
        arr = []
        for i1,mi1 in enumerate(newline):
            ii1 = t_sum[i][i1]
            for line in t_mul:
                jii1 = line[ii1] #*j.(*i+*i')
                arr.append(t_sum[jii1][mi1])
        newline.append(mex(N,arr))
    t_mul.append(newline)
print()
print(*t_mul,sep="\n")

BY Математические байки