Olympiad problems

2012 IMC, 5

Let $c \ge 1$ be a real number. Let $G$ be an Abelian group and let $A \subset G$ be a finite set satisfying $|A+A| \le c|A|$, where $X+Y:= \{x+y| x \in X, y \in Y\}$ and $|Z|$ denotes the cardinality of $Z$. Prove that \[|\underbrace{A+A+\dots+A}_k| \le c^k |A|\] for every positive integer $k$. [i]Proposed by Przemyslaw Mazur, Jagiellonian University.[/i]

2014 Bulgaria National Olympiad, 2

Tags: function , induction , limit , geometric series , algebra

Find all functions $f: \mathbb{Q}^+ \to \mathbb{R}^+ $ with the property: \[f(xy)=f(x+y)(f(x)+f(y)) \,,\, \forall x,y \in \mathbb{Q}^+\] [i]Proposed by Nikolay Nikolov[/i]

2014 USA Team Selection Test, 2

Tags: quadratic , induction , modular arithmetic , number theory , quadratic residue

Let $a_1,a_2,a_3,\ldots$ be a sequence of integers, with the property that every consecutive group of $a_i$'s averages to a perfect square. More precisely, for every positive integers $n$ and $k$, the quantity \[\frac{a_n+a_{n+1}+\cdots+a_{n+k-1}}{k}\] is always the square of an integer. Prove that the sequence must be constant (all $a_i$ are equal to the same perfect square). [i]Evan O'Dorney and Victor Wang[/i]

2010 China Western Mathematical Olympiad, 3

Tags: induction , combinatorics

Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

2012 CentroAmerican, 2

Tags: induction , number theory

Alexander and Louise are a pair of burglars. Every morning, Louise steals one third of Alexander's money, but feels remorse later in the afternoon and gives him half of all the money she has. If Louise has no money at the beginning and starts stealing on the first day, what is the least positive integer amount of money Alexander must have so that at the end of the 2012th day they both have an integer amount of money?

2019 Middle European Mathematical Olympiad, 3

Tags: combinatorics , induction

There are $n$ boys and $n$ girls in a school class, where $n$ is a positive integer. The heights of all the children in this class are distinct. Every girl determines the number of boys that are taller than her, subtracts the number of girls that are taller than her, and writes the result on a piece of paper. Every boy determines the number of girls that are shorter than him, subtracts the number of boys that are shorter than him, and writes the result on a piece of paper. Prove that the numbers written down by the girls are the same as the numbers written down by the boys (up to a permutation). [i]Proposed by Stephan Wagner, Austria[/i]

2012 Romania Team Selection Test, 4

Tags: induction , vector , combinatorics

Let $S$ be a set of positive integers, each of them having exactly $100$ digits in base $10$ representation. An element of $S$ is called [i]atom[/i] if it is not divisible by the sum of any two (not necessarily distinct) elements of $S$. If $S$ contains at most $10$ atoms, at most how many elements can $S$ have?

2003 Bulgaria National Olympiad, 3

Tags: polynomial , limit , induction , algebra

Determine all polynomials $P(x)$ with integer coefficients such that, for any positive integer $n$, the equation $P(x)=2^n$ has an integer root.

2013 Brazil National Olympiad, 5

Tags: induction , irrational number , combinatorics

Let $x$ be an irrational number between 0 and 1 and $x = 0.a_1a_2a_3\cdots$ its decimal representation. For each $k \ge 1$, let $p(k)$ denote the number of distinct sequences $a_{j+1} a_{j+2} \cdots a_{j+k}$ of $k$ consecutive digits in the decimal representation of $x$. Prove that $p(k) \ge k+1$ for every positive integer $k$.

2010 Canada National Olympiad, 1

Tags: induction , geometry , geometric transformation , reflection , symmetry , combinatorics

For all natural $n$, an $n$-staircase is a figure consisting of unit squares, with one square in the first row, two squares in the second row, and so on, up to $n$ squares in the $n^{th}$ row, such that all the left-most squares in each row are aligned vertically. Let $f(n)$ denote the minimum number of square tiles requires to tile the $n$-staircase, where the side lengths of the square tiles can be any natural number. e.g. $f(2)=3$ and $f(4)=7$. (a) Find all $n$ such that $f(n)=n$. (b) Find all $n$ such that $f(n) = n+1$.

2010 Contests, 2

Tags: induction , search , combinatorics

How many ways are there to line up $19$ girls (all of different heights) in a row so that no girl has a shorter girl both in front of and behind her?

2020 SAFEST Olympiad, 1

Tags: combinatorics , induction , local argument

You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.

2012 Balkan MO, 3

Tags: induction , inequalities , floor function , combinatorics , logarithm

Let $n$ be a positive integer. Let $P_n=\{2^n,2^{n-1}\cdot 3, 2^{n-2}\cdot 3^2, \dots, 3^n \}.$ For each subset $X$ of $P_n$, we write $S_X$ for the sum of all elements of $X$, with the convention that $S_{\emptyset}=0$ where $\emptyset$ is the empty set. Suppose that $y$ is a real number with $0 \leq y \leq 3^{n+1}-2^{n+1}.$ Prove that there is a subset $Y$ of $P_n$ such that $0 \leq y-S_Y < 2^n$

2020 Malaysia IMONST 2, 6

Tags: combinatorics , induction

Consider the following one-person game: A player starts with score $0$ and writes the number $20$ on an empty whiteboard. At each step, she may erase any one integer (call it a) and writes two positive integers (call them $b$ and $c$) such that $b + c = a$. The player then adds $b\times c$ to her score. She repeats the step several times until she ends up with all $1$'s on the whiteboard. Then the game is over, and the final score is calculated. Let $M, m$ be the maximum and minimum final score that can be possibly obtained respectively. Find $M-m$.

2014 Contests, 1

Tags: trigonometry , induction , algebra

Let $({{x}_{n}}),({{y}_{n}})$ be two positive sequences defined by ${{x}_{1}}=1,{{y}_{1}}=\sqrt{3}$ and \[ \begin{cases} {{x}_{n+1}}{{y}_{n+1}}-{{x}_{n}}=0 \\ x_{n+1}^{2}+{{y}_{n}}=2 \end{cases} \] for all $n=1,2,3,\ldots$. Prove that they are converges and find their limits.

PEN A Problems, 20

Tags: induction , abstract algebra , modular arithmetic , quadratic , number theory , divisibility theory

Determine all positive integers $n$ for which there exists an integer $m$ such that $2^{n}-1$ divides $m^{2}+9$.

1990 China Team Selection Test, 1

Tags: induction , combinatorics

In a wagon, every $m \geq 3$ people have exactly one common friend. (When $A$ is $B$'s friend, $B$ is also $A$'s friend. No one was considered as his own friend.) Find the number of friends of the person who has the most friends.

2010 Indonesia TST, 1

Tags: geometry , ratio , trigonometry , algebra , polynomial , induction , function

Is there a triangle with angles in ratio of $ 1: 2: 4$ and the length of its sides are integers with at least one of them is a prime number? [i]Nanang Susyanto, Jogjakarta[/i]

2008 China Team Selection Test, 1

Tags: algorithm , induction , geometry

Prove that in a plane, arbitrary $ n$ points can be overlapped by discs that the sum of all the diameters is less than $ n$, and the distances between arbitrary two are greater than $ 1$. (where the distances between two discs that have no common points are defined as that the distances between its centers subtract the sum of its radii; the distances between two discs that have common points are zero)

2006 Bulgaria Team Selection Test, 1

Tags: linear algebra , matrix , induction , combinatorics

[b]Problem 1. [/b]In the cells of square table are written the numbers $1$, $0$ or $-1$ so that in every line there is exactly one $1$, amd exactly one $-1$. Each turn we change the places of two columns or two rows. Is it possible, from any such table, after finite number of turns to obtain its opposite table (two tables are opposite if the sum of the numbers written in any two corresponding squares is zero)? [i] Emil Kolev[/i]

PEN O Problems, 52

Tags: induction

Is there a set $S$ of positive integers such that a number is in $S$ if and only if it is the sum of two distinct members of $S$ or a sum of two distinct positive integers not in $S$?

2004 Junior Balkan Team Selection Tests - Romania, 3

Tags: induction , number theory

Let $A$ be a set of positive integers such that a) if $a\in A$, the all the positive divisors of $a$ are also in $A$; b) if $a,b\in A$, with $1<a<b$, then $1+ab \in A$. Prove that if $A$ has at least 3 elements, then $A$ is the set of all positive integers.

1995 All-Russian Olympiad Regional Round, 11.4

Tags: induction , combinatorics

there are some identical squares with sides parallel, in a plane. Among any $k+1$ of them, there are two with a point in common. Prove they can be divided into $2k-1$ sets, such that all the squares in one set aint pairwise disjoint.

2002 China Western Mathematical Olympiad, 3

Tags: induction , number theory

Assume that $ \alpha$ and $ \beta$ are two roots of the equation: $ x^2\minus{}x\minus{}1\equal{}0$. Let $ a_n\equal{}\frac{\alpha^n\minus{}\beta^n}{\alpha\minus{}\beta}$, $ n\equal{}1, 2, \cdots$. (1) Prove that for any positive integer $ n$, we have $ a_{n\plus{}2}\equal{}a_{n\plus{}1}\plus{}a_n$. (2) Find all positive integers $ a$ and $ b$, $ a<b$, satisfying $ b \mid a_n\minus{}2na^n$ for any positive integer $ n$.

2009 Princeton University Math Competition, 2

Tags: calculus , integration , floor function , induction , ceiling function , logarithm

It is known that a certain mechanical balance can measure any object of integer mass anywhere between 1 and 2009 (both included). This balance has $k$ weights of integral values. What is the minimum $k$ for which there exist weights that satisfy this condition?