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 it is the hard part.

  1. 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.

  2. MIT

    Passengers \(P_1, \dotsc, P_n\) enter a plane with \(n\) seats. Each passenger has a different assigned seat. The first passenger sits in the wrong seat. Thereafter, each passenger either sits in their seat if unoccupied or otherwise sits in a random unoccupied seat. What is the probability that the last passenger sits in their own seat?

  3. 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?

  4. 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?

  5. MIT

    Slips of paper with the numbers from 1 to 99 are placed in a hat. Five numbers are randomly drawn out of the hat one at a time (without replacement). What is the probability that the numbers are chosen in increasing order?

  6. 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 an orange, a white and a blue with an 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?

  7. 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?

  8. MIT

    How many \(8 \times 8\) matrices are there whose entries are exclusively zero and one and whose every row and column contains an odd number of ones?

  9. 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?

  10. 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?