Found problems: 167
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]
Evaluate
$$ \sum_{k=0}^{n} \binom{n}{k}k^{2}.$$
Let all positive integers $n$ satisfy the following condition:
for each non-negative integers $k, m$ with $k + m \le n$,
the numbers $\binom{n-k}{m}$ and $\binom{n-m}{k}$ leave the same remainder when divided by $2$.
(Poland)
PS. The translation was done using Google translate and in case it is not right, there is the original text in Slovak
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$.
Consider an arithmetic progression $a_0,\ldots,a_n$ with $n\ge2$. Prove that $$\sum_{k=0}^n(-1)^k\binom{n}{k}a_k=0.$$
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$).
Evaluate $\sum_{k=0}^{37}(-1)^k\binom{75}{2k}$.
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}}). \]
Suppose that $m=nq$, where $n$ and $q$ are positive integers. Prove that the sum of binomial coefficients \[\sum_{k=0}^{n-1}{ \gcd(n, k)q \choose \gcd(n, k)}\] is divisible by $m$.
Prove that for a prime $p$, $x^{p-1}+x^{p-2}+ \cdots +x+1$ is irreducible in $\mathbb{Q}[x]$.
Find the coefficient of the fourth term of the expansion of $(x+y)^{15}$.
For every integer $ k \geq 2,$ prove that $ 2^{3k}$ divides the number
\[ \binom{2^{k \plus{} 1}}{2^{k}} \minus{} \binom{2^{k}}{2^{k \minus{} 1}}
\]
but $ 2^{3k \plus{} 1}$ does not.
[i]Author: Waldemar Pompe, Poland[/i]
Let $n>r\geqslant 3$ be two integers and $d$ be a positive integer such that $nd\geqslant \dbinom{n+r}{r+1}$. Show that \[(n-t)(d-t)>\dbinom{n-t+r}{r+1},\] for $t=1,2,\ldots,n-1$
[i]Vasile Brânzănescu[/i]
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$.
Given
$$b_n = \sum_{k=0}^{n} \binom{n}{k}^{-1}, \;\; n\geq 1,$$
prove that
$$b_n = \frac{n+1}{2n} b_{n-1} +1, \;\; n \geq 2.$$
Hence, as a corollary, show
$$ \lim_{n \to \infty} b_n =2.$$
Prove that for every natural number $n$ we have $$\sum_{s=n}^{2n} 2^{2n-s}{s \choose n}= 2^{2n}.$$
For every integer $ k \geq 2,$ prove that $ 2^{3k}$ divides the number
\[ \binom{2^{k \plus{} 1}}{2^{k}} \minus{} \binom{2^{k}}{2^{k \minus{} 1}}
\]
but $ 2^{3k \plus{} 1}$ does not.
[i]Author: Waldemar Pompe, Poland[/i]
Take $r$ such that $1\le r\le n$, and consider all subsets of $r$ elements of the set $\{1,2,\ldots,n\}$. Each subset has a smallest element. Let $F(n,r)$ be the arithmetic mean of these smallest elements. Prove that: \[ F(n,r)={n+1\over r+1}. \]
Let $n$ be a positive integer. A regular hexagon with side length $n$ is divided into equilateral triangles with side length $1$ by lines parallel to its sides.
Find the number of regular hexagons all of whose vertices are among the vertices of those equilateral triangles.
[i]UK - Sahl Khan[/i]
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.
Prove that for any prime $p\ge5$, the number
$$\sum_{0<k<\frac{2p}3}\binom pk$$is divisible by $p^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.
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$
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$.
Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.