Olympiad problems

2017-IMOC, C2

On a large chessboard, there are $4$ puddings that form a square with size $1$. A pudding $A$ could jump over a pudding $B$, or equivalently, $A$ moves to the symmetric point with respect to $B$. Is it possible that after finite times of jumping, the puddings form a square with size $2$?

2015 Switzerland - Final Round, 5

Tags: combinatorics , invariant , combinatorial algebra

We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ . [i]Proposed by Abbas Mehrabian, Iran[/i]

1986 IMO Shortlist, 12

Tags: invariant , algorithm , combinatorics , pentagon , game strategy

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

1989 IMO Longlists, 64

Tags: combinatorics , invariant , chessboard , algorithm

A natural number is written in each square of an $ m \times n$ chess board. The allowed move is to add an integer $ k$ to each of two adjacent numbers in such a way that non-negative numbers are obtained. (Two squares are adjacent if they have a common side.) Find a necessary and sufficient condition for it to be possible for all the numbers to be zero after finitely many operations.

Russian TST 2014, P3

Tags: combinatorics , game , invariant

Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In every round, player $A$ picks some positive integer $m$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves.

1958 AMC 12/AHSME, 40

Tags: invariant , algebra , polynomial , linear algebra , matrix , vector , geometry

Given $ a_0 \equal{} 1$, $ a_1 \equal{} 3$, and the general relation $ a_n^2 \minus{} a_{n \minus{} 1}a_{n \plus{} 1} \equal{} (\minus{}1)^n$ for $ n \ge 1$. Then $ a_3$ equals: $ \textbf{(A)}\ \frac{13}{27}\qquad \textbf{(B)}\ 33\qquad \textbf{(C)}\ 21\qquad \textbf{(D)}\ 10\qquad \textbf{(E)}\ \minus{}17$

2023 Bulgaria JBMO TST, 3

Tags: combinatorics , invariant

There are infinitely many boxes - initially one of them contains $n$ balls and all others are empty. On a single move we take some balls from a non-empty box and put them into an empty box and on a sheet of paper we write down the product of the resulting amount of balls in the two boxes. After some moves, the sum of all numbers on the sheet of paper became $2023$. What is the smallest possible value of $n$?

1995 Belarus National Olympiad, Problem 8

Tags: invariant , combinatorics

Five numbers 1,2,3,4,5 are written on a blackboard. A student may erase any two of the numbers a and b on the board and write the numbers a+b and ab replacing them. If this operation is performed repeatedly, can the numbers 21,27,64,180,540 ever appear on the board?

2023 Indonesia TST, 2

Tags: combinatorics , coin , invariant , monovariant

Let $n > 3$ be a positive integer. Suppose that $n$ children are arranged in a circle, and $n$ coins are distributed between them (some children may have no coins). At every step, a child with at least 2 coins may give 1 coin to each of their immediate neighbors on the right and left. Determine all initial distributions of the coins from which it is possible that, after a finite number of steps, each child has exactly one coin.