Olympiad problems

Kvant 2019, M2572

Let $k$ be a fixed positive integer. Prove that the sequence $\binom{2}{1},\binom{4}{2},\binom{8}{4},\ldots, \binom{2^{n+1}}{2^n},\ldots$ is eventually constant modulo $2^k$. [i]Proposed by V. Rastorguyev[/i]

2019 IMO Shortlist, C1

Tags: combinatorics , binomial coefficients , IMO Shortlist , IMO Shortlist 2019 , trivial , Hi

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

2015 Romania Team Selection Tests, 3

Tags: Sequence , binomial coefficients , congruence , number theory , Romanian TST

Define a sequence of integers by $a_0=1$ , and $a_n=\sum_{k=0}^{n-1} \binom{n}{k}a_k$ , $n \geq 1$ . Let $m$ be a positive integer , let $p$ be a prime , and let $q$ and $r$ be non-negative integers . Prove that : $$a_{p^mq+r} \equiv a_{p^{m-1}q+r} \pmod{p^m}$$

1999 IMO Shortlist, 1

Tags: binomial coefficients , algebra , counting , combinatorics , IMO Shortlist

Let $n \geq 1$ be an integer. A [b]path[/b] from $(0,0)$ to $(n,n)$ in the $xy$ plane is a chain of consecutive unit moves either to the right (move denoted by $E$) or upwards (move denoted by $N$), all the moves being made inside the half-plane $x \geq y$. A [b]step[/b] in a path is the occurence of two consecutive moves of the form $EN$. Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps $(n \geq s \geq 1)$ is \[\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.\]

1979 Romania Team Selection Tests, 6.

Tags: algebra , binomial coefficients

If $n>2$ is a positive integer, compute \[\max_{1\leqslant k\leqslant n}\max_{n_1+...+n_k=n} \binom{n_1}{2}\binom{n_2}{2}\ldots\binom{n_k}{2}.\] [i]Ioan Tomescu[/i]

2018 CMIMC Number Theory, 5

Tags: binomial coefficients , number theory

It is given that there exist unique integers $m_1,\ldots, m_{100}$ such that \[0\leq m_1 < m_2 < \cdots < m_{100}\quad\text{and}\quad 2018 = \binom{m_1}1 + \binom{m_2}2 + \cdots + \binom{m_{100}}{100}.\] Find $m_1 + m_2 + \cdots + m_{100}$.

1980 AMC 12/AHSME, 20

Tags: probability , binomial coefficients

A box contains 2 pennies, 4 nickels, and 6 dimes. Six coins are drawn without replacement, with each coin having an equal probability of being chosen. What is the probability that the value of coins drawn is at least 50 cents? $\text{(A)} \ \frac{37}{924} \qquad \text{(B)} \ \frac{91}{924} \qquad \text{(C)} \ \frac{127}{924} \qquad \text{(D)} \ \frac{132}{924} \qquad \text{(E)} \ \text{none of these}$

1956 Putnam, A5

Tags: Putnam , binomial coefficients , combinatorics

Call a subset of $\{1,2,\ldots, n\}$ [i]unfriendly[/i] if no two of its elements are consecutive. Show that the number of unfriendly subsets with $k$ elements is $\binom{n-k+1}{k}.$

1967 IMO Shortlist, 1

Tags: number theory , Divisibility , binomial coefficients , IMO , IMO 1967

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 Switzerland Team Selection Test, 11

Tags: combinatorics , binomial coefficients , IMO Shortlist , IMO Shortlist 2019 , trivial , Hi

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

Kvant 2023, M2736

Tags: number theory , binomial coefficients

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

2015 Postal Coaching, Problem 2

Tags: algebra , polynomial , function , binomial coefficients , generating functions , IMO Shortlist

Let $ n$ be a positive integer. Find the number of odd coefficients of the polynomial \[ u_n(x) \equal{} (x^2 \plus{} x \plus{} 1)^n. \]

2014 Contests, 1

Tags: inequalities , algebra , polynomial , binomial coefficients , binomial theorem , AMC

Let $a$, $b$, $c$ be real numbers greater than or equal to $1$. Prove that \[ \min \left(\frac{10a^2-5a+1}{b^2-5b+10},\frac{10b^2-5b+1}{c^2-5c+10},\frac{10c^2-5c+1}{a^2-5a+10}\right )\leq abc. \]

