Prerequisite: Division with remainder
Recall that
Definition (parity)
An integer number is said to be even if it is divisible by
, and odd otherwise.
Following the division with remainder theorem, we can write any integer number
So, alternatively,
Definition (parity)
An integer number is called even if
such that , and odd if such that .
We will use the concept of parity to highlight the notion of invariants in mathematics. An invariant is a parameter of the problem that is independent on the problem setting.
Example
On a
board checkers such that their position is symmetric with respect to the (bottom-left to top-right) diagonal of the board. Prove that at least one of the checkers is on the diagonal. Any checker that is not on the diagonal forces another checker in the symmetric position. In other words, putting a checker outside the diagonal does not change the parity of the total number of checkers as we are forced to add the symmetric one. However, we want to put an odd number of checkers. Therefore, at least one checker has to be on the diagonal.
Example
chips are placed in a row. It is allowed to swap two chips that have exactly one chip between them. Is it possible to reverse the order of all the chips using such operations? Number the chips based on their position by a number from
to . Reversing the order would require to change the parity of the position of every chip ( has to go to position , goes to , and, in general, goes to position , and the numbers and have different parity (prove!). But the allowed operation does not change the parity of the position number of the chip. Therefore, it is impossible to reverse the order of the chips.
Question to ponder
Does there exist a closed curve with no self-intersections on the plane such that it intersects the unit circle exactly
times? If it exists, how would you construct it? If it does not exist, why? You will not be able to produce a rigorous solution, but try to reason using intuition.
Problem 1
Problems.ru 104025
Misha wrote 2004 plus signs and 2005 minus signs on the board in some order. From time to time, Yura approaches the board, erases any two signs, and writes one sign instead: if he erased two identical signs, he writes a plus, and if he erased two different signs, he writes a minus. After several such actions, only one sign remains on the board. What is it?
Link to original
Problem 2
Работа в школе - ЗдчИнварианты2 - 4
The numbers
Link to originalare written on the board. In one move, you can erase two numbers and write their difference instead. Leonid did this for three days and three nights and ended up with 0. Prove that he got a bit tired and made a mistake somewhere.