Olympiad problems

1984 IMO Shortlist, 17

In a permutation $(x_1, x_2, \dots , x_n)$ of the set $1, 2, \dots , n$ we call a pair $(x_i, x_j )$ discordant if $i < j$ and $x_i > x_j$. Let $d(n, k)$ be the number of such permutations with exactly $k$ discordant pairs. Find $d(n, 2)$ and $d(n, 3).$

2002 District Olympiad, 4

Tags: set theory , counting , algebra , closedness

For any natural number $ n\ge 2, $ define $ m(n) $ to be the minimum number of elements of a set $ S $ that simultaneously satisfy: $ \text{(i)}\quad \{ 1,n\} \subset S\subset \{ 1,2,\ldots ,n\} $ $ \text{(ii)}\quad $ any element of $ S, $ distinct from $ 1, $ is equal to the sum of two (not necessarily distinct) elements from $ S. $ [b]a)[/b] Prove that $ m(n)\ge 1+\left\lfloor \log_2 n \right\rfloor ,\quad\forall n\in\mathbb{N}_{\ge 2} . $ [b]b)[/b] Prove that there are infinitely many natural numbers $ n\ge 2 $ such that $ m(n)=m(n+1). $ $ \lfloor\rfloor $ denotes the usual integer part.

2019 India PRMO, 12

Tags: combinatorics , counting , enumeration , enumerative combinatorics

Let $N$ be the number of ways of choosing a subset of $5$ distinct numbers from the set $${10a+b:1\leq a\leq 5, 1\leq b\leq 5}$$ where $a,b$ are integers, such that no two of the selected numbers have the same units digits and no two have the same tens digit. What is the remainder when $N$ is divided by $73$?

1995 AMC 12/AHSME, 29

Tags: counting , distinguishability , number theory , prime number

For how many three-element sets of positive integers $\{a,b,c\}$ is it true that $a \times b \times c = 2310$? $\textbf{(A)}\ 32 \qquad \textbf{(B)}\ 36 \qquad \textbf{(C)}\ 40 \qquad \textbf{(D)}\ 43 \qquad \textbf{(E)}\ 45$

2018 India IMO Training Camp, 2

Tags: combinatorics , counting

A $10$ digit number is called interesting if its digits are distinct and is divisible by $11111$. Then find the number of interesting numbers.

2009 Stanford Mathematics Tournament, 1

Tags: counting , distinguishability

In the future, each country in the world produces its Olympic athletes via cloning and strict training programs. Therefore, in the finals of the 200 m free, there are two indistinguishable athletes from each of the four countries. How many ways are there to arrange them into eight lanes?

2013 Greece Team Selection Test, 4

Tags: combinatorics , counting , circles , line

Given are $n$ different concentric circles on the plane.Inside the disk with the smallest radius (strictly inside it),we consider two distinct points $A,B$.We consider $k$ distinct lines passing through $A$ and $m$ distinct lines passing through $B$.There is no line passing through both $A$ and $B$ and all the lines passing through $k$ intersect with all the lines passing through $B$.The intersections do not lie on some of the circles.Determine the maximum and the minimum number of regions formed by the lines and the circles and are inside the circles.

2014 Korea National Olympiad, 2

Tags: function , counting , derangement , induction , combinatorics

How many one-to-one functions $f : \{1, 2, \cdots, 9\} \rightarrow \{1, 2, \cdots, 9\}$ satisfy (i) and (ii)? (i) $f(1)>f(2)$, $f(9)<9$. (ii) For each $i=3, 4, \cdots, 8$, if $f(1), \cdots, f(i-1)$ are smaller than $f(i)$, then $f(i+1)$ is also smaller than $f(i)$.

1986 IMO Longlists, 28

Tags: probability , combinatorics , counting

A particle moves from $(0, 0)$ to $(n, n)$ directed by a fair coin. For each head it moves one step east and for each tail it moves one step north. At $(n, y), y < n$, it stays there if a head comes up and at $(x, n), x < n$, it stays there if a tail comes up. Let$ k$ be a fixed positive integer. Find the probability that the particle needs exactly $2n+k$ tosses to reach $(n, n).$

2018 Turkey EGMO TST, 3

Tags: combinatorics , coloring , counting

In how many ways every unit square of a $2018$ x $2018$ board can be colored in red or white such that number of red unit squares in any two rows are distinct and number of red squares in any two columns are distinct.

1980 IMO Longlists, 11

Tags: combinatorics , system of equations , counting

Ten gamblers started playing with the same amount of money. Each turn they cast (threw) five dice. At each stage the gambler who had thrown paid to each of his 9 opponents $\frac{1}{n}$ times the amount which that opponent owned at that moment. They threw and paid one after the other. At the 10th round (i.e. when each gambler has cast the five dice once), the dice showed a total of 12, and after payment it turned out that every player had exactly the same sum as he had at the beginning. Is it possible to determine the total shown by the dice at the nine former rounds ?

2007 USA Team Selection Test, 6

Tags: algebra , polynomial , algorithm , modular arithmetic , counting , distinguishability , induction

For a polynomial $ P(x)$ with integer coefficients, $ r(2i \minus{} 1)$ (for $ i \equal{} 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i \minus{} 1)$ is divided by $ 1024$. The sequence \[ (r(1),r(3),\ldots,r(1023)) \] is called the [i]remainder sequence[/i] of $ P(x)$. A remainder sequence is called [i]complete[/i] if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.

