Olympiad problems

2009 AMC 12/AHSME, 21

Ten women sit in $ 10$ seats in a line. All of the $ 10$ get up and then reseat themselves using all $ 10$ seats, each sitting in the seat she was in before or a seat next to the one she occupied before. In how many ways can the women be reseated? $ \textbf{(A)}\ 89\qquad \textbf{(B)}\ 90\qquad \textbf{(C)}\ 120\qquad \textbf{(D)}\ 2^{10}\qquad \textbf{(E)}\ 2^2 3^8$

2003 All-Russian Olympiad, 4

Tags: symmetry , ceiling function , geometry , rectangle , combinatorics

Find the greatest natural number $N$ such that, for any arrangement of the numbers $1, 2, \ldots, 400$ in a chessboard $20 \times 20$, there exist two numbers in the same row or column, which differ by at least $N.$

1995 Iran MO (2nd round), 2

Tags: function , ceiling function , quadratic , number theory

Let $n \geq 0$ be an integer. Prove that \[ \lceil \sqrt n +\sqrt{n+1}+\sqrt{n+2} \rceil = \lceil \sqrt{9n+8} \rceil\] Where $\lceil x \rceil $ is the smallest integer which is greater or equal to $x.$

2008 ITest, 61

Tags: ceiling function , modular arithmetic

Find the units digit in the decimal expansion of \[\left(2008+\sqrt{4032000}\right)^{2000}+\left(2008+\sqrt{4032000}\right)^{2001}+\left(2008+\sqrt{4032000}\right)^{2002}+\]\[\cdots+\left(2008+\sqrt{4032000}\right)^{2007}+\left(2008+\sqrt{4032000}\right)^{2008}.\]

2014 Math Prize For Girls Problems, 19

Tags: limit , function , probability , expected value , ceiling function

Let $n$ be a positive integer. Let $(a, b, c)$ be a random ordered triple of nonnegative integers such that $a + b + c = n$, chosen uniformly at random from among all such triples. Let $M_n$ be the expected value (average value) of the largest of $a$, $b$, and $c$. As $n$ approaches infinity, what value does $\frac{M_n}{n}$ approach?

2010 Polish MO Finals, 1

Tags: pigeonhole principle , ceiling function , combinatorics

The integer number $n > 1$ is given and a set $S \subset \{0, 1, 2, \ldots, n-1\}$ with $|S| > \frac{3}{4} n$. Prove that there exist integer numbers $a, b, c$ such that the remainders after the division by $n$ of the numbers: \[a, b, c, a+b, b+c, c+a, a+b+c\] belong to $S$.

2003 Baltic Way, 17

Tags: ceiling function , number theory

All the positive divisors of a positive integer $n$ are stored into an increasing array. Mary is writing a programme which decides for an arbitrarily chosen divisor $d > 1$ whether it is a prime. Let $n$ have $k$ divisors not greater than $d$. Mary claims that it suffices to check divisibility of $d$ by the first $\left\lceil\frac{k}{2}\right\rceil$ divisors of $n$: $d$ is prime if and only if none of them but $1$ divides $d$. Is Mary right?

2008 Bulgaria National Olympiad, 3

Tags: inequalities , trigonometry , modular arithmetic , induction , ceiling function , pigeonhole principle , algebra

Let $n\in\mathbb{N}$ and $0\leq a_1\leq a_2\leq\ldots\leq a_n\leq\pi$ and $b_1,b_2,\ldots ,b_n$ are real numbers for which the following inequality is satisfied : \[\left|\sum_{i\equal{}1}^{n} b_i\cos(ka_i)\right|<\frac{1}{k}\] for all $ k\in\mathbb{N}$. Prove that $ b_1\equal{}b_2\equal{}\ldots \equal{}b_n\equal{}0$.

2012 AMC 10, 14

Tags: ceiling function , geometry , rectangle

Chubby makes nonstandard checkerboards that have $31$ squares on each side. The checkerboards have a black square in every corner and alternate red and black squares along every row and column. How many black squares are there on such a checkerboard? $ \textbf{(A)}\ 480 \qquad\textbf{(B)}\ 481 \qquad\textbf{(C)}\ 482 \qquad\textbf{(D)}\ 483 \qquad\textbf{(E)}\ 484 $

2012 JBMO TST - Turkey, 4

Tags: floor function , ceiling function , combinatorics

Let $G$ be a connected simple graph. When we add an edge to $G$ (between two unconnected vertices), then using at most $17$ edges we can reach any vertex from any other vertex. Find the maximum number of edges to be used to reach any vertex from any other vertex in the original graph, i.e. in the graph before we add an edge.

2020 Greece Team Selection Test, 4

Tags: ceiling function , number theory , perfect square

Let $a$ and $b$ be two positive integers. Prove that the integer \[a^2+\left\lceil\frac{4a^2}b\right\rceil\] is not a square. (Here $\lceil z\rceil$ denotes the least integer greater than or equal to $z$.) [i]Russia[/i]

1999 Baltic Way, 6

Tags: induction , floor function , ceiling function , combinatorics

What is the least number of moves it takes a knight to get from one corner of an $n\times n$ chessboard, where $n\ge 4$, to the diagonally opposite corner?

1994 IberoAmerican, 2

Tags: function , ceiling function , combinatorics

