AI summary by TwinMind

Stones on an Infinite Chessboard - Numberphile

Numberphile

17m 5s

Puzzle Introduction

  • Stepping stones puzzle invented by two Michigan State undergraduates
  • Infinite chessboard with brown stones (worth 1 point each) and numbered white stones
  • Brown stones placed anywhere, white stones numbered 2,3,4,5,6... (one of each value)
  • White stone placement rule: can only place stone labeled n if sum of its 8 neighbors equals n
  • Must place white stones in sequential order (2, then 3, then 4, etc.)
  • Goal: determine maximum white stone value achievable with given number of brown stones

Two Brown Stones Example (n=2)

  • Starting configuration: two brown stones (value 1 each) placed adjacently
  • White stone 2: placed between brown stones (1+1=2)
  • White stone 3: placed adjacent to stone 2 and brown stone (2+1=3)
  • White stone 4: strategically placed to enable stone 5 placement
  • White stone 5: placed using neighbors 1 and 4 (1+4=5)
  • White stone 6: placed using neighbors 1,2,3 (1+2+3=6)
  • Continued placement through stones 7,8,9,10,11,12,13,14,15,16
  • Maximum achievable: 16 (proven optimal by original puzzle creators)

Known Results for Different Brown Stone Counts

  • n=1: maximum white stone = 1
  • n=2: maximum white stone = 16
  • n=3: maximum white stone = 28
  • n=4: maximum white stone = 38
  • n=5: maximum white stone = 49
  • n=6: maximum white stone = 60
  • n≥7: unknown (no one has computed these values)

Lower Bound Construction (Andrew Harroid's Method)

  • Zigzag pattern construction using n brown stones
  • Each additional brown stone enables 5 more white stone placements
  • Formula: achievable value ≥ 5n - 4
  • Examples:
    • n=2: 5(2)-4 = 6
    • n=3: 5(3)-4 = 11
  • Simple linear construction, not optimal but proves growth pattern

Upper Bound Analysis (Robert Kibbitz's Proof)

  • Mountain climbing analogy: brown stones as base huts, white stones as ascending steps
  • Key insight: to reach high value h, must have neighbor ≤ h/2
  • Recursive argument: neighbors of h/2 stone must include one ≤ h/4
  • After d steps from high point, must find stone with value ≤ h/2^d
  • Eventually reaches brown stone (value 1) within finite distance

Theoretical Upper Bound Calculation

  • Example using target value 65,000 (≈ 2^16)
  • Within radius 15 of any 65,000-value stone must be a brown stone
  • For 3 brown stones: three 31×31 squares around each brown stone
  • Total available squares: 3 × 31² = 2,883 squares
  • Need 65,000 sequential values (2 through 65,000) = 64,999 stones
  • Contradiction: insufficient squares to place required stones
  • General upper bound: 714n (where n = number of brown stones)
  • Proves finite maximum regardless of clever placement strategies

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome