Olympiad problems

2007 USAMO, 1

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$, letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$. For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$. Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.

2003 Tournament Of Towns, 2

Tags: induction , combinatorics

What least possible number of unit squares $(1\times1)$ must be drawn in order to get a picture of $25 \times 25$-square divided into $625$ of unit squares?

2006 Moldova National Olympiad, 11.8

Tags: induction , combinatorics

Given an alfabet of $n$ letters. A sequence of letters such that between any 2 identical letters there are no 2 identical letters is called a [i]word[/i]. a) Find the maximal possible length of a [i]word[/i]. b) Find the number of the [i]words[/i] of maximal length.

2011 Spain Mathematical Olympiad, 3

Tags: algebra , polynomial , induction , floor function , modular arithmetic , number theory

The sequence $S_0,S_1,S_2,\ldots$ is defined by[list][*]$S_n=1$ for $0\le n\le 2011$, and [*]$S_{n+2012}=S_{n+2011}+S_n$ for $n\ge 0$.[/list]Prove that $S_{2011a}-S_a$ is a multiple of $2011$ for all nonnegative integers $a$.

2003 Putnam, 2

Tags: induction , function

Let $n$ be a positive integer. Starting with the sequence $1,\frac{1}{2}, \frac{1}{3} , \cdots , \frac{1}{n}$, form a new sequence of $n -1$ entries $\frac{3}{4}, \frac{5}{12},\cdots ,\frac{2n -1}{2n(n -1)}$, by taking the averages of two consecutive entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of $n -2$ entries and continue until the final sequence consists of a single number $x_n$. Show that $x_n < \frac{2}{n}$.

1962 AMC 12/AHSME, 32

Tags: induction , arithmetic series

If $ x_{k\plus{}1} \equal{} x_k \plus{} \frac12$ for $ k\equal{}1, 2, \dots, n\minus{}1$ and $ x_1\equal{}1,$ find $ x_1 \plus{} x_2 \plus{} \dots \plus{} x_n.$ $ \textbf{(A)}\ \frac{n\plus{}1}{2} \qquad \textbf{(B)}\ \frac{n\plus{}3}{2} \qquad \textbf{(C)}\ \frac{n^2\minus{}1}{2} \qquad \textbf{(D)}\ \frac{n^2\plus{}n}{4} \qquad \textbf{(E)}\ \frac{n^2\plus{}3n}{4}$

2013 Iran MO (2nd Round), 2

Tags: induction , invariant , geometry , geometric transformation , combinatorics

Suppose a $m \times n$ table. We write an integer in each cell of the table. In each move, we chose a column, a row, or a diagonal (diagonal is the set of cells which the difference between their row number and their column number is constant) and add either $+1$ or $-1$ to all of its cells. Prove that if for all arbitrary $3 \times 3$ table we can change all numbers to zero, then we can change all numbers of $m \times n$ table to zero. ([i]Hint[/i]: First of all think about it how we can change number of $ 3 \times 3$ table to zero.)

2004 AMC 10, 16

Tags: induction

The $ 5\times 5$ grid shown contains a collection of squares with sizes from $ 1\times 1$ to $ 5\times 5$. How many of these squares contain the black center square? [asy]unitsize(6mm); defaultpen(linewidth(.8pt)); for(int i=0; i<=5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } fill((2,2)--(2,3)--(3,3)--(3,2)--cycle);[/asy]$ \textbf{(A)}\ 12\qquad \textbf{(B)}\ 15\qquad \textbf{(C)}\ 17\qquad \textbf{(D)}\ 19\qquad \textbf{(E)}\ 20$

2011 Puerto Rico Team Selection Test, 7

Tags: modular arithmetic , induction , algebra

Show that for any natural number n, n^3 + (n + 1)^3 + (n + 2)^3 is divisible by 9.

2010 Vietnam National Olympiad, 4

Tags: induction , number theory

Prove that for each positive integer n,the equation $x^{2}+15y^{2}=4^{n}$ has at least $n$ integer solution $(x,y)$

PEN O Problems, 23

Tags: induction

Let $k, m, n$ be integers such that $1<n\le m-1 \le k$. Determine the maximum size of a subset $S$ of the set $\{ 1,2, \cdots, k \}$ such that no $n$ distinct elements of $S$ add up to $m$.

2014 AMC 12/AHSME, 23

Tags: binomial coefficient , pascal triangle , modular arithmetic , induction

The number $2017$ is prime. Let $S=\sum_{k=0}^{62}\binom{2014}{k}$. What is the remainder when $S$ is divided by $2017$? $\textbf{(A) }32\qquad \textbf{(B) }684\qquad \textbf{(C) }1024\qquad \textbf{(D) }1576\qquad \textbf{(E) }2016\qquad$

2007 Brazil National Olympiad, 2

Tags: quadratic , modular arithmetic , induction , number theory

Find the number of integers $ c$ such that $ \minus{}2007 \leq c \leq 2007$ and there exists an integer $ x$ such that $ x^2 \plus{} c$ is a multiple of $ 2^{2007}$.

1999 IberoAmerican, 3

Tags: induction , geometry , number theory

Let $A$ and $B$ points in the plane and $C$ a point in the perpendiclar bisector of $AB$. It is constructed a sequence of points $C_1,C_2,\dots, C_n,\dots$ in the following way: $C_1=C$ and for $n\geq1$, if $C_n$ does not belongs to $AB$, then $C_{n+1}$ is the circumcentre of the triangle $\triangle{ABC_n}$. Find all the points $C$ such that the sequence $C_1,C_2,\dots$ is defined for all $n$ and turns eventually periodic. Note: A sequence $C_1,C_2, \dots$ is called eventually periodic if there exist positive integers $k$ and $p$ such that $C_{n+p}=c_n$ for all $n\geq{k}$.

2008 ITest, 60

Tags: induction

Consider the Harmonic Table \[\begin{array}{c@{\hspace{15pt}}c@{\hspace{15pt}}c@{\hspace{15pt}}c@{\hspace{15pt}}c@{\hspace{15pt}}c@{\hspace{15pt}}c}&&&1&&&\\&&\tfrac12&&\tfrac12&&\\&\tfrac13&&\tfrac16&&\tfrac13&\\\tfrac14&&\tfrac1{12}&&\tfrac1{12}&&\tfrac14\\&&&\vdots&&&\end{array}\] where $a_{n,1}=1/n$ and \[a_{n,k+1}=a_{n-1,k}-a_{n,k}.\] Find the remainder when the sum of the reciprocals of the $2007$ terms on the $2007^\text{th}$ row gets divided by $2008$.

2005 MOP Homework, 6

Tags: function , floor function , induction , algebra

Let $c$ be a fixed positive integer, and $\{x_k\}^{\inf}_{k=1}$ be a sequence such that $x_1=c$ and $x_n=x_{n-1}+\lfloor \frac{2x_{n-1}-2}{n} \rfloor$ for $n \ge 2$. Determine the explicit formula of $x_n$ in terms of $n$ and $c$. (Here $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

PEN E Problems, 23

Tags: induction , number theory , prime number

Let $p_{1}=2, p_{2}={3}, p_{3}=5, \cdots, p_{n}$ be the first $n$ prime numbers, where $n \ge 3$. Prove that \[\frac{1}{{p_{1}}^{2}}+\frac{1}{{p_{2}}^{2}}+\cdots+\frac{1}{{p_{n}}^{2}}+\frac{1}{p_{1}p_{2}\cdots p_{n}}< \frac{1}{2}.\]

2024 APMO, 3

Tags: algebra , inequality , induction

Let $n$ be a positive integer and let $a_1, a_2, \ldots, a_n$ be positive reals. Show that $$\sum_{i=1}^{n} \frac{1}{2^i}(\frac{2}{1+a_i})^{2^i} \geq \frac{2}{1+a_1a_2\ldots a_n}-\frac{1}{2^n}.$$

2006 ISI B.Math Entrance Exam, 3

Tags: induction , algebra

Find all roots of the equation :- $1-\frac{x}{1}+\frac{x(x-1)}{2!} - \cdots +(-1)^n\frac{x(x-1)(x-2)...(x-n+1)}{n!}=0$.

2005 China Team Selection Test, 2

Tags: gauss , function , induction , search , inequalities

Let $n$ be a positive integer, and $x$ be a positive real number. Prove that $$\sum_{k=1}^{n} \left( x \left[\frac{k}{x}\right] - (x+1)\left[\frac{k}{x+1}\right]\right) \leq n,$$ where $[x]$ denotes the largest integer not exceeding $x$.

2011 Indonesia MO, 2

Tags: induction , number theory

For each positive integer $n$, let $s_n$ be the number of permutations $(a_1, a_2, \cdots, a_n)$ of $(1, 2, \cdots, n)$ such that $\dfrac{a_1}{1} + \dfrac{a_2}{2} + \cdots + \dfrac{a_n}{n}$ is a positive integer. Prove that $s_{2n} \ge n$ for all positive integer $n$.

2009 All-Russian Olympiad, 6

Tags: topology , induction , euler , linear algebra , matrix , invariant , graph theory

Given a finite tree $ T$ and isomorphism $ f: T\rightarrow T$. Prove that either there exist a vertex $ a$ such that $ f(a)\equal{}a$ or there exist two neighbor vertices $ a$, $ b$ such that $ f(a)\equal{}b$, $ f(b)\equal{}a$.

2009 Indonesia TST, 2

Tags: polynomial , induction , algebra

Let $ f(x)\equal{}a_{2n}x^{2n}\plus{}a_{2n\minus{}1}x^{2n\minus{}1}\plus{}\cdots\plus{}a_1x\plus{}a_0$, with $ a_i\equal{}a_{2n\minus{}1}$ for all $ i\equal{}1,2,\ldots,n$ and $ a_{2n}\ne0$. Prove that there exists a polynomial $ g(x)$ of degree $ n$ such that $ g\left(x\plus{}\frac1x\right)x^n\equal{}f(x)$.

PEN M Problems, 24

Tags: floor function , induction , recursive sequences

Let $k$ be a given positive integer. The sequence $x_n$ is defined as follows: $x_1 =1$ and $x_{n+1}$ is the least positive integer which is not in $\{x_{1}, x_{2},..., x_{n}, x_{1}+k, x_{2}+2k,..., x_{n}+nk \}$. Show that there exist real number $a$ such that $x_n = \lfloor an\rfloor$ for all positive integer $n$.

2013 India IMO Training Camp, 3

Tags: induction , algebra

Let $h \ge 3$ be an integer and $X$ the set of all positive integers that are greater than or equal to $2h$. Let $S$ be a nonempty subset of $X$ such that the following two conditions hold: [list] [*]if $a + b \in S$ with $a \ge h, b \ge h$, then $ab \in S$; [*]if $ab \in S$ with $a \ge h, b \ge h$, then $a + b \in S$.[/list] Prove that $S = X$.