6. Problems that can be solved with the help of invariants скачать в хорошем качестве

6. Problems that can be solved with the help of invariants

In this video I solve six problems in real time (though I had done numbers 1, 3 and 4 before). They come from a book called Problem-Solving Strategies by Arthur Engel. I did this because I am interested in how people go about finding non-obvious ideas. The ideas needed for these problems are not all that hard, but you can't just look at the problem and see immediately what to do, and I'm interested in what exactly goes on when one searches for the key idea. The wording of the problems below is almost exactly as it is in the book. 0:00 Introduction 4:09 Q1. Start with the integers 1,2,...,4n-1. In one move you may replace any two integers by their difference. Prove that an even integer will be left after 4n-2 steps. 7:12 Q2. Start with the set {3, 4, 12}. In each step you may choose two of the numbers a, b and replace them by 0.6a - 0.8b and 0.8a + 0.6b. Can you reach the goal (a) or (b) in finitely many steps: (a) {4, 6, 12}, (b) {x, y, z} with |x - 4|, |y - 6|, |z - 12| each less than 1 over the square root of 3? 17:02 Q3. Assume an 8 x 8 chessboard with the usual coloring. You may repaint all square (a) of a row or column (b) of a 2 x 2 square. The goal is to attain just one black square. Can you reach the goal? 20:35 Q4. We start with the state (a, b) where a, b are positive integers. To this initial state we apply the following algorithm: while a does not equal b, do if a is less than b then (a, b) goes to (2a, b - a) else (a, b) goes to (a - b, 2b). For which starting positions does the algorithm stop? 33:57 Q5. Around a circle, 5 ones and 4 zeros are arranged in any order. Then between any two equal digits, you write 0 and between different digits 1. Finally, the original digits are wiped out. If this process is repeated indefinitely, you can never get 9 zeros. Generalize! 45:21 Q6. There are a white, b black, and c red chips on a table. In one step, you may choose two chips of different colors and replace them by a chip of the third color. If just one chip will remain at the end, its color will not depend on the evolution of the game. When can this final state be reached?