Olympiad problems

1968 Putnam, A2

Tags: approximation

Given integers $a,b,c,d,m,n$ such that $ad-bc\ne 0$ and any real $\varepsilon >0$, show that one can find rational numbers $x,y$ such that $0<|ax+by-m|<\varepsilon$ and $0<|cx+dy-n|<\varepsilon$.

1968 IMO Shortlist, 19

Tags: approximation , circles , combinatorics , algebra

We are given a fixed point on the circle of radius $1$, and going from this point along the circumference in the positive direction on curved distances $0, 1, 2, \ldots $ from it we obtain points with abscisas $n = 0, 1, 2, .\ldots$ respectively. How many points among them should we take to ensure that some two of them are less than the distance $\frac 15$ apart ?

1947 Putnam, B2

Tags: differentiable function , approximation

Let $f(x)$ be a differentiable function defined on the interval $(0,1)$ such that $|f'(x)| \leq M$ for $0<x<1$ and a positive real number $M.$ Prove that $$\left| \int_{0}^{1} f(x)\; dx - \frac{1}{n} \sum_{k=1}^{n} f\left(\frac{k}{n} \right) \right | \leq \frac{M}{n}.$$

1946 Putnam, B4

Tags: approximation , sequence

For each positive integer $n$, put $$p_n =\left(1+\frac{1}{n}\right)^{n},\; P_n =\left(1+\frac{1}{n}\right)^{n+1}, \; h_n = \frac{2 p_n P_{n}}{ p_n + P_n }.$$ Prove that $h_1 < h_2 < h_3 <\ldots$

1983 IMO Longlists, 60

Tags: summation , series summation , approximation , inequality , algebra

Find the greatest integer less than or equal to $\sum_{k=1}^{2^{1983}} k^{\frac{1}{1983} -1}.$

1975 IMO Shortlist, 14

Tags: approximation , inequality , sequence , recurrence relation , integration , algebra

Let $x_0 = 5$ and $x_{n+1} = x_n + \frac{1}{x_n} \ (n = 0, 1, 2, \ldots )$. Prove that \[45 < x_{1000} < 45. 1.\]

2021 Brazil Undergrad MO, Problem 3

Tags: power , approximation , irrational number , perfect square , real analysis

Find all positive integers $k$ for which there is an irrational $\alpha>1$ and a positive integer $N$ such that $\left\lfloor\alpha^{n}\right\rfloor$ is of the form $m^2-k$ com $m \in \mathbb{Z}$ for every integer $n>N$.

1967 IMO Longlists, 16

Tags: approximation , irrational number , number theory

Prove the following statement: If $r_1$ and $r_2$ are real numbers whose quotient is irrational, then any real number $x$ can be approximated arbitrarily well by the numbers of the form $\ z_{k_1,k_2} = k_1r_1 + k_2r_2$ integers, i.e. for every number $x$ and every positive real number $p$ two integers $k_1$ and $k_2$ can be found so that $|x - (k_1r_1 + k_2r_2)| < p$ holds.

2018 China National Olympiad, 3

Tags: fractional part , approximation , inequality , diophantine approximation , number theory

Let $q$ be a positive integer which is not a perfect cube. Prove that there exists a positive constant $C$ such that for all natural numbers $n$, one has $$\{ nq^{\frac{1}{3}} \} + \{ nq^{\frac{2}{3}} \} \geq Cn^{-\frac{1}{2}}$$ where $\{ x \}$ denotes the fractional part of $x$.

2010 Morocco TST, 2

Tags: algebra , series summation , approximation , floor function , integration , calculus

Find the integer represented by $\left[ \sum_{n=1}^{10^9} n^{-2/3} \right] $. Here $[x]$ denotes the greatest integer less than or equal to $x.$

1995 IMC, 10

Tags: real analysis , approximation , function

a) Prove that for every $\epsilon>0$ there is a positive integer $n$ and real numbers $\lambda_{1},\dots,\lambda_{n}$ such that $$\max_{x\in [-1,1]}|x-\sum_{k=1}^{n}\lambda_{k}x^{2k+1}|<\epsilon.$$ b) Prove that for every odd continuous function $f$ on $[-1,1]$ and for every $\epsilon>0$ there is a positive integer $n$ and real numbers $\mu_{1},\dots,\mu_{n}$ such that $$\max_{x\in [-1,1]}|f(x)-\sum_{k=1}^{n}\mu_{k}x^{2k+1}|<\epsilon.$$

1975 IMO Shortlist, 3

Tags: integration , floor function , calculus , series summation , approximation , algebra

Find the integer represented by $\left[ \sum_{n=1}^{10^9} n^{-2/3} \right] $. Here $[x]$ denotes the greatest integer less than or equal to $x.$

1967 IMO Shortlist, 4

Tags: number theory , approximation , irrational number

Prove the following statement: If $r_1$ and $r_2$ are real numbers whose quotient is irrational, then any real number $x$ can be approximated arbitrarily well by the numbers of the form $\ z_{k_1,k_2} = k_1r_1 + k_2r_2$ integers, i.e. for every number $x$ and every positive real number $p$ two integers $k_1$ and $k_2$ can be found so that $|x - (k_1r_1 + k_2r_2)| < p$ holds.

2017 IMC, 4

Tags: approximation , probabilistic method , combinatorics

There are $n$ people in a city, and each of them has exactly $1000$ friends (friendship is always symmetric). Prove that it is possible to select a group $S$ of people such that at least $\frac{n}{2017}$ persons in $S$ have exactly two friends in $S$.

1967 IMO Longlists, 14

Tags: number theory , approximation , decimal representation , rational number , irrational number

Which fractions $ \dfrac{p}{q},$ where $p,q$ are positive integers $< 100$, is closest to $\sqrt{2} ?$ Find all digits after the point in decimal representation of that fraction which coincide with digits in decimal representation of $\sqrt{2}$ (without using any table).

1983 IMO Longlists, 23

Tags: polynomial , algebra , number theory , approximation , rational number

Let $p$ and $q$ be integers. Show that there exists an interval $I$ of length $1/q$ and a polynomial $P$ with integral coefficients such that \[ \left|P(x)-\frac pq \right| < \frac{1}{q^2}\]for all $x \in I.$

1967 IMO Shortlist, 2

Tags: number theory , approximation , decimal representation , rational number , irrational number

Which fractions $ \dfrac{p}{q},$ where $p,q$ are positive integers $< 100$, is closest to $\sqrt{2} ?$ Find all digits after the point in decimal representation of that fraction which coincide with digits in decimal representation of $\sqrt{2}$ (without using any table).

1983 IMO Shortlist, 21

Tags: algebra , summation , series summation , approximation , inequality

Find the greatest integer less than or equal to $\sum_{k=1}^{2^{1983}} k^{\frac{1}{1983} -1}.$

1983 IMO Shortlist, 10

Tags: algebra , number theory , polynomial , approximation , rational number

Let $p$ and $q$ be integers. Show that there exists an interval $I$ of length $1/q$ and a polynomial $P$ with integral coefficients such that \[ \left|P(x)-\frac pq \right| < \frac{1}{q^2}\]for all $x \in I.$