TGViewer
Математические байки Математические байки @mathtabletalks · 4.29K subscribers
Post #4724 3.65K

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)), образуют конечное поле
More from @mathtabletalks
  1. Sep 15, 2026к сегодняшнему 100-летию Серра — его свежее интервью от группы Бурбаки в 40-х годах до «I…
  2. Sep 15, 202615 сентября столетний юбилей отмечает французский математик Жан-Пьер Серр. Поздравляем юби…
  3. Sep 15, 2026youtube.com/watch?v=Px71N0DvoCA
  4. Aug 12, 2026До начала затмения остаётся всего несколько часов, так что на всякий случай напомню: и без…
  5. Aug 6, 2026Король приготовил N мудрецам испытание: каждому назначено целое число от 1 до N+1, все наз…
  6. Jul 28, 2026www.mathnet.ru/php/conference.phtml?eventID=27&confid=2780&option_lang=rus&if_videolibrary…
Threads Profile ViewerView any public Threads profile without an account.Open ThreadLook →Writing with AI? Make it sound human.Metric37 rewrites AI drafts so they read naturally. Free AI detector, 1,500 words free.Try Metric37 →