1992 India National Olympiad, 7

Tags: combinatorics , counting , chessboard , arithmetic progression

Let $n\geq 3$ be an integer. Find the number of ways in which one can place the numbers $1, 2, 3, \ldots, n^2$ in the $n^2$ squares of a $n \times n$ chesboard, one on each, such that the numbers in each row and in each column are in arithmetic progression.

2008 Germany Team Selection Test, 2

Tags: combinatorics , modular arithmetic , counting , triplets

Find all positive integers $ n$ for which the numbers in the set $ S \equal{} \{1,2, \ldots,n \}$ can be colored red and blue, with the following condition being satisfied: The set $ S \times S \times S$ contains exactly $ 2007$ ordered triples $ \left(x, y, z\right)$ such that: [b](i)[/b] the numbers $ x$, $ y$, $ z$ are of the same color, and [b](ii)[/b] the number $ x \plus{} y \plus{} z$ is divisible by $ n$. [i]Author: Gerhard Wöginger, Netherlands[/i]

1967 IMO Shortlist, 1

Tags: combinatorics , counting

Given $m+n$ numbers: $a_i,$ $i = 1,2, \ldots, m,$ $b_j$, $j = 1,2, \ldots, n,$ determine the number of pairs $(a_i,b_j)$ for which $|i-j| \geq k,$ where $k$ is a non-negative integer.

1980 IMO Shortlist, 11

Tags: combinatorics , system of equations , counting

Ten gamblers started playing with the same amount of money. Each turn they cast (threw) five dice. At each stage the gambler who had thrown paid to each of his 9 opponents $\frac{1}{n}$ times the amount which that opponent owned at that moment. They threw and paid one after the other. At the 10th round (i.e. when each gambler has cast the five dice once), the dice showed a total of 12, and after payment it turned out that every player had exactly the same sum as he had at the beginning. Is it possible to determine the total shown by the dice at the nine former rounds ?

2010 Today's Calculation Of Integral, 602

Tags: calculus , integration , floor function , counting , derangement , function , logarithm

Prove the following inequality. \[\frac{e-1}{n+1}\leqq\int^e_1(\log x)^n dx\leqq\frac{(n+1)e+1}{(n+1)(n+2)}\ (n=1,2,\cdot\cdot\cdot) \] 1994 Kyoto University entrance exam/Science

2016 Canadian Mathematical Olympiad Qualification, 3

Tags: combinatorics , counting

Given an $n \times n \times n$ grid of unit cubes, a cube is [i]good[/i] if it is a sub-cube of the grid and has side length at least two. If a good cube contains another good cube and their faces do not intersect, the first good cube is said to [i]properly[/i] contain the second. What is the size of the largest possible set of good cubes such that no cube in the set properly contains another cube in the set?

1999 IMO Shortlist, 2

Tags: geometry , rectangle , combinatorics , counting

If a $5 \times n$ rectangle can be tiled using $n$ pieces like those shown in the diagram, prove that $n$ is even. Show that there are more than $2 \cdot 3^{k-1}$ ways to file a fixed $5 \times 2k$ rectangle $(k \geq 3)$ with $2k$ pieces. (symmetric constructions are supposed to be different.)

2019 IFYM, Sozopol, 5

Tags: combinatorics , counting

Let $A$ be the number of 2019-digit numbers, that is made of 2 different digits (For example $10\underbrace{1...1}_{2016}0$ is such number). Determine the highest power of 3 that divides $A$.

2006 Pan African, 5

Tags: counting , distinguishability , combinatorics

In how many ways can the integers from $1$ to $2006$ be divided into three non-empty disjoint sets so that none of these sets contains a pair of consecutive integers?

2007 Purple Comet Problems, 15

Tags: counting , distinguishability

We have some identical paper squares which are black on one side of the sheet and white on the other side. We can join nine squares together to make a $3$ by $3$ sheet of squares by placing each of the nine squares either white side up or black side up. Two of these $3$ by $3$ sheets are distinguishable if neither can be made to look like the other by rotating the sheet or by turning it over. How many distinguishable $3$ by $3$ squares can we form?

2002 IMO Shortlist, 3

Tags: combinatorics , counting , bijection

Let $n$ be a positive integer. A sequence of $n$ positive integers (not necessarily distinct) is called [b]full[/b] if it satisfies the following condition: for each positive integer $k\geq2$, if the number $k$ appears in the sequence then so does the number $k-1$, and moreover the first occurrence of $k-1$ comes before the last occurrence of $k$. For each $n$, how many full sequences are there ?

1967 IMO Shortlist, 5

Tags: counting , triangle inequality , combinatorics , triangle

Let $n$ be a positive integer. Find the maximal number of non-congruent triangles whose sides lengths are integers $\leq n.$

2007 District Olympiad, 2

Tags: geometry , rectangle , combinatorics , numbering , counting

All $ 2n\ge 2 $ squares of a $ 2\times n $ rectangle are colored with three colors. We say that a color has a [i]cut[/i] if there is some column (from all $ n $) that has both squares colored with it. Determine: [b]a)[/b] the number of colorings that have no cuts. [b]b)[/b] the number of colorings that have a single cut.