2010 Princeton University Math Competition, 8

Tags: binomial coefficients

Let $N$ be the sum of all binomial coefficients $\binom{a}{b}$ such that $a$ and $b$ are nonnegative integers and $a+b$ is an even integer less than 100. Find the remainder when $N$ is divided by 144. (Note: $\binom{a}{b} = 0$ if $a<b$, and $\binom{0}{0} = 1$.)

1972 IMO, 3

Tags: factorial , number theory , binomial coefficients , recurrence relation , IMO , IMO 1972

Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.

2008 IMO Shortlist, 4

Tags: number theory , binomial coefficients , modular arithmetic , IMO Shortlist , Hi

Let $ n$ be a positive integer. Show that the numbers \[ \binom{2^n \minus{} 1}{0},\; \binom{2^n \minus{} 1}{1},\; \binom{2^n \minus{} 1}{2},\; \ldots,\; \binom{2^n \minus{} 1}{2^{n \minus{} 1} \minus{} 1}\] are congruent modulo $ 2^n$ to $ 1$, $ 3$, $ 5$, $ \ldots$, $ 2^n \minus{} 1$ in some order. [i]Proposed by Duskan Dukic, Serbia[/i]

1991 IMTS, 2

Tags: binomial coefficients , algebra unsolved , algebra

Find all pairs of integers, $n$ and $k$, $2 < k < n$, such that the binomial coefficients \[\binom{n}{k-1}, \binom{n}{k}, \binom{n}{k+1}\] form an increasing arithmetic series.

1990 IMO Longlists, 2

Tags: combinatorics , series summation , binomial coefficients , Summation , Combinatorial Identity , IMO Shortlist

Prove that $ \sum_{k \equal{} 0}^{995} \frac {( \minus{} 1)^k}{1991 \minus{} k} {1991 \minus{} k \choose k} \equal{} \frac {1}{1991}$

2005 iTest, 33

Tags: algebra , Binomial , binomial coefficients

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

1972 IMO Longlists, 15

Tags: factorial , number theory , binomial coefficients , recurrence relation , IMO , IMO 1972

Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.

2012 Iran Team Selection Test, 2

Tags: function , induction , ceiling function , binomial coefficients , algebra proposed , algebra

The function $f:\mathbb R^{\ge 0} \longrightarrow \mathbb R^{\ge 0}$ satisfies the following properties for all $a,b\in \mathbb R^{\ge 0}$: [b]a)[/b] $f(a)=0 \Leftrightarrow a=0$ [b]b)[/b] $f(ab)=f(a)f(b)$ [b]c)[/b] $f(a+b)\le 2 \max \{f(a),f(b)\}$. Prove that for all $a,b\in \mathbb R^{\ge 0}$ we have $f(a+b)\le f(a)+f(b)$. [i]Proposed by Masoud Shafaei[/i]

2014 VJIMC, Problem 3

Tags: Summation , binomial coefficients , algebra

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

2023 Brazil Undergrad MO, 2

Tags: function , real analysis , Convergence , binomial coefficients

Let $a_n = \frac{1}{\binom{2n}{n}}, \forall n \leq 1$. a) Show that $\sum\limits_{n=1}^{+\infty}a_nx^n$ converges for all $x \in (-4, 4)$ and that the function $f(x) = \sum\limits_{n=1}^{+\infty}a_nx^n$ satisfies the differential equation $x(x - 4)f'(x) + (x + 2)f(x) = -x$. b) Prove that $\sum\limits_{n=1}^{+\infty}\frac{1}{\binom{2n}{n}} = \frac{1}{3} + \frac{2\pi\sqrt{3}}{27}$.

1975 IMO Shortlist, 7

Tags: algebra , Summation , binomial coefficients , Binomial coefficient identity , combinatorics , IMO Shortlist

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 ).\]

2020 IMC, 8

Tags: IMC , real analysis , binomial coefficients , logarithms , IMC 2020

Compute $\lim\limits_{n \to \infty} \frac{1}{\log \log n} \sum\limits_{k=1}^n (-1)^k \binom{n}{k} \log k.$