Invariants
This chapter shows how invariants can be used in combinatorial problems. First, we show some examples that go from purely combinatorial problems to geometric ones, and how invariants are used to solve each of them. Then, we present in depth how coloring t
- PDF / 367,309 Bytes
- 15 Pages / 477 x 684 pts Page_size
- 107 Downloads / 266 Views
Invariants
3.1
Definition and First Examples
Example 3.1.1 There are three piles with n tokens each. In every step we are allowed to choose two piles, take one token from each of those two piles and add a token to the third pile. Using these moves, is it possible to end up having only one token? Solution To the tokens in the first pile we can assign the pair (0, 1), to the tokens in the second pile the pair (1, 0) and to the tokens in the third pile the pair (1, 1). Notice that the sum modulo 2 of any two of these pairs give us the third one. Thus, in every step the sum modulo 2 of all the assigned pairs is the same. However, the sum of all the assigned pairs in the beginning is (2n, 2n), which is equal to (0, 0) modulo 2. Since this pair was not assigned to any pile, it is not possible to end up with only one token. In the previous example the strategy was to find a property that did not change in every step of the problem, and proving it could not be preserved in the end. When one deals with problems involving a transformation (such as taking off tokens in a certain way), a property that does not change under that transformation is called an invariant. Invariants can be extremely diverse, and there are numerous problems of international mathematical olympiads that can be solved by finding some very special invariant. When one is trying to solve olympiad problems (or any problem in mathematics), looking for invariants is a fundamental strategy. Example 3.1.2 Let n be a positive integer and consider the ordered list (1, 2, 3, . . . , n). In each step we are allowed to take two different numbers in the list and swap them. Is it possible to obtain the original list after exactly 2009 steps? Solution Suppose at some moment number 1 is in place a1 , number 2 is in place a2 , and so on. We are going to count the number T of pairs (x, y) such that x < y but ax > ay . In other words, we are counting the pairs of numbers that are not ordered. Suppose that in a step we swapped numbers a and b, and there were k numbers P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_3, © Springer Basel 2013
27
28
3
Invariants
between them. If the pair (a, b) was counted in T , now it is not and vice-versa. The same happens to the k pairs formed by a and any of the numbers between a and b and the k pairs of b with any of those numbers. So there are exactly 2k + 1 pairs changing from being counted in T or not being counted in T . This means that T changes by an odd number. Thus, after 2009 steps T must be odd. Since T cannot be 0 after 2009 steps, we cannot get the original order. These ideas are useful even in combinatorial geometry problems. Example 3.1.3 (IMO 2011) Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line l going through a single point P ∈ S. The line rotates clockwise about the pivot P until the first time that the line meets some other point belonging to S. This point, Q, takes o
Data Loading...
