Found problems: 167
For an odd prime $ p, $ show that $ \sum_{k=1}^{p-1} \frac{k^p-k}{p}\equiv \frac{1+p}{2}\pmod p . $
Let $a,b,c$ be 3 integers, $b$ odd, and define the sequence $\{x_n\}_{n\geq 0}$ by $x_0=4$, $x_1=0$, $x_2=2c$, $x_3=3b$ and for all positive integers $n$ we have
\[ x_{n+3} = ax_{n-1}+bx_n + cx_{n+1} . \]
Prove that for all positive integers $m$, and for all primes $p$ the number $x_{p^m}$ is divisible by $p$.
In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$
There are no integers $ a,b,c $ that satisfy $ \left( a+b\sqrt{-3}\right)^{17}=c+\sqrt{-3} . $
[i]Dorin Andrica, Mihai Piticari[/i]
In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$
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}.\]
Given $n$ chairs around a circle which are marked with numbers from 1 to $n$ .There are $k$, $k \leq 4 \cdot n$ students sitting on those chairs .Two students are called neighbours if there is no student sitting between them. Between two neighbours students ,there are at less 3 chairs. Find the number of choices of $k$ chairs so that $k$ students can sit on those and the condition is satisfied.
Let $q=p^r$ for a prime number $p$ and positive integer $r$. Let $\zeta = e^{\frac{2\pi i}{q}}$. Find the least positive integer $n$ such that
\[\sum_{\substack{1\leq k\leq q\\ \gcd(k,p)=1}} \frac{1}{(1-\zeta^k)^n}\]
is not an integer. (The sum is over all $1\leq k\leq q$ with $p$ not dividing $k$.)
[i]Victor Wang[/i]
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}}). \]
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$.
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}.$
For $n \geq 3$ and $a_{1} \leq a_{2} \leq \ldots \leq a_{n}$ given real numbers we have the following instructions:
- place out the numbers in some order in a ring;
- delete one of the numbers from the ring;
- if just two numbers are remaining in the ring: let $S$ be the sum of these two numbers. Otherwise, if there are more the two numbers in the ring, replace
Afterwards start again with the step (2). Show that the largest sum $S$ which can result in this way is given by the formula
\[S_{max}= \sum^n_{k=2} \begin{pmatrix} n -2 \\
[\frac{k}{2}] - 1\end{pmatrix}a_{k}.\]
Find the smallest positive integer $n$ for which the number \[ A_n = \prod_{k=1}^n \binom{k^2}{k} = \binom{1}{1} \binom{4}{2} \cdots \binom{n^2}{n} \] ends in the digit $0$ when written in base ten.
[i]Proposed by Evan Chen[/i]
For what positive integers $n, k$ (with $k < n$) are the binomial coefficients $${n \choose k- 1} \,\,\, , \,\,\, {n \choose k} \,\,\, , \,\,\, {n \choose k + 1}$$ three successive terms of an arithmetic progression?
Let $n \geq 2$ be a given integer
$a)$ Prove that one can arrange all the subsets of the set $\{1,2... ,n\}$ as a sequence of subsets $A_{1}, A_{2},\cdots , A_{2^{n}}$, such that $|A_{i+1}| = |A_{i}| + 1$ or $|A_{i}| - 1$ where $i = 1,2,3,\cdots , 2^{n}$ and $A_{2^{n} + 1} = A_{1}$
$b)$ Determine all possible values of the sum $\sum \limits_{i = 1}^{2^n} (-1)^{i}S(A_{i})$ where $S(A_{i})$ denotes the sum of all elements in $A_{i}$ and $S(\emptyset) = 0$, for any subset sequence $A_{1},A_{2},\cdots ,A_{2^n}$ satisfying the condition in $a)$
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}$$
$(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$
Prove that exists integer $n > 2003$ that in sequence
$\binom{n}{0}$, $\binom{n}{1}$, $\binom{n}{2}$, ..., $\binom{n}{2003}$
each element is a divisor of all elements which are after him.
Let $p_n$ denote the $n^{\text{th}}$ prime number and define $a_n=\lfloor p_n\nu\rfloor$ for all positive integers $n$ where $\nu$ is a positive irrational number. Is it possible that there exist only finitely many $k$ such that $\binom{2a_k}{a_k}$ is divisible by $p_i^{10}$ for all $i=1,2,\ldots,2020?$
[i]Proposed by Superguy and ayan.nmath[/i]
Find the remainder of $\binom{3^n}{2^n}$ modulo $3^{n+1}$.
[i]Proposed by V. Rastorguev[/i]
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}$.
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. \]
The figure shows a network of roads bounding $12$ blocks. Person $P$ goes from $A$ to $B,$ and person $Q$ goes from $B$ to $A,$ each going by a shortest path (along roads). The persons start simultaneously and go at the same constant speed. At each point with two possible directions to take, both have the same probability. Find the probability that the persons meet.
[asy]
import graph; size(150); real lsf = 0.5; pen dp = linewidth(0.7) + fontsize(10); defaultpen(dp); pen ds = black;
draw((0,3)--(4,3),linewidth(1.2pt)); draw((4,3)--(4,0),linewidth(1.2pt)); draw((4,0)--(0,0),linewidth(1.2pt)); draw((0,0)--(0,3),linewidth(1.2pt)); draw((1,3)--(1,0),linewidth(1.2pt)); draw((2,3)--(2,0),linewidth(1.2pt)); draw((3,3)--(3,0),linewidth(1.2pt)); draw((0,1)--(4,1),linewidth(1.2pt)); draw((4,2)--(0,2),linewidth(1.2pt));
dot((0,0),ds); label("$A$", (-0.3,-0.36),NE*lsf); dot((4,3),ds); label("$B$", (4.16,3.1),NE*lsf); clip((-4.3,-10.94)--(-4.3,6.3)--(16.18,6.3)--(16.18,-10.94)--cycle);
[/asy]
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$.
Three boxes contain 600 balls each. The first box contains 600 identical red balls, the second box contains 600 identical white balls and the third box contains 600 identical blue balls. From these three boxes, 900 balls are chosen. In how many ways can the balls be chosen? For example, one can choose 250 red balls, 187 white balls and 463 balls, or one can choose 360 red balls and 540 blue balls.