Transcript Transfinite Chomp

Transfinite Chomp
Scott Huddleston and
Jerry Shurman
Presented by Ehren Winterhof
Chomp
Invented by David Gale, 1974
 Non-partisan combinatorial
 Played on ℕd for d in ℤ+
 A move consists of choosing a lattice point
in the position and removing it along with
all points outward
 Transfinite chomp uses ordinals for
notation

Ordinals
Ordinals Ω extend Natural Numbers ℕ to
include infinite numbers
 Totally ordered (mex, sup)
 ⊎, ⋆ (not commutative)
 Smallest infinite number is ω (little omega)
 In ascending order: ω, ω⊎1, ω⊎2, …, ω⋆2,
ω⋆2⊎1, …, ω⋆3, …, ω2, ω2 ⊎1, …, ω2⋆2,
ω3, …, ωω …

Chomp Notation
Each ordinal a is the set of all ordinals less
than a. ie. 5 = { 0 1 2 3 4 }
 A rectangular game is written as a x b


5x3={01234}x{012}
A bite from a two dimensional game is
⌐(a b) = ⌐a x ⌐b = { y | y ≥ a } x { z | z ≥ b
}
 Notation extends to any number of
dimensions

Chomp Size






Every Chomp position X has ordinal size, size(X)
Decompose position into finite, overlapping sum
of boxes S
Each component box has each side length ωe,
for non-negative integer e
Discard any box contained within another to
form S’
If Y is reachable from X, size(Y) < size(X)
Chomp terminates after finitely many moves
Size Example
Size (X) = Size (S’) = ω *3 + 1
Grundy Values
G(X) = mex{G(Y) : Y is reachable from X }
 Poison Cookie has Grundy value 1
 P-Positions have Grundy value 1 because
they are reversible


P-positions typically have value 0, but
unrestricted misere Chomp is “tame”
Extension
Two Chomp Positions A and B of
dimension d and d-1, (with 1 < d < ω)
 Ordinal h
 E(A, B, h) = A + (B x Ω) - ⌐(0,…,0,h)
 A plus an infinite “column” of B, truncated
to height h in the last direction
 “Extension of A by B to height h

Fundamental Theorem
For any A and B, there is a unique ordinal
h such that E(A, B, h) is a P position
 Uniqueness is easy given existence
 Existence requires complicated doubleinduction
 h is tricky to calculate, but if you choose B
to be the d-1 dimension poison square, h
is bounded by size(A – (B x Ω))

Consequences

Assuming we can find h, such that E(A, B,
h) is a P-position, we can:
Find the Grundy Value of a position
 Construct positions of arbitrary Grundy value


For finite A and ordinal h, G(A + (1d-1 x h))
has the same highest term as h.
(General Beanstalk Lemma)
P-Ordered Positions

A Chomp Position is P-Ordered if its P
subpositions are totally ordered by
inclusion
2xω
 { (1 x (i+1) + (2 x i) : 0 ≤ I < ω }
 { (1 x a) + (a x 1) : 0 < a }


If P is a P ordered Chomp Position, then
G(X x P) = G(X)
Two-Wide Chomp

Two Columns h, k of ordinal height
h = ωi * u + a
 k = ωj * v + b

If h and k differ by a factor of ω, by an
extension of the beanstalk lemma, the
Grundy value is infinite
 Limiting examination to i=j and u=v we get
the following

Finite Two Wide Grundy Values
If columns are of finite heights u, v
If i = j = 1, and u = v
More Two Wide Grundies
When 2 < i = j < ω, and u = v
When i = j < ω and u > v
When ω ≤ i = j
Question

In the sum of these three 2-wide Chomp
positions, what is the winning move that
reduces the game size the most?
A. (ω * 2 + 3) x 2
 B. (ω4 * 6 + 26) , (ω4 * 6 + 10)
 C. (ω3 * 10 + 36), (ω3 * 4 + 15)

Other Topics Covered
but omitted here
Side – Top Theorem
 N and P analysis of 3 wide chomp



ωω x 3 is a P Position
Open Questions