Permutations of Integers from 1 to n

The post below has been deleted. Click to close.

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

6 posts

#1 h Jul 20, 2021, 9:01 PM • 12 Y

Y by tree_3, InvertedDiabloNemesisXD, centslordm, jhu08, megarnie, ImSh95, son7, sohere, Kingsbane2139, Supercali, Marshall_Huang, kiyoras_2001

Let $n$ be a positive integer. Find the number of permutations $a_1$ , $a_2$ , $\dots a_n$ of the
sequence $1$ , $2$ , $\dots$ , $n$ satisfying
$a_1 \le 2a_2\le 3a_3 \le \dots \le na_n$ .

Proposed by United Kingdom

This post has been edited 1 time. Last edited by Twoisntawholenumber, Jul 20, 2021, 9:36 PM
Reason: Added the country that proposed the problem

Z K Y

The post below has been deleted. Click to close.

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

cadaeibf

701 posts

cadaeibf

#2 h Jul 20, 2021, 9:03 PM • 7 Y

Y by centslordm, THEfmigm, ImSh95, son7, crazyeyemoody907, Marshall_Huang, MS_asdfgzxcvb

solution

This post has been edited 1 time. Last edited by cadaeibf, Jul 20, 2021, 9:12 PM

Z K Y

The post below has been deleted. Click to close.

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

Twoisntawholenumber

6 posts

Twoisntawholenumber

#3 h Jul 20, 2021, 9:05 PM • 5 Y

Y by InvertedDiabloNemesisXD, centslordm, ImSh95, son7, Marshall_Huang

Let $A_n$ be the number of permutations which satisfy the property. We claim that $A_N=F_{N+1}$ , where $F_k$ is the $k^{th}$ Fibonacci number; defined as $F_0=0, F_1=1, F_{m+2}=F_{m+1}+F_{m} \forall m\ge0$ .
Claim: In the permutation, either $N=a_{N-1}$ or $N=a_N$ .
Proof: Suppose $N=a_{N-k}$ for some integer $k\ge 2$ . We can deduce that any integer $m<N-k$ must be given an index of less than $N-k$ ; if it were not, we would need $m_i\ge N(N-k)$ for some index $i$ , however as $m<N-k$ and $i\le n$ , $mi<N(N-k)$ , hence a contradiction.
Therefore the first $N-k-1$ integers are in the permutation $(a_1,a_2\dots a_{N-k-1})$ and the integer $N-k$ must be placed further along in the permutation than $N$ , so we would need $(N-k)j\ge N(N-k)$ for some index $j$ , hence $j=N$ . So $a_N=N-k$ , and therefore $(N-k)a_{N-k}=Na_N$ , sow e need $(N-r)a_{N-r}=N(N-k)$ for all non-negative integers $r\le k$ .
Consider the largest prime $p$ which is less than or $k+1$ . By Bertrand's Postulate, $p > \frac{k+1}{2}$ , hence this prime divides only one of the integers in the set $\{N-k,N-k+1\dots,N\}$ , as there are $k+1$ terms, and so at most two of the products $xa_x$ are divisible by this prime. However as $k\ge 2$ , we have at least 3 products, and so this is impossible.
We now show that $A_N=F_{N+1}$ by induction.
Base cases: $N=1$ and $N=2$ .
$N=1$ , we only have 1 permutation so $A_1=1=F_2$ .
$N=2$ , we only have 2 permutations, $\{1,2\}$ and $\{2,1\}$ , so $A_2=2=F_3$ .
Now we assume $A_n=F_{n+1}$ and $A_{n+1}=F_{n+2}$ for some $n$ .
Consider $A_{n+2}$ . By the earlier lemma, either $n+2=a_{n+1}$ or $n+2=a_{n+2}$ .
In the first case, if $a_{n+1}=n+2$ , we must have $a_{n+2}=n+1$ . As these products are greater than all other possible products, we can arrange the previous $n$ terms in a way which satisfies the condition, and we can do this in $A_n=F_{n+1}$ ways.
In the second case, the largest product is $(n+2)^2$ and hence we can arrange the remaining terms in $A_{n+1}=F_{n+2}$ ways. So we have $A_{n+2}=F_{n+1}+F_{n+2}=F_{n+3}$ , and so we are done.

Z K Y

The post below has been deleted. Click to close.

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

AwesomeYRY

579 posts

AwesomeYRY

#4 h Jul 20, 2021, 9:19 PM • 5 Y

Y by centslordm, ImSh95, son7, mijail, Marshall_Huang

We claim that the answer is $a_n= F_{n+1}$ where $F_n$ is the $n$ -th fibonacci number defined by $F_0=0$ , $F_1=1$ , $F_k=F_{k-1}+F_{k-2}$ . We proceed with induction, our base cases are $a_1=1=F_2$ , any permutation works. And $a_2=2=F_3$ , once again any permutation works.

Inductive step. We do casework on the position of $n$ .

Case 1: $a_n=n$ . In this case, all $i\cdot a_i\leq n\cdot a_n$ , so we will be left with any of the $a_{n-1}$ permutations of the first $n-1$ , all of which will work, Case 1 contributes $a_{n-1}$ .

Case 2: $a_{n-1}=n$ . In this case
$a_{n-1}\cdot n\leq (n-1)\cdot a_{n-1}\leq n\cdot a_n$ thus, $a_n\geq n-1$ , so $a_n=n$ . Now, once again all of the first $n-2$ : $1\leq j\leq n-2$ will satisfy $a_j\cdot j \leq n\cdot (n-1)$ , so any of the first $n-2$ work, so this case contributes $a_{n-2}$ .

