Olympiad problems

1997 IMO Shortlist, 24

For each positive integer $ n$, let $ f(n)$ denote the number of ways of representing $ n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $ f(4) \equal{} 4$, because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1. Prove that, for any integer $ n \geq 3$ we have $ 2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}$.

1978 Romania Team Selection Test, 1

Tags: counting

Prove that for every partition of $ \{ 1,2,3,4,5,6,7,8,9\} $ into two subsets, one of the subsets contains three numbers such that the sum of two of them is equal to the double of the third.

1989 IMO Shortlist, 23

Tags: combinatorics , counting , injective function , combinatorial inequality

A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.

2006 Tournament of Towns, 2

Tags: counting

Prove that one can find 100 distinct pairs of integers such that every digit of each number is no less than 6 and the product of the numbers in each pair is also a number with all its digits being no less than 6. [i](4 points)[/i]

1983 IMO Shortlist, 13

Tags: combinatorics , coloring , counting , 3d geometry , geometry

Let $E$ be the set of $1983^3$ points of the space $\mathbb R^3$ all three of whose coordinates are integers between $0$ and $1982$ (including $0$ and $1982$). A coloring of $E$ is a map from $E$ to the set {red, blue}. How many colorings of $E$ are there satisfying the following property: The number of red vertices among the $8$ vertices of any right-angled parallelepiped is a multiple of $4$ ?

1974 Bundeswettbewerb Mathematik, 3

Tags: combinatorics , counting , subset

Let $M$ be a set with $n$ elements. How many pairs $(A, B)$ of subsets of $M$ are there such that $A$ is a subset of $B?$

2000 AIME Problems, 5

Tags: counting , distinguishability , function

Given eight distinguishable rings, let $n$ be the number of possible five-ring arrangements on the four fingers (not the thumb) of one hand. The order of rings on each finger is significant, but it is not required that each finger have a ring. Find the leftmost three nonzero digits of $n.$

1969 IMO, 5

Tags: combinatorics , combinatorial geometry , counting , convex quadrilateral

Given $n>4$ points in the plane, no three collinear. Prove that there are at least $\frac{(n-3)(n-4)}{2}$ convex quadrilaterals with vertices amongst the $n$ points.

1992 IMO Longlists, 72

Tags: combinatorics , counting , inclusion-exclusion

In a school six different courses are taught: mathematics, physics, biology, music, history, geography. The students were required to rank these courses according to their preferences, where equal preferences were allowed. It turned out that: [list] [*][b](i)[/b] mathematics was ranked among the most preferred courses by all students; [*][b](ii)[/b] no student ranked music among the least preferred ones; [*][b](iii) [/b]all students preferred history to geography and physics to biology; and [*][b](iv)[/b] no two rankings were the same. [/list] Find the greatest possible value for the number of students in this school.

Russian TST 2018, P1

Tags: combinatorics , counting

There are 2018 points marked on a sphere. A zebra wants to paint each point white or black and, perhaps, connect some pairs of points of different colors with a segment. Find the residue modulo 5 of the number of ways to do this.

2019 AMC 12/AHSME, 13

Tags: counting

How many ways are there to paint each of the integers $2, 3, \dots, 9$ either red, green, or blue so that each number has a different color from each of its proper divisors? $\textbf{(A)}\ 144\qquad\textbf{(B)}\ 216\qquad\textbf{(C)}\ 256\qquad\textbf{(D)}\ 384\qquad\textbf{(E)}\ 432$

2020-21 IOQM India, 27

Tags: counting , combinatorics , enumerative combinatorics

Q.A bug travels in the co-ordinate plane moving along only the lines that are parallel to the $X$ and $Y$ axes.Let $A=(-3, 2)$ and $B = (3, -2)$. Consider all possible paths of the bug from $A$ to $B$.How many lattice points lie on at least one of these paths. My answer ($87$)

1982 Dutch Mathematical Olympiad, 3

Tags: probability , counting , distinguishability , combinatorics

Five marbles are distributed at a random among seven urns. What is the expected number of urns with exactly one marble?

2023 Bulgaria JBMO TST, 2

Tags: counting , combinatorics

On the coast of a circular island there are eight different cities. Initially there are no routes between the cities. We have to construct five straight two-way routes, which do not intersect, so that from each city there are one or two routes. In how many ways can this happen?

2011 Belarus Team Selection Test, 3

Tags: poset , linear extensions , counting , combinatorics

In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied? [i]Proposed by Gerhard Wöginger, Austria[/i]

2003 AIME Problems, 13

Tags: probability , counting , distinguishability , modular arithmetic , function , limit , vector

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$

1990 IMO Longlists, 10

Tags: combinatorics , counting , pigeonhole principle

Let $p, k$ and $x$ be positive integers such that $p \geq k$ and $x < \left[ \frac{p(p-k+1)}{2(k-1)} \right]$, where $[q]$ is the largest integer no larger than $q$. Prove that when $x$ balls are put into $p$ boxes arbitrarily, there exist $k$ boxes with the same number of balls.

1987 IMO, 1

Tags: permutation , counting , derangement , combinatorics , double counting

Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.

1997 AMC 8, 20

Tags: probability , counting , distinguishability

A pair of 8-sided dice have sides numbered 1 through 8. Each side has the same probability (chance) of landing face up. The probability that the product of the two numbers that land face-up exceeds 36 is $\textbf{(A)}\ \dfrac{5}{32} \qquad \textbf{(B)}\ \dfrac{11}{64} \qquad \textbf{(C)}\ \dfrac{3}{16} \qquad \textbf{(D)}\ \dfrac{1}{4} \qquad \textbf{(E)}\ \dfrac{1}{2}$

2023 Brazil EGMO Team Selection Test, 4

Tags: graph theory , counting , combinatorics

In the reality show [i]Big Sister Brasil[/i], it is said that there is a [i]treta[/i] if two people are friends with each other and enemies with a third one. For audience purposes, the broadcaster wants a lot of [i]tretas[/i]. If friendship and enmity are reciprocal relationships, given $n$ people, what is the maximum number of [i]tretas[/i]?

2020 LIMIT Category 1, 15

Tags: chessboard , counting , limit

In a $4\times 4$ chessboard, in how many ways can you place $3$ rooks and one bishop such that none of these pieces threaten another piece?

1973 IMO Shortlist, 8

Tags: binomial coefficient , combinatorics , counting , sequence

Prove that there are exactly $\binom{k}{[k/2]}$ arrays $a_1, a_2, \ldots , a_{k+1}$ of nonnegative integers such that $a_1 = 0$ and $|a_i-a_{i+1}| = 1$ for $i = 1, 2, \ldots , k.$

1992 IMO Longlists, 61

Tags: combinatorics , chessboard , counting , algorithm

There are a board with $2n \cdot 2n \ (= 4n^2)$ squares and $4n^2-1$ cards numbered with different natural numbers. These cards are put one by one on each of the squares. One square is empty. We can move a card to an empty square from one of the adjacent squares (two squares are adjacent if they have a common edge). Is it possible to exchange two cards on two adjacent squares of a column (or a row) in a finite number of movements?

2003 IMO Shortlist, 6

Tags: modular arithmetic , combinatorics , decimal representation , counting , function

Let $f(k)$ be the number of integers $n$ satisfying the following conditions: (i) $0\leq n < 10^k$ so $n$ has exactly $k$ digits (in decimal notation), with leading zeroes allowed; (ii) the digits of $n$ can be permuted in such a way that they yield an integer divisible by $11$. Prove that $f(2m) = 10f(2m-1)$ for every positive integer $m$. [i]Proposed by Dirk Laurie, South Africa[/i]

2021 Francophone Mathematical Olympiad, 2

Tags: coloring , combinatorics , graph theory , counting

Evariste has drawn twelve triangles as follows, so that two consecutive triangles share exactly one edge. [img]https://cdn.artofproblemsolving.com/attachments/6/2/50377e7ad5fb1c40e36725e43c7eeb1e3c2849.png[/img] Sophie colors every triangle side in red, green or blue. Among the $3^{24}$ possible colorings, how many have the property that every triangle has one edge of each color?