Olympiad problems

2017 Greece Team Selection Test, 2

Prove that the number $A=\frac{(4n)!}{(2n)!n!}$ is an integer and divisible by $2^{n+1}$, where $n$ is a positive integer.

1974 IMO, 3

Tags: binomial coefficient , summation , divisibility , modular arithmetic , number theory

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

2018 China Team Selection Test, 5

Tags: divisibility , binomial coefficient , number theory

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.

1998 Iran MO (3rd Round), 6

Tags: function , symmetry , binomial coefficient , counting , combinatorics

For any two nonnegative integers $n$ and $k$ satisfying $n\geq k$, we define the number $c(n,k)$ as follows: - $c\left(n,0\right)=c\left(n,n\right)=1$ for all $n\geq 0$; - $c\left(n+1,k\right)=2^{k}c\left(n,k\right)+c\left(n,k-1\right)$ for $n\geq k\geq 1$. Prove that $c\left(n,k\right)=c\left(n,n-k\right)$ for all $n\geq k\geq 0$.

2006 AMC 12/AHSME, 25

Tags: probability , counting , distinguishability , binomial coefficient

How many non-empty subsets $ S$ of $ \{1, 2, 3, \ldots, 15\}$ have the following two properties? (1) No two consecutive integers belong to $ S$. (2) If $ S$ contains $ k$ elements, then $ S$ contains no number less than $ k$. $ \textbf{(A) } 277\qquad \textbf{(B) } 311\qquad \textbf{(C) } 376\qquad \textbf{(D) } 377\qquad \textbf{(E) } 405$

1969 IMO Shortlist, 6

Tags: trigonometry , binomial coefficient , combinatorics

$(BEL 6)$ Evaluate $\left(\cos\frac{\pi}{4} + i \sin\frac{\pi}{4}\right)^{10}$ in two different ways and prove that $\dbinom{10}{1}-\dbinom{10}{3}+\frac{1}{2}\dbinom{10}{5}=2^4$

2009 China Team Selection Test, 3

Tags: algebra , polynomial , binomial coefficient , induction , modular arithmetic

Let $ f(x)$ be a $ n \minus{}$degree polynomial all of whose coefficients are equal to $ \pm 1$, and having $ x \equal{} 1$ as its $ m$ multiple root. If $ m\ge 2^k (k\ge 2,k\in N)$, then $ n\ge 2^{k \plus{} 1} \minus{} 1.$

2022 China Team Selection Test, 5

Tags: number theory , binomial coefficient , divisor

Given a positive integer $n$, let $D$ is the set of positive divisors of $n$, and let $f: D \to \mathbb{Z}$ be a function. Prove that the following are equivalent: (a) For any positive divisor $m$ of $n$, \[ n ~\Big|~ \sum_{d|m} f(d) \binom{n/d}{m/d}. \] (b) For any positive divisor $k$ of $n$, \[ k ~\Big|~ \sum_{d|k} f(d). \]

1985 IMO Longlists, 59

Tags: polynomial , combinatorics , binomial coefficient , combinatorial inequality , pascal triangle

For any polynomial $P(x)=a_0+a_1x+\ldots+a_kx^k$ with integer coefficients, the number of odd coefficients is denoted by $o(P)$. For $i-0,1,2,\ldots$ let $Q_i(x)=(1+x)^i$. Prove that if $i_1,i_2,\ldots,i_n$ are integers satisfying $0\le i_1<i_2<\ldots<i_n$, then: \[ o(Q_{i_{1}}+Q_{i_{2}}+\ldots+Q_{i_{n}})\ge o(Q_{i_{1}}). \]

2021 BMT, 9

Tags: binomial coefficient , number theory

Let $p=101.$ The sum \[\sum_{k=1}^{10}\frac1{\binom pk}\] can be written as a fraction of the form $\dfrac a{p!},$ where $a$ is a positive integer. Compute $a\pmod p.$

2016 German National Olympiad, 4

Tags: binomial coefficient

Find all positive integers $m,n$ with $m \leq 2n$ that solve the equation \[ m \cdot \binom{2n}{n} = \binom{m^2}{2}. \] [i](German MO 2016 - Problem 4)[/i]

2005 iTest, 33

Tags: algebra , binomial coefficient , binomial

If the coefficient of the third term in the binomial expansion of $(1 - 3x)^{1/4}$ is $-a/b$, where $ a$ and $b$ are relatively prime integers, find $a+b$.

2014 AMC 12/AHSME, 13

Tags: counting , distinguishability , complementary counting , binomial coefficient

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$

2017 India National Olympiad, 6

Tags: algebra , binomial coefficient , geometry , binomial theorem , heron's formula , integer

Let $n\ge 1$ be an integer and consider the sum $$x=\sum_{k\ge 0} \dbinom{n}{2k} 2^{n-2k}3^k=\dbinom{n}{0}2^n+\dbinom{n}{2}2^{n-2}\cdot{}3+\dbinom{n}{4}2^{n-k}\cdot{}3^2 + \cdots{}.$$ Show that $2x-1,2x,2x+1$ form the sides of a triangle whose area and inradius are also integers.

1998 Nordic, 4

Tags: modular arithmetic , binomial coefficient , combinatorics

Let $n$ be a positive integer. Count the number of numbers $k \in \{0, 1, 2, . . . , n\}$ such that $\binom{n}{k}$ is odd. Show that this number is a power of two, i.e. of the form $2^p$ for some nonnegative integer $p$.

1967 IMO, 3

Tags: number theory , divisibility , binomial coefficient

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$.

1972 Putnam, A1

Tags: binomial coefficient , arithmetic sequence

Show that $\binom{n}{m},\binom{n}{m+1},\binom{n}{m+2}$ and $\binom{n}{m+3}$ cannot be in arithmetic progression, where $n,m>0$ and $n\geq m+3$.

2011 Indonesia TST, 2

Tags: limit , combinatorics , binomial coefficient

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}$$

1967 IMO Longlists, 17

Tags: number theory , divisibility , binomial coefficient

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$.

2013 Peru IMO TST, 5

Tags: number theory , prime number , binomial coefficient

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}$.

2020 Greece Team Selection Test, 3

Tags: trivial , binomial coefficient , combinatorics

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$).

2024 JHMT HS, 15

Tags: number theory , combinatorics , binomial coefficient

Let $\ell = 1$, $M = 23$, $N = 45$, and $u = 67$. Compute the number of ordered pairs of nonnegative integers $(X, Y)$ with $X \leq M - \ell$ and $Y \leq N + u$ such that the sum \[ \sum_{k=\ell}^{u} \binom{X + k}{M}\cdot\binom{Y - k}{N} \] is divisible by $89$ (for integers $a$ and $b$, define the binomial coefficient $\tbinom{a}{b}$ to be the number of $b$-element subsets of any given $a$-element set, which is $0$ when $a < 0$, $b < 0$, or $b > a$).

1996 Romania National Olympiad, 1

Tags: binomial coefficient , algebra , sum

For $n ,p \in N^*$ , $ 1 \le p \le n$, we define $$ R_n^p = \sum_{k=0}^p (p-k)^n(-1)^k C_{n+1}^k $$ Show that: $R_n^{n-p+1} =R_n^p$ .

1996 VJIMC, Problem 2

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

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$$

1980 Polish MO Finals, 6

Tags: algebra , binomial coefficient

Prove that for every natural number $n$ we have $$\sum_{s=n}^{2n} 2^{2n-s}{s \choose n}= 2^{2n}.$$