Summary
Highlights
The session introduces advanced combinatorics, focusing on invariants and games. It also covers general problem-solving techniques, differentiating between showing existence (constructive vs. non-constructive) and non-existence, such as through invariants or paradoxes like the pigeonhole principle. Monovariants, which change predictably, are also introduced as a critical concept. Strategies for game theory problems are also discussed, emphasizing symmetrical strategies.
Invariants are quantities that do not change under a specific set of operations, making them useful for proving impossibility. The typical problem involves an initial state, a set of allowed moves, and a target final state. If an invariant quantity differs between the initial and target states, the target state is unreachable. The strategy involves defining an invariant quantity, verifying its constancy under all moves, and then comparing its value in the initial versus final states.
Several invariant problems are explored, starting with a five-pointed star where lamp states on intersections can be flipped along lines. The parity of activated lamps on the internal pentagon serves as an invariant, demonstrating why specific configurations are unattainable. Another example involves sequences of numbers where the sum of squares is an invariant, proving the impossibility of reaching certain target sequences. A 3x3 grid problem with number manipulation demonstrates the use of a checkerboard coloring invariant (sum of white cells minus sum of black cells) to prove impossibility.
This section examines coin pile problems on a number line, where players can move two coins by one position each, either closer or further apart. The invariant here is the sum of (position * number of coins) at that position, representing the center of mass. This invariant demonstrates that all coins can only be collected at a single point if certain divisibility conditions are met, such as the initial center of mass being divisible by the total number of coins. The discussion also touches upon variations, like weighted sums (2^n * coins) for different move types, and circular arrangements, introducing modulo arithmetic as a necessary invariant.
A problem from the Balkan Olympiad involves N people in a circle exchanging candies. Each person can either give one candy to a neighbor or divide their candies between their two neighbors. The question is whether all candies can be collected by a single person. The complexity arises from the freedom of choices. The invariant argument suggests that if moves are largely reversible, major invariants are unlikely. The critical insight involves understanding how combinations of moves effectively allow for shifting a single candy by two positions, impacting problem solvability differently based on whether N is odd or even. If N is odd, there are no significant invariants, and all candies can be collected; if N is even, a parity invariant might prevent this.
Mono-invariants are quantities that constantly increase or decrease with each move in a game, but always in a controlled manner (e.g., strictly positive or strictly negative changes). They are useful for proving that a process must eventually terminate, rather than proving impossibility. The Euclidean algorithm (GCD) is presented as an example, where the sum of the two numbers serves as a strictly decreasing mono-invariant, guaranteeing termination.
Another example involves a sequence of four non-negative integers (a, b, c, d) transformed into their absolute differences (|a-b|, |b-c|, |c-d|, |d-a|). The question is whether this process always leads to (0,0,0,0). The maximum value among the four numbers and the GCD of the four numbers are both relevant. While the maximum non-strictly decreases, the GCD non-strictly increases. A subtle analysis of parity (all numbers modulo 2) suggests that the GCD gains a factor of 2 every few moves, implying that eventually, the numbers must all become zero for the GCD not to exceed the maximum possible value.
This section discusses a problem from the International Mathematical Olympiad (IMO) involving N dwarves numbered 1 to N, standing in a queue. When dwarf 'i' is called, they move 'i' positions forward in the queue. The process stops if a dwarf cannot move the required number of steps. The problem asks to prove that the process always terminates and to determine the maximum number of moves. A mono-invariant, sharp in nature, like a weighted sum (e.g., sum of (2^position * dwarf_number) or more complex weighted sums of pairwise relative positions), can prove termination and estimate the number of moves. The example showcases that such quantities can predict the process ending and even quantify the maximum steps.
The discussion shifts to game theory, focusing on identifying winning strategies. The first game involves two players (Alberto and Barbara) removing tokens from a pile, where they can remove 1 to 2021 tokens. The player who takes the last token wins. Winning strategies are often found by classifying positions as 'winning' (W) or 'losing' (L). A position is W if there's a move to an L position; it's L if all moves lead to W positions. For this game, positions that are multiples of 2022 are losing positions, leading to a strategy of ensuring the opponent always starts from a multiple of 2022.
Another game involves placing congruent plates on a rectangular table. The player unable to place a plate loses. Alberto, playing first, can win by placing the first plate exactly at the center of the table. Subsequently, whenever Barbara places a plate, Alberto places his plate symmetrically opposite to Barbara's, maintaining a central symmetry. This guarantees Alberto always has a valid move as long as Barbara does, ensuring he wins. The key is that the initial central placement by Alberto preserves the central symmetry of available space.
A game where players write divisors of 10^10 on a board, with each new number having to be a divisor of the previous, and losing if a number already written is chosen. This game converts to a grid problem (11x11, based on prime factors 2 and 5 of 10^10). A 'block-matching' or pairing strategy helps identify the winner; if the table's dimensions allow for perfect pairing, the second player wins. However, if dimensions are odd (as in a 10x10 case for 10^10 divisors), the first player can choose the center and employ a symmetry strategy.
The final game involves Alberto moving a pawn on an infinite grid (8-directional movement) and Barbara placing walls (X's) on squares. Alberto cannot move into walled squares. The question is whether Barbara can trap Alberto within a rectangle. This is a complex problem, but a simplified lemma involves trapping Alberto in a semi-plane. Barbara's strategy involves placing walls strategically to restrict Alberto's movement. If Barbara can maintain a 'wall front' that shrinks faster than Alberto can cross, she can eventually trap him. A strategy of 'alternating X's' can efficiently reduce the potential movement area, proving Barbara can indeed trap Alberto.