Cute counting

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Cute counting

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: KMO 2022 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

228 posts

#1 h Oct 29, 2022, 12:07 PM

Y by

For positive integers $m, n$ ( $m>n$ ), $a_{n+1}, a_{n+2}, ..., a_m$ are non-negative integers that satisfy the following inequality.
$2> \frac{a_{n+1}}{n+1} \ge \frac{a_{n+2}}{n+2} \ge \cdots \ge \frac{a_m}{m}$ Find the number of pair $(a_{n+1}, a_{n+2}, \cdots, a_m)$ .

This post has been edited 3 times. Last edited by chrono223, Oct 29, 2022, 12:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

53 posts

#2 h Oct 30, 2022, 11:45 AM • 1 Y

Y by Mango247

Denote $k, l$ be integers which satisfies the following statements.
$2>\frac{a_{n+1}}{n+1}\geq\cdots\geq\frac{a_k}{k}>1=\frac{a_{k+1}}{k+1}=\cdots=\frac{a_l}{l}>\frac{a_{l+1}}{l+1}\geq\cdots\geq\frac{a_m}{m}$ (Note that $n\leq k\leq l\leq m$ )

Then $a_i=i$ for $k+1\leq i\leq l$ .
Step 1. $1>\frac{a_{l+1}}{l+1}\geq\cdots\geq\frac{a_m}{m}$ $\Leftrightarrow$ $a_{i+1} \leq a_i$ for $l\leq i<m$ .
pf) If $a_{i+1}>a_i$ for such $l< i<m$ , $\frac{a_{i+1}}{i+1}\geq \frac{a_i +1}{i+1}>\frac{a_i}{i}$ since $a_i<i$ . Also contradiction for $a_{l+1}>a_l$ .
If $a_{i+1}\leq a_i$ , $\frac{a_{i+1}}{i+1}\leq\frac{a_i}{i+1}\leq\frac{a_i}{i}$ . Furthermore, $\frac{a_{l+1}}{l+1}\leq\frac{a_l}{l+1}<1$ .

Step 2. $2>\frac{a_{n+1}}{n+1}\geq\cdots\geq\frac{a_k}{k}>1$ $\Leftrightarrow$ $a_{i+1}\leq a_i+1$ for $n<i<k$ and $a_k>k$ .
pf) If $a_{i+1}\geq a_i+2$ for $n<i<k$ , $\frac{a_{i+1}}{i+1}\geq\frac{a_i+2}{i+1}>\frac{a_i}{i}$ since $2>\frac{a_i}{i}$ .
If $a_{i+1}\leq a_i+1$ , $\frac{a_{i+1}}{i+1}\leq\frac{a_i+1}{i+1}\leq\frac{a_i}{i}$ since $a_i\geq a_k+(i-k)>i$ .

For fixed $k$ and $l$ the number of sequences are $_{l+1}H_{m-l}\times \:_{n}H_{k-n}=\binom{m}{l}\times\binom{k-1}{n-1}$

$\therefore \sum_{n\leq k\leq l\leq m}{\binom{m}{l}\binom{k-1}{n-1}}=\sum_{l=n}^{m}\binom{m}{l}\sum_{k=n}^{l}\binom{k-1}{n-1}=\sum_{l=n}^{m}\binom{m}{l}\binom{l}{n}=\sum_{l=n}^{m}\binom{m}{n}\binom{m-n}{l-n}=2^{m-n}\binom{m}{n}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

497 posts

#3 h Nov 5, 2022, 4:42 AM • 1 Y

Y by mathverse06

Let $X_{m,n}$ be the set of such sequence $(a_{n+1},\cdots,a_m)$ . The given condition can be interpreted as follows:
$\begin{cases} a_{k+1} \leq a_k +1 & \text{ if } a_k/k \geq 1, \\ a_{k+1} \leq a_k & \text{ if } a_k / k< 1 \end{cases}$ for all $n+1\leq k\leq m-1$ .

Claim. $|X_{m+1,n}| = 2|X_{m,n}| + |X_{m,n-1}|$ (for convenience $|X_{m,m}| = 1$ )
Proof. For a sequence $(a_{n+1},\cdots,a_m, a_{m+1}) \in X_{m+1,n}$
Case 1. $a_{m+1} = 0$
Trivial 1-1 correspondence with $X_{m,n}$
Case 2. $a_{n+1} \leq 2n$ , $a_{m+1} \geq 1$
1-1 correspondence with $X_{m,n-1}$ by $(a'_n, \cdots , a'_{m}) = (a_{n+1} - 1, \cdots , a_{m+1} - 1)$ .
Case 3. $a_{n+1} = 2n+1$ , $a_{m+1} \geq 1$
1-1 correspondence with $X_{m,n}$ by $(a'_{n+1}, \cdots , a'_m) = (a_{n+2} - 1,\cdots, a_{m+1} -1)$ . $\blacksquare$

Solving the recurrence relation gives $|X_{m,n}| = 2^{m-n} \binom{m}{n}$ . (consider $2^{-(m-n)} |X_{m,n}|$ )

This post has been edited 1 time. Last edited by EagleEye, Nov 5, 2022, 4:42 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

561 posts

#4 h Jun 26, 2023, 2:46 AM

Y by

EagleEye wrote:

Let $X_{m,n}$ be the set of such sequence $(a_{n+1},\cdots,a_m)$ . The given condition can be interpreted as follows:
$\begin{cases} a_{k+1} \leq a_k +1 & \text{ if } a_k/k \geq 1, \\ a_{k+1} \leq a_k &\text{ if } a_k / k< 1 \end{cases}$ for all $n+1\leq k\leq m-1$ .

Claim. $|X_{m+1,n}| = 2|X_{m,n}| + |X_{m,n-1}|$ (for convenience $|X_{m,m}| = 1$ )
Proof. For a sequence $(a_{n+1},\cdots,a_m, a_{m+1}) \in X_{m+1,n}$
Case 1. $a_{m+1} = 0$
Trivial 1-1 correspondence with $X_{m,n}$
Case 2. $a_{n+1} \leq 2n$ , $a_{m+1} \geq 1$
1-1 correspondence with $X_{m,n-1}$ by $(a'_n, \cdots , a'_{m}) = (a_{n+1} - 1, \cdots , a_{m+1} - 1)$ .
Case 3. $a_{n+1} = 2n+1$ , $a_{m+1} \geq 1$
1-1 correspondence with $X_{m,n}$ by $(a'_{n+1}, \cdots , a'_m) = (a_{n+2} - 1,\cdots, a_{m+1} -1)$ . $\blacksquare$

Solving the recurrence relation gives $|X_{m,n}| = 2^{m-n} \binom{m}{n}$ . (consider $2^{-(m-n)} |X_{m,n}|$ )

Uh… how do you solve this recurrence relationship..

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a