Global AI and Data Science

Global AI & Data Science

Train, tune and distribute models with generative AI and machine learning capabilities

 View Only

A Counter Intuitive Game Result

By Moloy De posted Thu December 24, 2020 08:55 PM

  

The game goes as follows:

You are playing solitaire in the first quadrant of the Cartesian Plane. Your first move is to place a checker at the origin. On each turn, a legal move consists of removing one checker from the board and then placing two new checkers in the cells immediately above and to the right of the original checker. If either of those two cells is occupied, then the move is illegal, and a different checker must be selected for removal.

 

The challenge is to drive away all the checkers from the bottom left 3 by 3 squares.

Observations:

  1. After k moves there will be k checkers in the board
  2. If you put the weight 1/2k to a square where k is the Manhattan Distance (sum of the coordinates) of the square from the origin, then in any move the total weight remains to be one.
  3. The total of the distances of the checkers from origin is increasing as the distance of each checker from origin is non-decreasing.
  4. It is impossible to drive away all the checkers from the bottom left 3 by 3 squares. For a proof see the blog by Lipton and Regan.

QUESTION I: What is the minimum number of moves required to drive away all the checkers from bottom left 2 by 2 squares?

QUESTION II: Is there an inherent feature of a state that breaks down if we assume there is no checker in the bottom left 3 by 3 squares?

Merry Christmas and Happy New Year


#GlobalAIandDataScience
#GlobalDataScience
0 comments
3 views

Permalink