Found problems: 167
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. \]
Compute the prime factorization of $1007021035035021007001$. (You should write your answer in the form $p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}$ where $p_1,\ldots,p_k$ are distinct prime numbers and $e_1,\ldots,e_k$ are positive integers.)
For every integer $n \ge 1$, the function $f_n : \left\{ 0, 1, \cdots, n \right\} \to \mathbb R$ is defined recursively by $f_n(0) = 0$, $f_n(1) = 1$ and \[ (n-k) f_n(k-1) + kf_n(k+1) = nf_n(k) \] for each $1 \le k < n$. Let $S_N = f_{N+1}(1) + f_{N+2}(2) + \cdots + f_{2N} (N)$. Find the remainder when $\left\lfloor S_{2013} \right\rfloor$ is divided by $2011$. (Here $\left\lfloor x \right\rfloor$ is the greatest integer not exceeding $x$.)
[i]Proposed by Lewis Chen[/i]
Prove that for any natural numbers $n,r$ with $r + 3 \le n $the binomial coefficients $n \choose r$, $n \choose r+1$, $n \choose r+2 $, $n \choose r+3 $ cannot be successive terms of an arithmetic progression.
Let $m, n$ be integers such that $n \geq m \geq 1$. Prove that $\frac{\text{gcd} (m,n)}{n} \binom{n}{m}$ is an integer. Here $\text{gcd}$ denotes greatest common divisor and $\binom{n}{m} = \frac{n!}{m!(n-m)!}$ denotes the binomial coefficient.
Prove that for all $a\in\{0,1,2,\ldots,9\}$ the following sum is divisible by 10:
\[ S_a = \overline{a}^{2005} + \overline{1a}^{2005} + \overline{2a}^{2005} + \cdots + \overline{9a}^{2005}. \]
Show that for each natural number $n > 1$
$1 \cdot \sqrt{{n \choose 1}}+ 2 \cdot \sqrt{{n \choose 2}}+...+n \cdot \sqrt{{n \choose n}} <\sqrt{2^{n-1}n^3}$
Show that the coefficients of a binomial expansion $(a+b)^n$ where $n$ is a positive integer, are all odd, if and only if $n$ is of the form $2^{k}-1$ for some positive integer $k$.
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}$
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$.
In Happy City there are $2014$ citizens called $A_1, A_2, \dots , A_{2014}$. Each of them is either [i]happy[/i] or [i]unhappy[/i] at any moment in time. The mood of any citizen $A$ changes (from being unhappy to being happy or vice versa) if and only if some other happy citizen smiles at $A$. On Monday morning there were $N$ happy citizens in the city.
The following happened on Monday during the day: the citizen $A_1$ smiled at citizen $A_2$, then $A_2$ smiled at $A_3$, etc., and, finally, $A_{2013}$ smiled at $A_{2014}$. Nobody smiled at anyone else apart from this. Exactly the same repeated on Tuesday, Wednesday and Thursday. There were exactly $2000$ happy citizens on Thursday evening.
Determine the largest possible value of $N$.
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$).
If $$s_n = 1 + q + q^2 +... + q^n$$ and $$ S_n = 1 +\frac{1 + q}{2}+ \left( \frac{1 + q}{2}\right)^2 +... + \left( \frac{1 + q}{2}\right)^n,$$ prove that $${n + 1 \choose 1}+{n + 1 \choose 2} s_1 + {n + 1 \choose 3} s_2 + ... + {n + 1 \choose n + 1} s_n = 2^nS_n$$
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$.
In Pascal's Triangle, each entry is the sum of the two entries above it. The first few rows of the triangle are shown below.
\[\begin{array}{c@{\hspace{8em}}
c@{\hspace{6pt}}c@{\hspace{6pt}}c@{\hspace{6pt}}c@{\hspace{4pt}}c@{\hspace{2pt}}
c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{3pt}}c@{\hspace{6pt}}
c@{\hspace{6pt}}c@{\hspace{6pt}}c} \vspace{4pt}
\text{Row 0: } & & & & & & & 1 & & & & & & \\\vspace{4pt}
\text{Row 1: } & & & & & & 1 & & 1 & & & & & \\\vspace{4pt}
\text{Row 2: } & & & & & 1 & & 2 & & 1 & & & & \\\vspace{4pt}
\text{Row 3: } & & & & 1 & & 3 & & 3 & & 1 & & & \\\vspace{4pt}
\text{Row 4: } & & & 1 & & 4 & & 6 & & 4 & & 1 & & \\\vspace{4pt}
\text{Row 5: } & & 1 & & 5 & &10& &10 & & 5 & & 1 & \\\vspace{4pt}
\text{Row 6: } & 1 & & 6 & &15& &20& &15 & & 6 & & 1
\end{array}\]
In which row of Pascal's Triangle do three consecutive entries occur that are in the ratio $3: 4: 5$?
Let be four positive integers $m, n, p, q$, with $p < m$ given and $q < n$. Take four points $A(0; 0), B(p; 0), C (m; q)$ and $D(m; n)$ in the coordinate plane. Consider the paths $f$ from $A$ to $D$ and the paths $g$ from $B$ to $C$ such that when going along $f$ or $g$, one goes only in the positive directions of coordinates and one can only change directions (from the positive direction of one axe coordinate into the the positive direction of the other axe coordinate) at the points with integral coordinates. Let $S$ be the number of couples $(f, g)$ such that $f$ and $g$ have no common points. Prove that
\[S = \binom{n}{m+n} \cdot \binom{q}{m+q-p} - \binom{q}{m+q} \cdot \binom{n}{m+n-p}.\]
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]
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.
Consider the Pascal's triangle in the figure where the binomial coefficients are arranged in the usual manner. Select any binomial coefficient from anywhere except the right edge of the triangle and labet it $C$. To the right of $C$, in the horizontal line, there are $t$ numbers, we denote them as $a_1,a_2,\cdots,a_t$, where $a_t = 1$ is the last number of the series. Consider the line parallel to the left edge of the triangle containing $C$, there will only be $t$ numbers diagonally above $C$ in that line. We successively name them as $b_1,b_2,\cdots,b_t$, where $b_t = 1$. Show that
\[b_ta_1-b_{t-1}a_2+b_{t-2}a_3-\cdots+(-1)^{t-1}b_1a_t = 1\].
For example, Suppose you choose $\binom41 = 4$ (see figure), then $t = 3$, $a_1 = 6, a_2 = 4, a_3 = 1$ and $b_1 = 3, b_2 = 2, b_3 = 1$.
\[\begin{array}{ccccccccccc} & & & & & 1 & & & & & \\
& & & & 1 & & \underset{b_3}{1} & & & & \\
& & & 1 & & \underset{b_2}{2} & & 1 & & & \\
& & 1 & & \underset{b_1}{3} & & 3 & & 1 & & \\
& 1 & & \boxed{4} & & \underset{a_1}{6} & & \underset{a_2}{4} & & \underset{a_3}{1} & \\
\ldots & & \ldots & & \ldots & & \ldots & & \ldots & & \ldots \\
\end{array}\]
Prove the equality
$${n \choose 0}^2+ {n \choose 1}^2+ {n \choose 2}^2+...+{n \choose n}^2={2n \choose n}$$
Prove that for any prime $p$ in the interval $\left]n, \frac{4n}{3}\right]$, $p$ divides \[\sum^{n}_{j=0}{{n}\choose{j}}^{4}.\]
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$ .
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$.
If $x$ is a real number such that $x^2 -x$ is an integer, and for some $n \ge 3$, $x^n -x$ is also an integer, prove that $x$ is an integer.
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}$.