Let $n$ and $r$ two positive integers. It is wanted to make $r$ subsets $A_1,\ A_2,\dots,A_r$ from the set $\{0,1,\cdots,n-1\}$ such that all those subsets contain exactly $k$ elements and such that, for all integer $x$ with $0\leq{x}\leq{n-1}$ there exist $x_1\in{}A_1,\ x_2\in{}A_2 \dots,x_r\in{}A_r$ (an element of each set) with $x=x_1+x_2+\cdots+x_r$. Find the minimum value of $k$ in terms of $n$ and $r$.

1993 Balkan MO, 2

Tags: calculus , integration , ceiling function , floor function , inequalities , combinatorics

A positive integer given in decimal representation $\overline{ a_na_{n-1} \ldots a_1a_0 }$ is called [i]monotone[/i] if $a_n\leq a_{n-1} \leq \cdots \leq a_0$. Determine the number of monotone positive integers with at most 1993 digits.

2005 France Team Selection Test, 4

Tags: floor function , ceiling function , induction , inequalities , number theory , logarithm

Let $X$ be a non empty subset of $\mathbb{N} = \{1,2,\ldots \}$. Suppose that for all $x \in X$, $4x \in X$ and $\lfloor \sqrt{x} \rfloor \in X$. Prove that $X=\mathbb{N}$.

1987 IMO Longlists, 49

Tags: analytic geometry , ceiling function , combinatorics

In the coordinate system in the plane we consider a convex polygon $W$ and lines given by equations $x = k, y = m$, where $k$ and $m$ are integers. The lines determine a tiling of the plane with unit squares. We say that the boundary of $W$ intersects a square if the boundary contains an interior point of the square. Prove that the boundary of $W$ intersects at most $4 \lceil d \rceil $ unit squares, where $d$ is the maximal distance of points belonging to $W$ (i.e., the diameter of $W$) and $\lceil d \rceil$ is the least integer not less than $d.$

2011 China Team Selection Test, 2

Tags: ceiling function , floor function , number theory

Let $a_1,a_2,\ldots,a_n,\ldots$ be any permutation of all positive integers. Prove that there exist infinitely many positive integers $i$ such that $\gcd(a_i,a_{i+1})\leq \frac{3}{4} i$.

1997 Romania Team Selection Test, 4

Tags: floor function , ceiling function , number theory , prime number , combinatorics , poset

Let $p,q,r$ be distinct prime numbers and let \[A=\{p^aq^br^c\mid 0\le a,b,c\le 5\} \] Find the least $n\in\mathbb{N}$ such that for any $B\subset A$ where $|B|=n$, has elements $x$ and $y$ such that $x$ divides $y$. [i]Ioan Tomescu[/i]

2012 ELMO Shortlist, 4

Tags: induction , floor function , ceiling function , inequalities , pigeonhole principle , combinatorics

A tournament on $2k$ vertices contains no $7$-cycles. Show that its vertices can be partitioned into two sets, each with size $k$, such that the edges between vertices of the same set do not determine any $3$-cycles. [i]Calvin Deng.[/i]

2010 USAMO, 3

Tags: inequalities , ceiling function , algebra

The 2010 positive numbers $a_1, a_2, \ldots , a_{2010}$ satisfy the inequality $a_ia_j \le i+j$ for all distinct indices $i, j$. Determine, with proof, the largest possible value of the product $a_1a_2\ldots a_{2010}$.

Russian TST 2020, P3

Tags: ceiling function , number theory , perfect square

Let $a$ and $b$ be two positive integers. Prove that the integer \[a^2+\left\lceil\frac{4a^2}b\right\rceil\] is not a square. (Here $\lceil z\rceil$ denotes the least integer greater than or equal to $z$.) [i]Russia[/i]

2010 Iran MO (3rd Round), 4

Tags: floor function , ceiling function , combinatorics

suppose that $\mathcal F\subseteq X^{(K)}$ and $|X|=n$. we know that for every three distinct elements of $\mathcal F$ like $A,B$ and $C$ we have $A\cap B \not\subset C$. a)(10 points) Prove that : \[|\mathcal F|\le \dbinom{k}{\lfloor\frac{k}{2}\rfloor}+1\] b)(15 points) if elements of $\mathcal F$ do not necessarily have $k$ elements, with the above conditions show that: \[|\mathcal F|\le \dbinom{n}{\lceil\frac{n-2}{3}\rceil}+2\]

2005 All-Russian Olympiad, 3

Tags: ceiling function , induction , combinatorics

Given 2005 distinct numbers $a_1,\,a_2,\dots,a_{2005}$. By one question, we may take three different indices $1\le i<j<k\le 2005$ and find out the set of numbers $\{a_i,\,a_j,\,a_k\}$ (unordered, of course). Find the minimal number of questions, which are necessary to find out all numbers $a_i$.

2003 Germany Team Selection Test, 3

Tags: floor function , inequalities , least common multiple , ceiling function , number theory

Let $N$ be a natural number and $x_1, \ldots , x_n$ further natural numbers less than $N$ and such that the least common multiple of any two of these $n$ numbers is greater than $N$. Prove that the sum of the reciprocals of these $n$ numbers is always less than $2$: $\sum^n_{i=1} \frac{1}{x_i} < 2.$

2006 Iran Team Selection Test, 2

Tags: ceiling function , algebra , logarithm

Let $n$ be a fixed natural number. [b]a)[/b] Find all solutions to the following equation : \[ \sum_{k=1}^n [\frac x{2^k}]=x-1 \] [b]b)[/b] Find the number of solutions to the following equation ($m$ is a fixed natural) : \[ \sum_{k=1}^n [\frac x{2^k}]=x-m \]