Another Sticky Problem

The game presented by a Java applet below was published in 2004 the Mathematics Magazine as problem #1687 (Sung Soo Kim). A solution by Li Zhou appeared in v. 78, n. 1 (February, 2005), p. 70.

A two-player game starts with two sticks, one of length N and one of length N+1, where n is a positive integer. Players alternate turns. A turn consists of breaking a stick into two sticks of positive integer lengths, or removing k sticks of length k for some positive integer k. The player who makes the last move wins. Which player can force a win, and how?

The applet allows for experimentation with different starting lengths. At the outset, you can force the computer to make the first move by pressing the "Make move" button. Sticks are represented by a row of small squares that might remind of a chocolate brick. To break a piece click on a square to the right of the desired break line.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

Strategy

|Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Let A be the set of positions with an even number of sticks and at most one stick of even length. Let B be the set of game positions with an odd number of sticks and at most two sticks of even length. Note that the initial and final game positions are in A. It is also evident that any move from an A-position results in a B-position and that from each B-position a move can be made that results in an A-position. Thus the second player can force a win by always making a move that puts the game into an A-position.


Related material
Read more...

  • What Is a Combinatorial Game?
  • A Game of Candy Squares
  • A Sticky Problem
  • Date Game
  • Dawson's Chess: an Interactive Gizmo
  • Dawson's Kayles: an Interactive Gizmo
  • Grundy's Game
  • Hex 7
  • Kayles
  • Nimble: an Interactive Gizmo
  • Northcott's game (An Interactive Gizmo)
  • Odd Scoring
  • One Pile: an Interactive Gizmo
  • Plainim (An Interactive Gizmo)
  • Plainim Misere (An Interactive Gizmo)
  • Scoring: the simplest of the impartial games
  • Scoring Misere: an Interactive Gizmo
  • Scoring Misere: Two Heaps Perfect Strategy
  • The Fraction Game
  • The Silver Dollar Game
  • Silver Dollar Game With No Silver Dollar
  • Subtraction Game
  • TacTix: an Interactive Gizmo
  • Turning Turtles
  • Take-Away Games
  • Wythoff's Nim, Literal Implementation
  • Wythoff's Nim (An Interactive Gizmo)
  • |Contents|

    Copyright © 1996-2018 Alexander Bogomolny

    71493220