For positive integer $n \ge 3$, find the number of ordered pairs $(a_1, a_2, ... , a_n)$ of integers that satisfy the following two conditions For positive integer $i$ such that $1\le i \le n$, $1 \le a_i \le i$ For positive integers $i,j,k$ such that $1\le i < j < k \le n$, if $a_i = a_j$ then $a_j \ge a_k$
Problem
Source: KJMO 2022 number 2
Tags: combinatorics, counting
Seungjun_Lee
19.01.2023 17:45
Bump! Bump!
mathmax12
19.01.2023 17:57
wait why is your profile different in both of the posts
Seungjun_Lee
19.01.2023 18:50
mathmax12 wrote: wait why is your profile different in both of the posts I changed my profile picture after I posted the forst one
mathmax12
20.01.2023 03:29
Seungjun_Lee wrote: mathmax12 wrote: wait why is your profile different in both of the posts I changed my profile picture after I posted the forst one I never knew you could do that
pokmui9909
20.01.2023 12:03
Let $t$ be the minimum integer such that $a_{t + 1} < t + 1$ (if $a_i = i$ for all $i$, then $t = n$). We can prove $a_{t + 1} \ge a_{t + 2} \ge ... \ge a_n$ by induction. Thus, the answer is $\sum_{t = 1}^{n} {}_{t-1}H_{n - t} = \sum_{t = 1}^{n} \binom{n - 1}{n - t} = 2^n$
Seungjun_Lee
21.01.2023 05:32
pokmui9909 wrote: Let $t$ be the minimum integer such that $a_{t + 1} < t + 1$ (if $a_i = i$ for all $i$, then $t = n$). We can prove $a_{t + 1} \ge a_{t + 2} \ge ... \ge a_n$ by induction. Thus, the answer is $\sum_{t = 1}^{n} {}_{t-1}H_{n - t} = \sum_{t = 1}^{n} \binom{n - 1}{n - t} = 2^n$ Oh!!! fantastic solution!