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
