Olympiad problems

2008 AMC 12/AHSME, 15

Let $ k\equal{}2008^2\plus{}2^{2008}$. What is the units digit of $ k^2\plus{}2^k$? $ \textbf{(A)}\ 0 \qquad \textbf{(B)}\ 2 \qquad \textbf{(C)}\ 4 \qquad \textbf{(D)}\ 6 \qquad \textbf{(E)}\ 8$

2003 APMO, 5

Tags: graph theory , combinatorics , induction

Given two positive integers $m$ and $n$, find the smallest positive integer $k$ such that among any $k$ people, either there are $2m$ of them who form $m$ pairs of mutually acquainted people or there are $2n$ of them forming $n$ pairs of mutually unacquainted people.

2006 China Western Mathematical Olympiad, 4

Tags: induction , combinatorics

Given a positive integer $ n\geq 2$, let $ B_{1}$, $ B_{2}$, ..., $ B_{n}$ denote $ n$ subsets of a set $ X$ such that each $ B_{i}$ contains exactly two elements. Find the minimum value of $ \left|X\right|$ such that for any such choice of subsets $ B_{1}$, $ B_{2}$, ..., $ B_{n}$, there exists a subset $ Y$ of $ X$ such that: (1) $ \left|Y\right| \equal{} n$; (2) $ \left|Y \cap B_{i}\right|\leq 1$ for every $ i\in\left\{1,2,...,n\right\}$.

2014 AMC 10, 20

Tags: induction

The product $(8)(888\dots8)$, where the second factor has $k$ digits, is an integer whose digits have a sum of $1000$. What is $k$? ${ \textbf{(A)}\ 901\qquad\textbf{(B)}\ 911\qquad\textbf{(C)}\ 919\qquad\textbf{(D)}}\ 991\qquad\textbf{(E)}\ 999 $

1999 All-Russian Olympiad, 6

Tags: floor function , inequalities , number theory , algebra , induction

Prove that for all natural numbers $n$, \[ \sum_{k=1}^{n^2} \left\{ \sqrt{k} \right\} \le \frac{n^2-1}{2}. \] Here, $\{x\}$ denotes the fractional part of $x$.

1997 Putnam, 3

Tags: induction , integration , calculus

Evaluate the following : \[ \int_{0}^{\infty}\left(x-\frac{x^3}{2}+\frac{x^5}{2\cdot 4}-\frac{x^7}{2\cdot 4\cdot 6}+\cdots \right)\;\left(1+\frac{x^2}{2^2}+\frac{x^4}{2^2\cdot 4^2}+\frac{x^6}{2^2\cdot 4^2\cdot 6^2}+\cdots \right)\,\mathrm{d}x \]

2005 QEDMO 1st, 1 (Z4)

Tags: 3d geometry , modular arithmetic , geometry , induction , number theory

Prove that every integer can be written as sum of $5$ third powers of integers.

2016 Ukraine Team Selection Test, 4

Tags: induction , modular arithmetic , number theory

Find all positive integers $a$ such that for any positive integer $n\ge 5$ we have $2^n-n^2\mid a^n-n^a$.

2004 APMO, 1

Tags: greatest common divisor , number theory , induction

Determine all finite nonempty sets $S$ of positive integers satisfying \[ {i+j\over (i,j)}\qquad\mbox{is an element of S for all i,j in S}, \] where $(i,j)$ is the greatest common divisor of $i$ and $j$.

PEN K Problems, 3

Tags: functional equation , function , induction

Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$: \[f(n+1) > f(f(n)).\]

2007 District Olympiad, 1

Tags: limit , real analysis , induction

Let $a_1\in (0,1)$ and $(a_n)_{n\ge 1}$ a sequence of real numbers defined by $a_{n+1}=a_n(1-a_n^2),\ (\forall)n\ge 1$. Evaluate $\lim_{n\to \infty} a_n\sqrt{n}$.

2012 Kazakhstan National Olympiad, 3

Tags: number theory , induction

The sequence $a_{n}$ defined as follows: $a_{1}=4, a_{2}=17$ and for any $k\geq1$ true equalities $a_{2k+1}=a_{2}+a_{4}+...+a_{2k}+(k+1)(2^{2k+3}-1)$ $a_{2k+2}=(2^{2k+2}+1)a_{1}+(2^{2k+3}+1)a_{3}+...+(2^{3k+1}+1)a_{2k-1}+k$ Find the smallest $m$ such that $(a_{1}+...a_{m})^{2012^{2012}}-1$ divided $2^{2012^{2012}}$

2001 Cono Sur Olympiad, 3

Tags: algebra , function , induction

A function $g$ defined for all positive integers $n$ satisfies [list][*]$g(1) = 1$; [*]for all $n\ge 1$, either $g(n+1)=g(n)+1$ or $g(n+1)=g(n)-1$; [*]for all $n\ge 1$, $g(3n) = g(n)$; and [*]$g(k)=2001$ for some positive integer $k$.[/list] Find, with proof, the smallest possible value of $k$.

2013 USAJMO, 4

Tags: olympiad combinatorics , recursion , function , induction

Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$, where we keep track of the order of the summation. For example, $f(4)=6$ because $4$ can be written as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$. Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

2008 China Team Selection Test, 3

Tags: trapezoid , geometry , trigonometry , number theory , modular arithmetic , analytic geometry , induction

Find all positive integers $ n$ having the following properties:in two-dimensional Cartesian coordinates, there exists a convex $ n$ lattice polygon whose lengths of all sides are odd numbers, and unequal to each other. (where lattice polygon is defined as polygon whose coordinates of all vertices are integers in Cartesian coordinates.)

PEN K Problems, 16

Tags: functional equation , induction , function

Find all functions $f: \mathbb{Z}\to \mathbb{Z}$ such that for all $m,n\in \mathbb{Z}$: \[f(m+f(n)) = f(m)+n.\]

2009 Indonesia TST, 1

Tags: logarithm , combinatorics , induction , inequalities

2008 persons take part in a programming contest. In one round, the 2008 programmers are divided into two groups. Find the minimum number of groups such that every two programmers ever be in the same group.

2009 USA Team Selection Test, 1

Tags: rectangle , induction , geometry , combinatorics

Let $m$ and $n$ be positive integers. Mr. Fat has a set $S$ containing every rectangular tile with integer side lengths and area of a power of $2$. Mr. Fat also has a rectangle $R$ with dimensions $2^m \times 2^n$ and a $1 \times 1$ square removed from one of the corners. Mr. Fat wants to choose $m + n$ rectangles from $S$, with respective areas $2^0, 2^1, \ldots, 2^{m + n - 1}$, and then tile $R$ with the chosen rectangles. Prove that this can be done in at most $(m + n)!$ ways. [i]Palmer Mebane.[/i]

2013 Rioplatense Mathematical Olympiad, Level 3, 4

Tags: induction , game strategy , game , combinatorics

Two players $A$ and $B$ play alternatively in a convex polygon with $n \geq 5$ sides. In each turn, the corresponding player has to draw a diagonal that does not cut inside the polygon previously drawn diagonals. A player loses if after his turn, one quadrilateral is formed such that its two diagonals are not drawn. $A$ starts the game. For each positive integer $n$, find a winning strategy for one of the players.

2007 Korea National Olympiad, 4

Tags: prime number , induction , relatively prime , inequalities , number theory

For all positive integer $ n\geq 2$, prove that product of all prime numbers less or equal than $ n$ is smaller than $ 4^{n}$.

2007 Tournament Of Towns, 6

Tags: function , combinatorics , induction

The audience arranges $n$ coins in a row. The sequence of heads and tails is chosen arbitrarily. The audience also chooses a number between $1$ and $n$ inclusive. Then the assistant turns one of the coins over, and the magician is brought in to examine the resulting sequence. By an agreement with the assistant beforehand, the magician tries to determine the number chosen by the audience. [list][b](a)[/b] Prove that if this is possible for some $n$, then it is also possible for $2n$. [b](b)[/b] Determine all $n$ for which this is possible.[/list]

2012 Math Prize for Girls Olympiad, 2

Tags: induction , geometry , floor function , rectangle

Let $m$ and $n$ be integers greater than 1. Prove that $\left\lfloor \dfrac{mn}{6} \right\rfloor$ non-overlapping 2-by-3 rectangles can be placed in an $m$-by-$n$ rectangle. Note: $\lfloor x \rfloor$ means the greatest integer that is less than or equal to $x$.