Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Chomp - Square and Thin

      1 March, 2001
      4 comments
      March 2001

      Square Chomp

      How can the first player (Player A) of a game of Square Chomp guarantee to win? Simple. The first move is to chomp all the cookies except those along the left and bottom edges.

      If the second player (Player B) now chomps the poisoned cookie, she has lost, so we can assume she doesn't. So she must chomp either some cookies along the left edge, starting from the top, or some cookies along the bottom edge, starting from the right side.

      Player A should then chomp the "symmetric cookies" - the matching cookies along the bottom edge if Player B chomped some on the left edge, and vice versa.

      At each stage, either Player B will chomp the poisoned cookie, or she can only take cookies from the left edge or bottom edge, but not both. So at each stage Player A can reply by taking the "symmetric cookies", until only the poisoned cookie is left, which Player B has to eat.

      Thin Chomp

      The analysis of Thin Chomp is a little more complicated, but not much. Clearly Player A can win Chomp played on the shortest possible "Thin Grid" - a grid of just 2 cookies. We will use a recursive argument - showing that if Player A can win Chomp played on all Thin Grids 1,..,n-1 cookies long, then she can win on a Grid n cookies long.

      On a Thin Grid n cookies long, Player A should start by taking just the top righthand cookie.

      If Player B now chomps any cookie from the bottom row, she has transformed the game into Chomp played on a shorter Thin Grid, and Player A can win. So we can assume she doesn't take any cookies from the bottom row.

      If she chomps all the cookies from the top row, then Player A can chomp all the cookies left except the poisoned one, and again Player B loses.

      So we can assume that Player B chomps some but not all of the cookies in the top row. This means there are at least two more cookies left in the bottom row than in the top row.

      Player A should now chomp only cookies from the bottom row, leaving exactly one more cookie in the bottom row than are left in the top.

      Then Player B's move can be analysed in exactly the same way as for her first move, and we come to the conclusion that if she is not to lose, she will have to chomp some but not all of the cookies in the top row. But there are only finitely many cookies in the top row, so eventually this won't be possible, and Player B will lose.

      Back to main Mystery Mix page

      • Log in or register to post comments

      Comments

      Anonymous

      11 November 2010

      Permalink

      So, how can the first player (Player A) of a game of ( 4x7 ) Chomp guarantee to win ?

      • Log in or register to post comments

      Anonymous

      19 January 2011

      In reply to So, how can the first player by Anonymous

      Permalink

      Im in AP Comp Sci and we have this game but on a 4x7 grid and I cannot figure out how to win. Any suggestions?? PLEASE???

      • Log in or register to post comments

      Anonymous

      20 January 2011

      In reply to ARRRGG by Anonymous

      Permalink

      I'm in ap comp sci too and I know you go to the same school as me, mere child. I have won twice and I have no idea what I was doing. I got it like this on my turn:
      X o _ _ _ _ _
      o o _ _ _ _ _
      _ _ _ _ _ _ _
      _ _ _ _ _ _ _

      I clicked on the south east O and in two turns I won.

      • Log in or register to post comments

      Anonymous

      29 October 2014

      In reply to ARRRGG by Anonymous

      Permalink

      It extremely difficult to win against the computer. I did it, but that was after I ran the computer against itself and then copied its exact moves. There are certain situations that guarantee a win and you basically have to figure out all of them. The computer I played against used this list of winning positions:
      private static int winPositions[][] =
      {
      {1},
      {7,6}, {6,5}, {5,4}, {4,3}, {3,2}, {2,1},
      {7,7,4}, {7,5,2}, {6,4,2}, {4,2,2},
      {7,4,3}, {6,3,3}, {5,5,3},
      {4,1,1,1}, {3,1,1},
      {2,2,2,1},
      {2,2,1}, {3,3,1,1},
      {5,2,1,1},
      };
      //Each array is number of squares in row 0, 1, 2, 3 (a missing element is 0)

      • Log in or register to post comments

      Read more about...

      xfile
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms