Invariants & Semi-Invariants

A truth can become easy to see if you just notice a simple invariant, a measurement or a property that doesn’t change. Noticing this invariant is the hard part.

  1. Jenia Tevelev

    We’re at a birthday party and it’s time to cut the cake! The cake has a square top and single candle directly in the middle, and guests, one after another, cut the cake in the following fashion: they choose two adjacent sides of the remaining cake and make a single cut through the interior of those sides, cutting away a wedge of cake. In a sense, they’re “cutting the corners” off the cake. Will any of the guests be able to get a piece with the candle?

  2. Jenia Tevelev

    Alice and Bob play a game where, taking turns, each of them puts a stone in one of the squares of an \(8 \times 8\) chessboard. A player loses if they create an “L”-shape of three stones. What is a winning strategy?

  3. Putnam and Beyond

    There are 2000 white balls in a box. There are also unlimited supplies of white, blue, and orange balls, initially outside the box. During each turn, we can replace two balls in the box with one or two balls as one of these actions: two whites with a blue, two oranges with a blue, two blues with a white and orange, a white and a blue with a orange, or a blue and orange with a white.

    1. After finitely many of the above actions there are three balls left in the box. Prove that at least one of them is blue.
    2. Is it possible that after finitely many actions only one ball is left in the box?

  4. Jenia Tevelev

    Alice and Bob play the following game. They start with 2012 points on the plane such that no three lie on a common line. Every two points are connected by a segment. They take turns, Alice marking any of the points with one of the digits \(0,\dotsc,9,\) and then Bob after her marking any of the segments with one of the digits \(0,\dotsc, 9.\) At some time during the game Alice will be out of moves, at which point Bob will just continue marking segments. Bob will win if in the end one of the segments is marked by the same digit as both of its endpoints. Who is going to win?

  5. Polya Seminar

    Let \(P_1, P_2, \dotsc, P_{2023}\) be distinct points in the plane. Connect the points with the line segments \(P_1P_2\) and \(P_2P_3\) and … and \(P_{2023}P_1\). Can you draw a single line that passes through the interior of every one of these line segments?

  6. Putnam and Beyond

    There is a heap of \(1001\) stones on a table. You are allowed to perform the following operation: you choose one of the heaps containing more than one stone, throw away a stone from the heap, then divide it into two smaller (not necessarily equal) heaps. Is it possible to reach a situation in which all the heaps on the table contain exactly three stones by performing the operation finitely many times?

  7. Putnam and Beyond

    Several positive integers are written on a blackboard. One can choose two distinct integers on the board, erase them, and in their place write their greatest common divisor (\(\mathrm{gcd}\)) and least common multiple (\(\mathrm{lcm}\)). Continuing this indefinitely, prove that eventually the numbers will stop changing.

  8. Putnam 2023 B1

    Consider an \(m\)-by-\(n\) grid of unit squares, indexed by \((i,j)\) with \(1 \leq i \leq m\) and \(1 \leq j \leq n.\) There are \((m-1)(n-1)\) coins, which are initially placed in the squares \((i,j)\) with \(1 \leq i \leq m-1\) and \(1 \leq j \leq n-1.\) If a coin occupies the square \((i,j)\) with \(i \leq m-1\) and \(j \leq n-1\) and the squares \((i+1,j), (i,j+1),\) and \((i+1,j+1)\) are unoccupied, then a legal move is to slide the coin from \((i,j)\) to \((i+1,j+1).\) How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?