Case 3: $a_j=n$ for $j\leq n-2$ . I claim that there are no valid solutions. Note for all indices $n\geq k \geq j$ , we have
$j\cdot n = j\cdot a_j \leq k\cdot a_k \Longrightarrow a_k\geq \frac{j\cdot n}{k}\geq j$ Thus,
$a_j,a_{j+1},\ldots, a_n\geq j$ Since these $a_k$ are distinct, $\{a_j,\ldots a_n\}$ must be some permutation of $\{j,\ldots,n\}$ . Consider $x>j$ such that $a_x=j$ . Then,
$jn=j\cdot a_j\leq x\cdot a_x=xj$ Thus, $x\geq n$ so $x=n$ and $a_n=j$ . Now, note that $a_y=n-1$ for some $j<y<n$ . Thus,
$n\cdot j=n\cdot a_n\geq y\cdot a_y = y\cdot (n-1)\geq (j+1)(n-1)=nj+n-j-1\geq nj+n-(n-2)-1=nj+1$ Thus, $nj\geq nj+1$ , a contradiction. Thus, there are no solutions for $j\leq n-2$ . To recap, $a_n=a_{n-1}+a_{n-2}+0=a_{n-2}+a_{n-2}$ , so our induction is complete.

Z K Y

The post below has been deleted. Click to close.

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

Eyed

1065 posts

Eyed

#5 h Jul 20, 2021, 10:12 PM • 8 Y

Y by VulcanForge, tree_3, centslordm, Smileyklaws, Deemaths, ImSh95, grey_hat_hacker, MS_asdfgzxcvb

Solved with nukelauncher

We claim the answer is $F_{n+1}$ , where $F_1=F_2=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq3$ are the Fibonacci numbers. We prove this by induction on $n$ , with the base cases of $n=1,2$ being trivially true.

Claim:
$n\in\left\{ a_{n-1},a_n \right\}$ .

Proof.
Suppose not. Then let $a_k=n$ . Note that none of $1,2,\dots,k-1$ are elements of $\left\{ a_{k+1},a_{k+2},\dots,a_n \right\}$ as that would contradict the given inequality. Therefore, $\left\{ a_{k+1},\dots,a_n \right\}$ is a permutation of $\left\{ k,k+1,\dots,n-1 \right\}$ . We must have $a_n=k$ to satisfy the inequality for $na_n\geq ka_k$ , but then this implies that we have the equality $ka_k=(k+1)a_{k+1}=\dots=na_n,$ a clear contradiction when $k<n-1$ . $\blacksquare$

With the claim, the number of permutations for $n$ is the sum of the number of permutations for the cases of $n-2$ and $n-1$ by taking cases on whether $a_n=n$ or $a_{n-1}=n$ and $a_n=n-1$ . This completes the inductive step, so we are done.

Z K Y

The post below has been deleted. Click to close.

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

pad

1671 posts

pad

#6 h Jul 20, 2021, 11:29 PM • 6 Y

Y by centslordm, Wizard0001, ImSh95, mijail, alexgsi, Marshall_Huang

Claim: We have $n\in \{a_{n-1},a_n\}$ .

Proof: Suppose instead that $a_x=n$ and $x \le n-2$ . For all $y>x$ , we have
$xn = xa_x \le ya_y \le na_y \implies a_y \ge x.$ Therefore,
$\{a_{x+1},a_{x+2},\ldots, a_{n-1}\} = \{x,x+1,\ldots,n-1\}.$ In particular, $a_z=x$ for some $z>x$ . Then
$xn = xa_x \le za_z=zx \implies n \le z \implies z=n.$ So $a_n=x$ . Now,
$xn = xa_x \le \cdots \le na_n = nx,$ so actually $ia_i=xn$ for all $x\le i\le n$ . Now the finish is easy. We have $(n-1)a_{n-1} = nx$ , so $n-1 \mid nx$ , so $n-1\mid x$ . But $x\le n-2$ , contradiction. $\blacksquare$

If $a_n=n$ , then there are $f(n-1)$ ways for the first $n-1$ . If $a_{n-1}=n$ , then $a_n=n-1$ , and there are $f(n-2)$ ways for the first $n-2$ . Hence $f(n)=f(n-1)+f(n-2)$ , and since $f(1)=f(2)=1$ , we have $f(n) = F_{n+1}$ .

Z K Y

The post below has been deleted. Click to close.

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

mathaddiction

308 posts

mathaddiction

#7 h Jul 20, 2021, 11:44 PM • 3 Y

Y by centslordm, ImSh95, Marshall_Huang

The answer is $F_{n+1}$ , the $(n+1)^{th}$ Fibonacci number.
Let $a_1,...,a_n$ be such a permutation.
Claim.
(i) $a_i\geq i-1$
(ii) $a_i\leq i+1$

Proof.
(i) If $a_i\leq i-2$ , we prove by backward induction that $a_j\leq j-2$ for all $1\leq j\leq i$ . If $a_i=i-2$ , then
$(i-1)a_{i-1}\leq ia_i=i(i-2)$ hence $a_{i-1}<i-1$ , which implies $a_i\leq i-3$ . If $a_i\leq i-3$ then
$(i-1)a_{i-1}\leq ia_i=i(i-3)$ hence $a_{i-1}<i-2$ , which implies $a_{i-1}\leq i-3$ as desired. But this is obviously impossible since $a_2\leq 0$ .
(ii) Suppose on the contrary that $a_i\geq i+2$ , then $a_{i+1}\geq i+1$ , hence at least one of $1,...,i$ , say $k$ is not in $a_1,...,a_{i-1}$ . Suppose $a_j=k$ , then $j\geq i+2$ , contradiction. $\blacksquare$
Now it is easy to see that the permutation consists of only $2$ -cycles $(i,i+1)$ and fixed points, and conversely every such permutation satisfies the condition.
We count the number of such permutation, denote it by $x_n$ . If $a_1=2$ then there are $x_{n-2}$ ways to permute $\{3,..,n\}$ , and if $a_1=1$ there are $x_{n-1}$ ways to permute $\{2,...,n\}$ . Hence
$x_n=x_{n-1}+x_{n-2}$ combine with the obvious fact that $x_1=1$ and $x_2=2$ we have $x_n=F_{n+1}$ as desired.

This post has been edited 2 times. Last edited by mathaddiction, Jul 20, 2021, 11:45 PM

Z K Y

The post below has been deleted. Click to close.

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

SnowPanda

186 posts

SnowPanda

#8 h Jul 21, 2021, 2:48 AM • 2 Y

Y by ImSh95, Marshall_Huang

Solution

Z K Y

The post below has been deleted. Click to close.

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

lneis1

243 posts

lneis1

#9 h Jul 21, 2021, 8:50 AM • 2 Y

Y by ImSh95, Marshall_Huang

Let $a_j=n$
First we will show that $j \leq n-2$
If $j < i< n$ then $a_i > j$ because $jn \leq ia_i < na_i$

Also $a_n > j$ because $na_n\geq (n-1)a_{n-1} > nj$ .

But notice that $a_j, a_{j+1}, a_{j+2}, \cdot \cdot \cdot a_n$ are $(n-1)(j+1)-nj=n-j+1$ numbers which are all greater than $j$ ,
Whereas there are only $n-j$ such values.

Hence we get that $n$ can only be placed in the last two positions.

So let $S_n$ denote the total no of permutations satisfying the condition for n numbers.
Now $(a_1,a_2,a_3...a_{n-1},n)$ first keep $n$ constant so we will have $S_{n-1}$ such permutations
And then consider $(a_1, a_2, a_3...., n, n-1)$ which is $S_{n-2}$

So $S_n=S_{n-1}+S_{n-2}$ which is indeed the $(n+1)th$ Fibonacci number.

Z K Y

The post below has been deleted. Click to close.

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

554183

484 posts

554183

#10 h Jul 21, 2021, 3:03 PM • 2 Y

Y by ImSh95, Marshall_Huang

Pretty easy.
Let the number of permutations be $x_n$ . We claim that $x_n = F_{n+1}$ (the $n+1$ th Fibonacci number).
Claim : if $a_i =n$ , then $i \in \{n-1, n\}$ .
Proof : FTSOC assume $a_i = n, i \leq n-2$ . Then we must have $a_{i+1} \geq \frac{in}{i+1} >i \implies a_{i+1} \geq i+1$ . Now $a_{i+2} \geq \frac{(i+1)^2}{i+2} > i \implies a_{i+2} \geq i+1$ . Now we either have $a_{i+2} \geq i+2$ or $a_{i+2}=i+1$ . But if $a_{i+2}=i+1, a_{i+1}=i+2$ for size reasons. Now note that $a_{i+3} \geq \frac{(i+1)(i+2)}{i+3} > i \implies a_{i+3} \geq i+3$ . Continuing this till $n$ , we see that $a_n \geq n$ , or that $a_n=n-1$ and $a_{n-1}=n$ . Either way, this is a contradiction.

To finish, note that if $a_n=n$ we have $x_{n-1}$ sequences, and if $a_{n-1}=n, a_n=n-1$ for size reasons, so we have $x_{n-2}$ sequences. We get $x_{n}=x_{n-1}+x_{n-2}$ , and seeing $x_1 =1, x_2=2$ , we are done !

Z K Y

The post below has been deleted. Click to close.

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

Mathematicsislovely

245 posts

Mathematicsislovely

#11 h Jul 21, 2021, 5:09 PM • 2 Y

Y by ImSh95, Marshall_Huang

Let $X_n$ denote the total number of permutation of $[n]$ with the given property.Let $b_n$ denote the number of permutation of $[n]$ with the given property with $a_n=n$ and $c_n$ denote the number of permutation of $[n]$ with the given property with $a_n\ne n$ .Then,
$X_n=b_n+c_n =X_{n-1}+c_n$ Now we will try to find out recursion for $c_n$

Claim: If $a_m=n$ then $a_n=m$ .

Proof. If $a_m=n$ then,
$mn=ma_m\le (m+1)a_{m+1}\le\dots\le na_n$ .
So $m+r\le n$ so the above relation implies $a_{m+r}\ge m$ for $r=1,2,\dots,n-m$ .
But then $\{a_{m+1},a_{m+2}\dots a_n\}=\{m,m+1,m+2,\dots,n-1\}$ [becoz size of both set are equal].
But then $a_{m+r}=m\implies m(m+r)\ge ma_m=mn\implies {m+r}\ge n$ So indeed $m+r=n$ $\blacksquare$

So, $ma_m=(m+1)a_{m+1}=(m+2)a_{m+2}=\dots =na_n=mn$
In particular, $(n-1)a_{n-1}=nm$ .Since $\gcd(n,n-1)=1$ so $n\mid a_{n-1}$ .This is possible only when $a_{n-1}=n$ .In particular, $m=n-1$ .
So $c_n=X_{n-2}$ because $a_{n-1}=n\implies a_n=(n-1)$ for size reason.
So $X_n=X_{n-1}+X_{n-2}$ .
Now $X_1=1$ and $X_{2}= 2$ implies $X_n=F_{n+1}$ .Where $F_n$ is $n$ th Fibonacci number. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Spacesam

596 posts

Spacesam

#12 h Jul 21, 2021, 10:17 PM • 2 Y

Y by ImSh95, Marshall_Huang

We will induct. We establish the base cases first: for $n = 1$ and $n = 2$ , the answers are $1$ and $2$ , respectively, and we claim that the answer is $F_{n + 1}$ where $F_0 = 0$ , $F_1 = 1$ , $F_2 = 1$ , etc.

Proceed by strong induction. For the inductive step of $i - 1$ to $i$ , the idea is to consider where the largest element $i$ could go. It can obviously go at the end; this reduces to the $i - 1$ case, contributing $F_i$ .

Additionally, it can also go one place before the end, so the second to last product is $i(i - 1)$ . As a result, this forces $i(i - 1) \leq ia_i$ , so $i - 1 \leq a_i$ and so $a_i = i - 1$ , reducing to the $i - 2$ case. This contributes $F_{i - 1}$ . The key claim now which finishes the problem is as follows:

Claim: There are no other positions for $i$ that work other than the two named above.

Assume that $a_k = i$ where $k \leq i - 2$ . The idea is to consider what the minimum of $a_{k + 1}, a_{k + 2}, \cdots, a_i$ is. Observe that this minimum element is at most $k$ since there are $i - k$ elements from $a_{k + 1}$ to $i$ . Consequently, we know that the elements from $a_{k + 1}$ to $a_i$ are forced to be some permutation of $(k, k + 1, \cdots, i - 1)$ with $a_i = k$ .

Since $a_k = a_i$ , we know that every term in between must be equal to them as well. Now, we just need to consider where the $i - 1$ element goes. By our logic above, we can write $(i - 1) \cdot a = ki$ for some integer $a$ . However, $\gcd(i, i - 1) = 1$ , so we know $i - 1 \mid k$ , implying $i - 1 \leq k$ , contradiction. $\square$

Thus we are done since $F_{i - 1} + F_i = F_{i + 1}$ .

This post has been edited 1 time. Last edited by Spacesam, Jul 21, 2021, 10:18 PM

Z K Y

The post below has been deleted. Click to close.

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

yofro

3153 posts

yofro

#13 h Jul 22, 2021, 4:02 AM • 2 Y

Y by ImSh95, Marshall_Huang

The answer is the $n+1$ th Fibonacci number. I prove this with strong induction. Let $P(n)$ be the number of ways to do so. The base cases are easy since
$P(1)=|\{1\}|=1=F_2$ $P(2)=|\{1,2\}, \{2,1\}|=2=F_3$ We do casework on the index of $n$ . If $n$ is at the last position, there are $P(n-1)$ ways. If $n$ is at the second-to-last position, $n-1$ must be at the last position, hence there are $P(n-2)$ ways. I now prove that $n$ cannot be at any other position, effectively solving the problem.

Suppose the contrary. Clearly, $n$ cannot be at the first position. Hence there is a valid sequence of the first $k$ numbers, then $n$ , then a jumble of the other numbers. Consider the number $k+1$ . Let's say its at index $r$ . Then
$n(k+1)\le (k+1)r$ $n\le r$ $r=n$ Hence $k+1$ is the last number. Suppose that the number at index $n-1$ is $r$ . Thus
$(n-1)r\le(k+1)n$ But $k+2\le r$ , hence
$(k+2)(n-1)\le (k+1)n$ $nk+2n-k-2\le nk+n$ $n\le k+2$ Meaning that there are at least $n-2$ numbers before the number $n$ , i.e. $n$ is at one of the last two spots, as desired.

This post has been edited 1 time. Last edited by yofro, Jul 22, 2021, 4:19 AM

Z K Y

The post below has been deleted. Click to close.

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

hakN

429 posts

hakN

#14 h Jul 22, 2021, 12:32 PM • 2 Y

Y by ImSh95, Marshall_Huang

For $m \leq n$ , let $f_m(n)$ denote the number of permutations of the set $\{m,m+1, \dots , n\}$ such that $ma_m \leq (m+1)a_{m+1} \leq \dots \leq na_n$ . We will prove that $f_i(n) = f_{i+1}(n) + f_{i+2}(n)$ for all $1 \leq i \leq n-2$ . Now fix some $1 \leq i \leq n-2$ .
Let $a_k = i$ . If $k = i$ , then we are left with $f_{i+1}(n)$ such permutations. Let $k > i$ . Then we have $k\cdot a_k = k \cdot i \geq (k-1) \cdot a_{k-1} \ge(k-1) \cdot (i+1) \iff k \leq i + 1$ .
So we have $k = i+1$ , in other words $a_{i+1} = i$ . Then $ia_i \leq (i+1)i \implies a_i \leq i+1 \implies a_i = i+1$ . So $a_i = i+1$ and $a_{i+1} = i$ and we are left with $f_{i+2}(n)$ such permutations. Thus we have proved the claim.
Now define a sequence as $F_1 = 1 , F_2 = 1,$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 3$ . It is easy to see that $f_n(n) = 1$ and $f_{n-1}(n) = 2$ .
Thus, we have $f_1(n) = F_{n+1}$ . Also it is well known that $F_n = \frac{(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n}{\sqrt{5}}$ .
So, our answer is $F_{n+1} = \frac{(\frac{1 + \sqrt{5}}{2})^{n+1} - (\frac{1 - \sqrt{5}}{2})^{n+1}}{\sqrt{5}}$ .

Z K Y

The post below has been deleted. Click to close.

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

rustam

348 posts

rustam

#15 h Jul 22, 2021, 1:34 PM • 2 Y

Y by ImSh95, Marshall_Huang

This problem was used in 2017 Uzbekistan young mathematicians olympiad, but it was take from Crux.

Z K Y

The post below has been deleted. Click to close.

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

Acclab

33 posts

Acclab

#65 h Feb 28, 2024, 5:44 PM • 1 Y

Y by Marshall_Huang

Main claim: $a_n$ is a valid permutation iff $|a_i-i| \leq 1 \; \forall i$

. FTSoC suppose $|a_i - i| \geq 2$ for some $i$ , write $a_i = i+k$ with $k \geq 2$ , and further require such $k$ to be maximal. By the Pigeonhole principle, it is possible to choose $\phi \geq i$ so that $a_\phi \leq i$ . Then since $\phi \geq i$ , $\phi a_{\phi} \geq i a_i = i(i+k).$ Suppose $a_\phi = i-t$ , then $\phi \geq i+k+t$ as otherwise $\phi a_\phi < (i+k+t)(i-t) = i(i+k) - tk - t \leq i(i+k).$

Futhermore, we claim $|a_\phi - \phi| > k$ even if $t = 0$ ( $t > 0$ is trivial). That is, $\phi > i+k+t$ is strict as otherwise $\phi a_\phi = (i+k)i, ia_i = (i+1)a_{i+1} = ... = (i+k)a_{i+k} = i(i+k).$ This is contradictive if $k \geq 2$ , as $gcd(i, i+1) = 1$ so $a_i = i+1 = i+k$ implying $k=1$ , so $|a_\phi - \phi| > k$ , contraditing with maximality. The converse is easy to check, as
$ia_i \leq i(i+1) = (i+1)((i+1)-1) \leq (i+1)a_{i+1}$ for any $1 \leq i \leq n$ .

Now consider $p_n$ to be the number of such permutations. By combinatorics reasoning, if $a_n = n$ then there are $p_{n-1}$ ways of valid permutation, and if $a_n = n-1$ , $a_{n-1} = n$ and we have $p_{n-2}$ ways. So $p_n = p_{n-1} + p_{n-2}$ . It's easy to check $p_1 = 1$ and $p_2 = 2$ , so $p_n = F_{n+1}$ , the $n+1$ -th Fibonacci number.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

808 posts

shendrew7

#66 h Apr 23, 2024, 3:47 AM • 1 Y

Y by Marshall_Huang

We prove the answer is $f(n) = \boxed{F_{n+1}}$ through recursion, starting by noting trivial base cases $n=1$ and $n=2$ .

Our problem can be translated to selecting $n$ numbers from each row of an $n \times n$ multiplication table such that each cell is in a distinct column and the entries are in weakly increasing order. We consider the number selected in the last column:

$n^2$ : The remaining $n-1$ numbers have $f(n-1)$ permutations.
$n(n-1)$ : We're forced to select $n(n-1)$ from the $(n-1)$ -th column too, leaving $f(n-2)$ possibilities.
$n(n-k)$ for $k \ge 2$ : Consider the selections from row $n-k+1$ to row $n$ , which must be at least $n(n-k)$ . Since we clearly can't select $n(n-k)$ on row $n$ , as this forces equality to holds on all rows in between, we are left with a $k \times (k-1)$ rectangle of potential cells. Attempting to select $k$ cells in distinct rows and columns results in a Pigeonhole contradiction.

Hence we get $f(n) = f(n-1)+f(n-2)$ , as desired. $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Apr 23, 2024, 3:50 AM

Z K Y

The post below has been deleted. Click to close.

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

PennyLane_31

77 posts

PennyLane_31

#67 h Jun 25, 2024, 2:02 AM • 2 Y

Y by Thelink_20, Marcos_Vinicius

For each $n\in\mathbb{Z^*_+}$ , let $P_n$ be the number of permutations of $\{1,2,3,\dots, n\}$ such that $a_1\le 2a_2\leq 3a_3\le\dots na_n$
Afirmation: $P_n= F_{n+1}$ , where $F_n$ denotes the $n$ th Fibonacci.

Proof: Induction in $n$

(I) Base case:
$n= 2$ , we have two possible permutations: $\{1,2\}$ and $\{2,1\}$ , note that $1\cdot 1\le 2\cdot 2$ and $1\cdot 2\le 2\cdot 1$ . So, $P_2= 2= F_3$ .

(ii) Hypothesis: Assuming the lemma is valid for all $m\le n-1$ $m\in\mathbb{Z^*_+}$ , we will prove it is valid for $n$ .

We have two cases:

If $a_n= n$ , then we need to choose $\{1,2,\dots, n-1\}$ for $a_1, a_2, \dots, a_{n-1}$ . So, there are $P_{n-1}$ possible permutations.

If $a_n= n-i$ , with $i\in\{1,2,\dots, n-1\}$ , then we know that

$(n-1)a_{n-1}\le na_n= n(n-i)\implies \dfrac{a_{n-1}}{n-i}\le 1+\dfrac{1}{n-1}$ .

If $a_{n-1}\ge n-i+1\implies \dfrac{n-i+1}{n-i}\le \dfrac{a_{n-1}}{n-i}\le 1+\dfrac{1}{n-1}\implies n-1\le n-i\implies i\le 1\therefore i=1$ .

So, $a_n= n-1$ and $a_{n-1}= n$ . Indeed, this gives us a solution, because we now have $\{1,2,3,\dots, n-2\}$ for $a_1, a_2, \dots, a_{n-2}$ , which leads us to $P_{n-2}$ possible permutations.

Now, if $a_{n-1}\le n-i-1$ . Let $a_{n-1}= n-j$ , with $j\ge i+1$ .

Observe that $(n-2)a_{n-2}\le (n-1)a_{n-1}= (n-j)(n-1)\implies \dfrac{a_{n-2}}{n-j}\le \dfrac{n-1}{n-2}= 1+\dfrac{1}{n-2}$ .

If $a_{n-2}\geq n-j+1$ ( $a_{n-2}\neq a_{n-1}$ ), thus $1+\dfrac{1}{n-j}=\dfrac{n-j+1}{n-j}\le\dfrac{a_{n-2}}{n-j}\le 1+\dfrac{1}{n-2}$

$\implies n-2\le n-j\implies j\le 2\implies j=2\implies i=1$ .

Finally, $a_n= n-1$ and $a_{n-1}= n-2$ . Also, we get that $a_{n-2}\ge n-2+1= n-1\implies a_{n-2}= n$ .

But $a_{n-2}(n-2)= n(n-2)\leq a_{n-1}(n-1)= (n-2)(n-1)\implies n\le n-1$ , absurd!
So, we must have $a_{n-2}\le n-j-1$ . Inductively, we will have that $a_1<a_2<a_3<\dots<a_{n-2}<a_{n-1}<a_n$ . One number is missing! As $a_n\neq n$ , then $n$ would appear somewhere, but with this ordination is impossible! Contradiction!

Therefore, $P_n= P_{n-1}+P_{n-2}$ , $\forall n$ . As $P_2= 2$ and $P_3=3$ , we get that $P_n= F_{n-1}$ , QED $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

L13832

268 posts

L13832

#68 h Jul 13, 2024, 8:22 AM

Y by

Almost similar to the solutions above but i'll still post it becoz i spent an hour solving it and another to write it...
The answer is $A_n=F_{n+1}$ , the ${n+1}^{th}$ Fibonacci number (this can be checked by going upto $n=5$ ) where $A_n$ denotes the number of permutations.
CLAIM: $a_i\neq n$ for $1\le i\le n-2$ .
PROOF: Note that if $a_i \le k-2$ , then $a_k=k-2$ or $a_k \le k-3$ . If $a_k = k -2$ , then we have
$a_{k-1} (k-1) < (k-1)^2 \implies a_{k-1} < k-1 \implies a_{k-1} \le k-2.$ If $a_k = k-2$ , then $a_{k-1} \ne k-2$ , hence $a_{k-1} \le k-3$ . Otherwise if $a_k \le k-3$ , then we have
$a_{k-1} (k-1) \le k(k-3) < (k-1)(k-2) \implies a_{k-1} < k-2 \implies a_{k-1} \le k-3.$ This is a contradiction, so the only remaining cases to be checked are $a_{n-1}=n$ or $a_n=n$ which is trivial recurrence. Hence, $A_n=A_{n-1}+A_{n-2}$ where $A_1=1$ and $A_2=2$ so $\boxed{A_n=F_{n+1}}$ .

This post has been edited 2 times. Last edited by L13832, Jul 13, 2024, 6:14 PM

Z K Y

The post below has been deleted. Click to close.

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

PEKKA

1852 posts

PEKKA

#69 h Jul 21, 2024, 9:24 PM

Y by

The answer is $F_{n+1},$ where $F_k$ is the kth Fibonacci number.
The key claim is that in any permutation that works (interchangeable with the description "is good"), $n=a_{n-1}$ or $n=a_n.$
FTSOC assume there is a $k$ with $1 \le k \le n-2$ such that we have a good permutation and $a_{k}=n.$
First, we establish that all the numbers $a_i$ with index higher than $k$ must be at least $k,$ else there is a value $m$ such that $ma_m<kn,$ which does not happen in a good permutation.
Then the only option for $a_n$ is $k,$ as a lower index causes the $ia_i$ value to be less than $kn.$
Then, every number in between must have the exact value $kn.$
However, any permutation of the numbers that are at least $k$ into the indices $a_{k+1}, a_{k+2}\dots a_n$ is $\sum _{i=1}^{k}(n-k+i)(n-i)$ by the rearrangement inequality. This sum equals $kn(n-k)+\frac{k^2(k+1)}{2},$ which exceeds $kn(n-k).$
This is a contradiction.
Therefore, $n=a_{n-1}$ or $n=a_n.$
Now we use induction to count the number of permutations.
Base case: $n=2,3.$ These cases are true, verified on paper (too lazy to type)
Inductive step: Assume for the values $n=k-1,k$ there are $F_k$ and $F_{k+1}$ good permutations. Now consider $n=k+1.$
In the case of $n=a_{n-1},$ $a_n=n-1$ is the only option, then the earlier terms are permuted in $F_k$ ways
When $a_n=n,$ the earlier terms are permuted in $F_{k+1}$ ways.
Therefore, in total for the $k+1$ case there are $F_k+F_{k+1}=F_{k+2}$ total ways to permute, completing the induction. Q.E.D.

Z K Y

The post below has been deleted. Click to close.

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

qwertyuiop123456789

6 posts

qwertyuiop123456789

#70 h Jul 29, 2024, 2:40 PM

Y by

Click to reveal hidden text
I think just split into 2 cases whether $a_n$ and $a_{n-1}$ are $n$ and $n-1$ or not.
Maybe induction is also ok?
Btw I am a noob at LaTeX so I can't type my solution out

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

401 posts

alexanderhamilton124

#71 h Aug 25, 2024, 10:23 AM

Y by

Our answer is $\text{F}_{n + 1}$ , with $\text{F}_0 = 1, \text{F}_1 = 2$ . Let $F_n$ denote the number of permutations for $n$ . First off, if $n$ is in $n ^{\text{th}}$ spot, then the number of permutations is simply $\text{F}_{n - 1}$ , since $n^2 > (n - 1)^2$ . If $n$ is the $(n - 1)^{\text{th}}$ spot, then $n - 1$ is forced to be in the $n^{\text{th}}$ spot, since $n(n - 1) > n(n - 2)$ . Now, our number of permutations is simply $F_{n - 2}$ , as $n(n - 1) > (n - 2)^2$ .

Now, we claim that $n$ can't be in the spots $1, 2, \dots, n - 2$ . Say $n$ is in the $(n - k) ^ {\text{th}}$ spot, where $k \geq 2$ . Observe that $n(n - k) > (n - k - 1)n$ , so numbers $\leq n - k - 1$ , can't be in the spots ahead of where $n$ is positioned. So $n - k, n - k + 1, ..., n - 1$ , are forced to be in the spots ahead of $n$ . Note that $n - k$ is forced to be in the $n^{\text{th}}$ spot, and since $n(n - k) < (n - k + 1)(n - 1)$ , we have a contradiction.

So, $\text{F}_n = \text{F}_{n - 1} + \text{F}_{n - 2}$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

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

MathWithAnE

7 posts

MathWithAnE

#72 h Sep 12, 2024, 5:16 PM

Y by

Counting solution :coolspeak:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1328 posts

ezpotd

#73 h Sep 27, 2024, 10:33 PM

Y by

The answer is $F_{n + 1}$ where $F_i$ is the $i$ th Fibonacci number. We prove this by induction. The base cases of $n = 1,2$ are trivial.

Inductive Step: We consider the placement of the element $n$ . If it is in the end, we get $F_{n}$ valid sequences. If it is second to the end, we must have $a_n \cdot n \ge n(n - 1)$ , forcing $a_n = n - 1$ , so we just need the condition to hold for the first $n - 2$ elements, giving another $F_{n - 1}$ valid sequences. We now claim that $n$ cannot be placed any further back. Assume for the sake of contradiction that it is placed at $n - k$ . Then we have $k$ elements less than $n$ after $n$ , at least one of these $a_i$ is at most $n - k$ . If it is less than $n - k$ , we would have $n(n - k) > ia_i$ , since $n \ge i, n - k > a_i$ , so it must be exactly $n - k$ (furthermore all of these elements located after $n$ are at least $n - k$ to satisfy the inequality). Furthermore, since $i(n - k) \ge (n - k)n$ , we have $i \ge n$ , forcing $i = n$ . So we have for $n > i > n - k$ , $na_n \ge ia_i \ge (n - k)a_{n - k}$ , so $ia_i = n(n - k)$ , however just consider when $a_i = n -1$ , we must have $i > n - k$ since the elements located after $n$ are all the elements from $n - 1$ to $n - k$ in some order. Then we have $ia_i \ge (n - 1)(n - k + 1) = n^2 - kn + k - 1 > (n)(n - k)$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

Bonime

38 posts

Bonime

#74 h Oct 30, 2024, 10:09 PM

Y by

Let $f(n)$ be the number of permutations satisfying the statement. The answer is $\boxed{f(n)=F_{n+1}=\frac{(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}}{\sqrt{5}}}$

We´re prove it by a strong induction in $n$ :

Base Case: For $n=1$ we just have the permutation {1}, so, $f(1)=F_2=1$ . For $n=2$ we have {1,2} and {2,1}, so $f(2)=F_3=2$ . $\blacksquare$

Induction Hypothesis: Assume the afirmation is valid for all $m\leq n-1$ .

Inductive Step: Let´s prove the following lemma:

Lemma: In a permutation such that $a_1\le 2a_2\leq 3a_3\le\dots na_n$ we just can have $n=a_{n-1}$ or $n=a_n$

Proof: FTSoC, assume that we can have $n=a_{n-2}$ . Clearly, if this case is impossible, the other ones will be too. Look at the position of $n-2$ in that permutation: Since $n(n-2)>(n-1)(n-2)$ for $n>2$ , we must have $a_n=n-2$ . But, note that we won´t have numbers to place in $a_{n-1}$ since $(n-2)a_{n-2}=n^2-2n$ and $na_n=n^2-2n$ , so we´ll must have $(n-1)a_{n-1}=n^2-2n$ but $(n-1)\nmid n^2-2n$ for $n>1$ . Contradiction! $\blacksquare$

Therefore, if $n+a_n$ , we´ll have $f(n-1)=F_n$ permutations for the other numbers and if $n=a_{n-1}$ , we´ll must have $a_n=n-1$ therefore we´re going to have $f(n-2)=F_{n-1}$ permutations. Hence by the additive principle, $f(n)=f(n-1)+f(n-2)=F_n+F_{n-1}=F_{n+1}=\frac{(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}}{\sqrt{5}}$ as we wanted to show $\blacksquare$

This post has been edited 1 time. Last edited by Bonime, Oct 31, 2024, 10:14 AM

Z K Y

The post below has been deleted. Click to close.

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

de-Kirschbaum

204 posts

de-Kirschbaum

#75 h Feb 26, 2025, 8:48 PM

Y by

Note that the largest number $n$ could either be in position $n-1$ or position $n$ because if it is in position $n-2$ then we must have $n-1$ in position $n-1$ and that doesn't work as $(n-1)^2=n^2-2n+1 > n(n-2)=n^2-2n$ . Further note that if $n$ is in position $n-1$ then $n-1$ must be in position $n$ , and that $(n-2)^2 =n^2-4n+4 \leq (n-1)n=n^2-n$ for all $n \geq 3$ .

Thus, if we let $p_n$ denote the number of valid permutations for $1,2,\ldots, n$ we must have that $p_n=p_{n-1}+p_{n-2}$ for all $n \geq 3$ . The base cases are $p_1=1, p_2=2$ (easily derivable manually) so $p_n=f_{n+1}$ where $f_i$ is the $i$ th fibonacci number indexed at $1$ .

This post has been edited 1 time. Last edited by de-Kirschbaum, Feb 26, 2025, 8:53 PM

Z K Y

The post below has been deleted. Click to close.

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

eg4334

639 posts

eg4334

#76 h Mar 14, 2025, 3:11 AM

Y by

The answer is $F_{n+1}$ in the notation of fibonacci numbers. Let the answer be $x_n$ . Basically if $n$ pairs with $n$ , then we only need to decide the rest and we can ignore the last one, giving $x_{n-1}$ . If $n$ pairs with $n-1$ , then $n-1$ must pair with $n$ . The rest are then indepdent giving $x_{n-2}$ . If $n$ pairs with $n-2$ then to satisfy the condition $n-1$ must pair with $n-1$ which leaves nothing for $n$ which works. Then $x_n = x_{n-1} + x_{n-2}$ and the rest is trivial.

Z K Y

The post below has been deleted. Click to close.

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

Maximilian113

578 posts

Maximilian113

#77 h Apr 17, 2025, 4:05 PM

Y by

We claim that the answer is $\boxed{F_{n+1}}$ where $F_n$ is the $n$ th Fibonacci Number. We proceed with induction. The base cases, $n=1, 2$ are trivial, so if the proposition holds for $n \leq k-1$ where $k \geq 3$ then for $n=k,$ suppose that $a_r=k$ with $r < k.$ Then $ra_r=rk,$ so all $\ell < r$ must have occured somewhere in $a_x$ with $x < r.$ Therefore for the inequalities to hold $a_k=r,$ so $rk=ra_r \leq (r+1)a_{r+1} \leq \cdots \leq (k-1)a_{k-1} \leq ka_k=kr.$ Hence equality holds so $(k-1)a_{k-1} = kr.$ But $\gcd(k, k-1) = 1 \implies (k-1) | r \implies r=k-1.$ Therefore $a_{k-1}=k, a_k=k-1$ and by the inductive hypothesis there are $F_{k-1}$ ways. But if $a_r=k$ with $r=k$ by the inductive hypothesis there are $F_k$ ways, so adding yields $F_k+F_{k-1}=F_{k+1}$ ways. QED

Z K Y

The post below has been deleted. Click to close.

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

SYBARUPEMULA

26 posts

SYBARUPEMULA

#78 h May 17, 2025, 12:39 AM

Y by

Claim: $a_j \geq j - 1$ , for $1 \leq j \leq n$ .
For $j = 1$ is trivial. Assume FTSOC, $a_i \leq i - 2$ for some $i \geq 2$ . Thus
$(i-1)a_{i-1} \leq i\cdot a_{i} \Rightarrow a_{i-1} \leq \frac{i}{i-1} \cdot a_i < a_i + 1$ The last inequality is true as $i - a_i > 1 \Rightarrow i - a_i - 1 > 0 \Rightarrow i\cdot a_i + i - a_i - 1 > i\cdot a_i \Rightarrow (a_i + 1)(i - 1) > i\cdot a_i$ where $a_i, i > 0$ . Hence as $a_{i-1} < a_i + 1$ and $a_{i-1} \neq a_i$ , then $a_{i-1} \leq a_i - 1 \leq a_i - 3$ . Continuing this gives $a_1 \leq -2$ . Contradiction. So our claim proved.

Then with our claim, $a_n = n$ or $a_n = n-1$ . Denote $b_n$ as the number permutations $(a_1, a_2, ..., a_n)$ .
If $a_n = n$ , the number permutation is simply $b_{n-1}$ .

If $a_n = n-1$ , there must exist $k$ such that $a_k = k - 1, a_{k-1} = n$ . To prove this, this is because $a_n = n -1$ , the value of $a_{n-1} = n-2$ or $a_{n-1} = n$ . If $a_{n-1} = n-2$ , the value of $a_{n-2}=n-3$ or $a_{n-2}=n$ . If $a_{n-1}=n$ , thus we are done. Repeating the same process until $a_{k-1} = n$ , hence our statement was proved. Thus,
$(k-1)a_{k-1} \leq k\cdot a_k \Rightarrow (k-1)n \leq k(k-1)$ .
This gives $k \geq n$ , hence $k = n$ , so $a_{n-1} = n$ . Thus, the number permutation in this case is $b_{n-2}$ .

Then, we have $b_n = b_{n-1} + b_{n-2}$ . It's easy to see that $b_1 = 1, b_2 = 2$ . Thus, $b_n = F_{n+1}$ where $F_n$ denote the $n$ -th Fibonacci number.

This post has been edited 1 time. Last edited by SYBARUPEMULA, May 17, 2025, 12:40 AM

Z K Y

The post below has been deleted. Click to close.

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

maromex

230 posts

maromex

#79 h May 27, 2025, 5:20 PM

Y by

Let $P(n)$ denote the answer to this question for each positive integer $n.$

First, in the cases $n = 1$ and $n = 2,$ check all permutations to see that $P(1) = 1$ and $P(2) = 2.$

Now assume $n \ge 3.$ We will do cases on which of the $a_i$ is equal to $n.$

If $a_n = n,$ then notice that $(n-1)a_{n-1} \le (n-1)(n-1) < n^2,$ so the last inequality is always true. The count of the number of ways to permute $a_1, a_2, \ldots a_{n-1},$ to make the rest of the inequalities true, is equal to $P(n-1).$

If $a_{n-1} = n,$ then notice that $(n-1)n \le na_n \le n(n-1),$ which implies $a_n = n-1.$ Then, $(n-2)a_{n-2} \le (n-2)(n-2) < (n-1)n,$ so the second last inequality is true. The count of the number of ways to permute $a_1, a_2, \ldots a_{n-2},$ to make the rest of the inequalities true, is equal to $P(n-2).$

Now for the "other" case: suppose that for some $m < n-1$ we have $a_m = n.$ Notice that, for all $m+1 \le k \le n,$ we must have $mn \le ka_k.$ Because there are $n - m$ different $a_k$ and all of them must be different and at most $n-1,$ one of them must be $m$ or less. In order to have $mn \le ka_k$ for the $k$ such that $a_k \le m,$ we have $mn \le ka_k \le km \le mn \implies k = n \text{ and } a_k = m.$ Therefore, we have $na_n = mn.$ This causes us to have $mn \le ka_k \le mn$ for all $m+1 \le k \le n-1,$ therefore $ka_k = mn.$ But if we choose $k = n - 1,$ we get $a_k = \frac{mn}{n-1} = m + \frac{m}{n-1}.$ This is not an integer because $m < n-1,$ so we have a contradiction; this case's assumption is false.

We conclude that $P(n) = P(n-2) + P(n-1)$ for all $n \ge 3.$ Therefore the values of $P(n)$ follow the Fibonacci sequence.

Z K Y