Does there exist a non-zero game such that the sum of three or more copies of it is zero?
In combinatorial game theory, there are non-zero games $G$ with the property $G+G=0$; this is in particular true for all impartial games.
Now I wonder if there also exist non-zero games such that $G+G+G=0$. I don't see an obvious reason why those shouldn't exist, but I also have no idea on how to construct such a game.
Such a game obviously has to be a fuzzy game, as the sum of two positive games is positive, and the sum of two negative games is negative. Also, clearly $G\ne -G$, or else $G+G+G = G+(-G)+G = G \ne 0$. But beyond that, I'm out of ideas.
It would also be interesting for larger numbers than three. If for $n\in\mathbb N$ we define $nG$ as the sum of $n$ copies of $G$, for which (if any) $n>2$ does there exist a game such that $nG=0$, but $mG\ne 0$ for $0<m<n$?
1 answer
Yes: there are indeed fuzzy games for which $nG=0$ but $2G≠0$.
The game $G := \{1|*-1\}$, found by r~~ as the result of a related inquiry, is an example. $2G$ is not 0 (as r~~ shows in the linked answer); but $4G$ is 0.
Unfortunately I don't have an elegant proof that $4G = 0$.[1]
It remains an interesting problem to find games such that $nG=0$ but $mG≠0$ for $m < n$ and $n$ not equal to a power of two.
Old answer
Brute-force computer search on the 1029 games of birthday ≤ 2 finds no nonzero games $G$ such that $G+G+G=0$.
I wasn't very surprised by this result. What was surprising is that $G+G$ is never fuzzy for any of those games!
(By the way $\{1 | 0\}$ is a useful example of a fuzzy $G$ with non-fuzzy $G+G$.)
As you can see in the code below, I filtered the 1029 games of birthday ≤ 2 for the 785 nonzero fuzzy games (testgames1). Then I computed $G+G$ for each of those 785 games to make sure that $G+G≠0$ as desired by the OP; 456 games resulted (testgames2). But exactly half of those games were positive and exactly half negative!
Here's my code (in Guile Scheme) and results (in the assertions, all of which succeed):
;;; cgt
;; preliminary defs
(use-modules (ice-9 control))
(use-modules (unit-test))
(use-modules (ice-9 match))
(define-syntax mλ (λ (x) (syntax-case x () ((mλ x ...) #`(match-lambda* x ...)))))
(define-syntax amap (lambda (x) (syntax-case x () ((_ f body ...) #`(map (lambda (#,(datum->syntax x 'it)) f) body ...)))))
(define (amb . ls) (shift x (apply append (map x ls))))
;; game = (left-moves right-moves)
(define games
(λ (n)
(if (zero? n) '((() ()))
(if (>= n 1) (append (games (- n 1)) (reset (list (amap (apply append (amap (amb '() (list it)) (games (- n 1)))) '(0 1)))))))))
(define 2games (games 2))
(assert-equal (length 2games) 1029)
;; in this we use somewhat different notation: when Right chooses a game, we flip the game---this allows easier symmetry checking
;; edit: we no longer use this notation
(define (any? ? l) (∧ (pair? l) (∨ (? (car l)) (any? ? (cdr l)))))
;(match-define (flip (x y)) `(,y ,x))
(define (moves game left?)
(define pos (if left? 0 1))
(define moves (list-ref game pos))
moves)
(define (wins? game left?)
(define pos (if left? 0 1))
(define moves (list-ref game pos))
(∧ (pair? moves) (any? (λ (game) (¬ (wins? game (¬ left?)))) moves)))
(assert-equal (wins? '(() ((() ()))) #f) #t)
(assert-equal (wins? '(() ((() ()))) #t) #f)
(define gamesum
(mλ (() '(() ()))
((g1) g1)
((g1 g2) (map (λ (left?) (append (amap (gamesum it g2) (moves g1 left?)) (amap (gamesum g1 it) (moves g2 left?)))) '(#t #f)))
((g1 . gs) (fold gamesum g1 gs))))
(assert-equal #t (wins? (gamesum '(((() ())) ()) '(((() ())) ())) #t))
(assert-equal #f (wins? (gamesum '(((() ())) ()) '(((() ())) ())) #f))
(assert-equal #f (wins? (gamesum '(((() ())) ()) '(() ((() ())))) #t))
(assert-equal #f (wins? (gamesum '(((() ())) ()) '(() ((() ())))) #f))
(define testgames1 (filter (λ (game) (∧ (wins? game #t) (wins? game #f))) (games 2)))
(assert-equal 785 (length testgames1))
(define testgames2 (filter (λ (game) (∨ (wins? (gamesum game game) #t) (wins? (gamesum game game) #f))) testgames1)) ; games $G$ such that $G+G≠0$
(assert-equal 456 (length testgames2))
(define testgames2l (filter (λ (game) (∧ (wins? (gamesum game game) #t) (¬ (wins? (gamesum game game) #f)))) testgames1)) ; games $G$ such that L wins $G+G$
(define testgames2r (filter (λ (game) (∧ (¬ (wins? (gamesum game game) #t)) (wins? (gamesum game game) #f))) testgames1)) ; games $G$ such that R wins $G+G$
(assert-equal (/ 456 2) (length testgames2l))
(assert-equal (/ 456 2) (length testgames2r))
-
(Applying the domination axiom[1:1] did not much simplify the game $2G$, and so I used brute-force. I have not implemented the reversibility axiom in code. For these axioms see e.g. Larsson's notes, pp. 15–16.) ↩︎ ↩︎
0 comment threads
0 comment threads