Combinatorics, Invariants
An invariant is a property of a system or mathematical object that remains unchanged when transformations or operations are applied. Identifying an invariant can be key to solving problems about processes or proving impossibility. Questions involve finding such constant quantities or properties.
-
Question
On the circle, there are blue and red points. It is allowed to add a red point and change the colors of its neighboring points or remove a red point and change the colors of its neighboring points (it is not allowed to leave fewer than 2 points on the circle). Prove that it is impossible to move, using only these operations, from a circle with two red points to a circle with two blue points.
K. KaznvoskySources:Topics:Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Algebra Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings -> Chessboard Coloring- Tournament of Towns, 1979-1980, Main, Spring Question 1
-
Wolf and sheep
The game takes place on an infinite plane. One player moves the wolf, and the other – 50 sheep. After a move by the wolf, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or sheep moves no more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial configuration?
Sources:Topics:Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Game Theory Proof and Example -> Constructing an Example / Counterexample- Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 5 Points 16
-
The Knight and the Dragon
A knight encountered a dragon with three heads on his way and they began to fight. Every time the knight chops off one of the dragon's heads, three new heads appear in its place. Is it possible that at the end of the battle, the dragon will have a thousand heads?
Topics:Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) -
Ali Baba and the Forty Thieves
Ali Baba wrote the number `17` on a piece of paper. The forty thieves pass the paper to each other, and each one either adds `1` to the existing number, or subtracts `1`, until each of them has done so once, and then they return the paper to Ali Baba.
Is it possible that the number now written on the paper is `40`?
Sources: -
Playing with Chocolate
Yossi and Danny are playing the following game. They have a chocolate bar of size `5xx7` squares, which is placed on a table. Each player, in turn, breaks one of the pieces of chocolate on the table along a straight line and returns the resulting pieces to the table. That is, in the first turn, the original chocolate bar is broken, and in the following turns, one piece is chosen from the pieces created up to that point and broken. It is only possible to break along the lines of the squares, and each break is from edge to edge. The player who cannot make a move loses. The winner eats all the chocolate.
Which of the two can guarantee a victory for themselves, if Yossi makes the first move?
-
Game with Piles of Stones
Two players are playing the following game. On the table are three piles of stones. The first pile has `10` stones, the second – `15`, and the third – `20`. Each player, in their turn, chooses one of the piles currently on the table and divides it into two smaller piles. The player who cannot make a move loses.
Which of the two players has a winning strategy, and what is it?
Sources: -
Question
A knight exited the square `a1` and, after several moves, returned to the same square.
Is it possible that the knight made an odd number of moves?
Topics:Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Colorings -> Chessboard Coloring -
Question
A knight moves from square `a1` to square `h8`. Is it possible that along the way it visited every square on the board exactly once?
-
Question
The game takes place on an infinite plane. One player moves the wolf, and another player moves K sheep. After the wolf's move, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or a sheep cannot move more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial positions?
Sources: -
Question
On an infinite grid of squares, 6 squares are marked, as in the diagram. How many squares contain stones? In one move, a stone can be removed if it has no adjacent stone above and to its right; then, two stones are placed in the squares above and to the right of the removed stone. Can we remove all stones from the marked squares if the initial state is:
A. (8 points) All marked squares.
B. (8 points) Only the bottom-left marked square.O
O O
O O OM. Konvitz'
Sources: