Olympiad problems

2014 VJIMC, Problem 3

Let $k$ be a positive even integer. Show that $$\sum_{n=0}^{k/2}(-1)^n\binom{k+2}n\binom{2(k-n)+1}{k+1}=\frac{(k+1)(k+2)}2.$$

2011 Indonesia TST, 2

Tags: binomial coefficient , limit , combinatorics

Find the limit, when $n$ tends to the infinity, of $$\frac{\sum_{k=0}^{n} {{2n} \choose {2k}} 3^k} {\sum_{k=0}^{n-1} {{2n} \choose {2k+1}} 3^k}$$

2025 Romania EGMO TST, P4

Tags: binomial coefficient , number theory , least common multiple

How does one show $$\text{lcm}\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n}\right)=\frac{\text{lcm}(1,2,\ldots,n+1)}{n+1}$$

1975 IMO Shortlist, 7

Tags: binomial coefficient , algebra , summation , binomial coefficient identity , combinatorics

Prove that from $x + y = 1 \ (x, y \in \mathbb R)$ it follows that \[x^{m+1} \sum_{j=0}^n \binom{m+j}{j} y^j + y^{n+1} \sum_{i=0}^m \binom{n+i}{i} x^i = 1 \qquad (m, n = 0, 1, 2, \ldots ).\]

2014 AMC 12/AHSME, 13

Tags: binomial coefficient , counting , distinguishability , complementary counting

A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that night. The friends can room in any combination they wish, but with no more than $2$ friends per room. In how many ways can the innkeeper assign the guests to the rooms? $\textbf{(A) }2100\qquad \textbf{(B) }2220\qquad \textbf{(C) }3000\qquad \textbf{(D) }3120\qquad \textbf{(E) }3125\qquad$

2019 Pan-African Shortlist, N6

Tags: binomial coefficient , number theory

Find the $2019$th strictly positive integer $n$ such that $\binom{2n}{n}$ is not divisible by $5$.

2020 Estonia Team Selection Test, 1

Tags: combinatorics , binomial coefficient , trivial

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

2018 China Team Selection Test, 5

Tags: binomial coefficient , number theory , divisibility

Given a positive integer $k$, call $n$ [i]good[/i] if among $$\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n}$$ at least $0.99n$ of them are divisible by $k$. Show that exists some positive integer $N$ such that among $1,2,...,N$, there are at least $0.99N$ good numbers.

2013 Peru IMO TST, 5

Tags: binomial coefficient , number theory , prime number

Determine all integers $m \geq 2$ such that every $n$ with $\frac{m}{3} \leq n \leq \frac{m}{2}$ divides the binomial coefficient $\binom{n}{m-2n}$.

1965 Putnam, A2

Tags: binomial coefficient

Show that, for any positive integer $n$, \[ \sum_{r=0}^{[(n-1)/2]}\left\{\frac{n-2r}n\binom nr\right\}^2 = \frac 1n\binom{2n-2}{n-1}, \] where $[x]$ means the greatest integer not exceeding $x$, and $\textstyle\binom nr$ is the binomial coefficient "$n$ choose $r$", with the convention $\textstyle\binom n0 = 1$.

1996 VJIMC, Problem 2

Tags: binomial coefficient , summation , binomial , number theory , algebra

Let $\{x_n\}^\infty_{n=0}$ be the sequence such that $x_0=2$, $x_1=1$ and $x_{n+2}$ is the remainder of the number $x_{n+1}+x_n$ divided by $7$. Prove that $x_n$ is the remainder of the number $$4^n\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}2\binom n{2k}5^k$$

1967 IMO Shortlist, 1

Tags: binomial coefficient , number theory , divisibility

Let $k,m,n$ be natural numbers such that $m+k+1$ is a prime greater than $n+1$. Let $c_s=s(s+1)$. Prove that \[(c_{m+1}-c_k)(c_{m+2}-c_k)\ldots(c_{m+n}-c_k)\] is divisible by the product $c_1c_2\ldots c_n$.

2020 Greece Team Selection Test, 3

Tags: binomial coefficient , combinatorics , trivial

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

2014 Greece Team Selection Test, 4

Tags: binomial coefficient , combinatorics

Square $ABCD$ is divided into $n^2$ equal small squares by lines parallel to its sides.A spider starts from $A$ and moving only rightward or upwards,tries to reach $C$.Every "movement" of the spider consists of $k$ steps rightward and $m$ steps upwards or $m$ steps rightward and $k$ steps upwards(it can follow any possible order for the steps of each "movement").The spider completes $l$ "movements" and afterwards it moves without limitation (it still moves rightwards and upwards only).If $n=m\cdot l$,find the number of the possible paths the spider can follow to reach $C$.Note that $n,m,k,l\in \mathbb{N^{*}}$ with $k<m$.

Kvant 2023, M2736

Tags: binomial coefficient , number theory

Find the remainder of $\binom{3^n}{2^n}$ modulo $3^{n+1}$. [i]Proposed by V. Rastorguev[/i]

2019 Pan-African, 6

Tags: binomial coefficient , number theory

Find the $2019$th strictly positive integer $n$ such that $\binom{2n}{n}$ is not divisible by $5$.

1994 Hong Kong TST, 2

Tags: binomial coefficient , combinatorics

In a table-tennis tournament of $10$ contestants, any $2$ contestants meet only once. We say that there is a winning triangle if the following situation occurs: $i$-th contestant defeated the $j$-th contestant, $j$-th contestant defeated the $k$-th contestant, and, $k$-th contestant defeated the $i$-th contestant. Let, $W_i$ and $L_i $ be respectively the number of games won and lost by the $i$-th contestant. Suppose, $L_i+W_j\geq 8$ whenever the $j$-th contestant defeats the $i$-th contestant. Prove that, there are exactly $40$ winning triangles in this tournament.