Let $m_1, m_2, \ldots, m_n$ be a collection of $n$ positive integers, not necessarily distinct. For any sequence of integers $A = (a_1, \ldots, a_n)$ and any permutation $w = w_1, \ldots, w_n$ of $m_1, \ldots, m_n$, define an $A$-inversion of $w$ to be a pair of entries $w_i, w_j$ with $i < j$ for which one of the following conditions holds: $a_i \ge w_i > w_j$ $w_j > a_i \ge w_i$, or $w_i > w_j > a_i$. Show that, for any two sequences of integers $A = (a_1, \ldots, a_n)$ and $B = (b_1, \ldots, b_n)$, and for any positive integer $k$, the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $A$-inversions is equal to the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $B$-inversions.
Problem
Source: USAMO #2
Tags: AMC, USA(J)MO, USAMO, 2017 USAMO, combinatorics, Hi
20.04.2017 02:16
Do you think proving trivial case where all m are distinct can salvage anything?
20.04.2017 02:16
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem.
20.04.2017 02:18
20.04.2017 02:22
I put that above + proving it for $n=2$ and writing down: "assume it holds true for $n=2, \ldots, n-1.$ For $n$ WLOG let $w_{n} = \max \{w_1, w_2, \ldots, w_{n} \},$ and it suffices to show that the number of new $A$-inversions created with $w_n$ as one of the pair can be bijected to another permutation with the same number of $B$-inversions created with $w_n$ as one of the pair, which is easy" (I don't think this is even true lol). How much does this worth? (not expecting much...)
20.04.2017 02:22
infiniteturtle wrote:
I got the first part. Do you think I would get a point?
20.04.2017 02:24
infiniteturtle wrote:
How does this work? I actually don't see. (I'm sure there's a solution using this $f_A$ but I can't tell what it is.)
20.04.2017 02:27
Compare $A$ and $A'=(a_1+1,a_2,a_3,..., a_n)$. (I guess I forgot to say that $w_i,w_j$ make an inversion iff $w_j\neq w_i, a_i$ and $f_A(i,j)\ge 0.$)
20.04.2017 02:29
We create a bijection to a sequence $B = (b_1, b_2, ... ,b_n)$ such that every integer $B$ is greater than everything in the permutation. Let $A$ be an arbitrary sequence. For each permutation $m_1. m_2, .. ,m_n$ define the inversion set with respect to A of $m_i$ to be all the $m_j$ such that $(m_i, m_j)$ is an A-inversion. And let $In_A(m_i)$ be the cardinality of the inversion set with respect to A of $m_i$ For each sequence $M = m_1, m_2, ... , m_n$ we create a permutation such that the number of A-inversions of M is equal to the number of $B$-inversions. Call this sequence $p_1, p_2, ... ,p_n$. We create this sequence backwards. If $In_A(m_{n-1}) = 1$ then we let $p_{n-1} > p_n$ and if $In_A(m_{n-1}) = 0$ then we let $p_{n-1} \le p_n$. Similarly if $In_A(m_{n-2}) = 2$ then we let $p_{n-2}$ be greater than the last 2 terms, if it's 1 then in the middle and if its 0 then less than both of them. We continue in this fashion until we create a well defined sequence of $p_1, p_2, ... p_n$ which has the same number of $B$-inversions. (This is because the number of $B$ inversions of $p_1, p_2, ... , p_n$ is when $i<j$ and $p_i > p_j$ and by construction this is the same number of $A$-inversions of the sequence $M$) All that remains to be show is that if we have 2 sequences $t_1, t_2, ... ,t_n$ and $q_1, q_2, ... ,q_n$ such that $In_A(t_i) = In_A(q_i)$ then we have that these 2 sequences are the same. The casework for this is pretty silly, just start with $In_A(t_1) = In_A(q_1) \implies t_1 = q_1$ and then continue in this fashion for the rest of the sequence we easily see that this is a bijection. We have found a bijection to a constant set which preserves the number of inversions. Thus, the number of permutations with $k$ inversions is constant regardless of the sequence $A$ as desired. Wait somebody pls check this
20.04.2017 02:32
So I tried to fakesolve this, and then somehow my fakesolve turned into a valid solution. So essentially I used induction to prove that it was sufficient to prove for all a_i's equal. Then I managed in the last 10 minutes to find what I called a "transitive comparison $*>$" (roughly a redefinition of $>$), such that if $m_i*>m_j$ then it is counted as an $A$-inversion. I just hope my proof is complete enough and understandable enough to get 7...this one was difficult. Do you think this counts as the algebra problem? It felt like algebra to me (please don't take away my combo ).
20.04.2017 02:37
Can someone check if this works? Edit: this works Induction on $n$ trivially gives that the result is true for all distinct, and we replace integer with reals because it makes our life easier. Now, let $F_k$ be the number of permutations of our original sequence $M$ that give $k$ $A$-inversions. We will construct a new sequence $M'$ by taking each duplicated set $m_{i+1},...,m_{i+j}$ and subtracting very small (different and $<1$) values to make them pairwise distinct. Let $F_k'$ be the same as $F_k$ but for this new sequence. I claim that the $F_k'$ are related to the $F_k$ by a system of linear equations with coefficients independent of $A$. Consider the $A$-inversions added to a permutation of $M$ by performing our operation and sending it to a permutation of $M'$. Because of the way we dealt with the duplicated elements, the only inversions we add are those that lie solely amongst each group of formerly duplicated values. By construction the $a_i$ cannot lie in between 2 of these values, so these $A$-inversions are just of type 1 and 3, i. e. they are just inversions in the traditional sense, thus the number of inversions added is independent of the $a_i$. If $M$ has duplicate sets of size $j_1,...,j_x$, then we can add at most $L=\binom{j_1}{2}+...+\binom{j_x}{2}$ inversions by permuting the duplicate values. Thus we can write $F_k'=c_{k,0} F_k+c_{k,1} F_{k-1}+...+c_{k,L} F_{k-L}$ where the $c_{i,j}$ are independent of the $a_i$. These equations form a triangular matrix which has a unique solution, thus the values of $F_k$ are uniquely determined from those of $F_k'$ so the $F_k$ are independent of $A$.
20.04.2017 02:43
Shaddoll wrote:
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step.
20.04.2017 02:49
pieater314159 wrote: Shaddoll wrote:
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step. Hm yeah the number of $A$-inversions involving $w_1$ depends on $a_1$ unless I'm being dumb.
20.04.2017 02:52
Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall
20.04.2017 03:49
mathwizard888 wrote: pieater314159 wrote: Shaddoll wrote:
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step. Hm yeah the number of $A$-inversions involving $w_1$ depends on $a_1$ unless I'm being dumb. I think you are misunderstanding my solution. We set the rest of the $a_i$s to be equal to $a_1$(which I showed we could do by induction). And then we prove that no matter what we set that equal amount to, it gives the same amount of ways for $k$ A-inversions.
20.04.2017 03:52
bobthesmartypants wrote: Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall Ok so I came up with the circle epiphany 5m before the end of the contest, but I think something like this works:
20.04.2017 03:52
@Shaddoll I don't get how you showed that it's fine to set all of the $a_i$ equal.
20.04.2017 03:54
infiniteturtle wrote: Compare $A$ and $A'=(a_1+1,a_2,a_3,..., a_n)$. I proved that it suffices to do this, but was not able to actually prove the problem is true for $A$ and $A'$. Will this give me any marks?
20.04.2017 03:55
High wrote: Do you think proving trivial case where all m are distinct can salvage anything? I also only proved the case where all of the $m_i$ are distinct. Can someone explain why this case is trivial? (It took me 4 pages just to prove this case.) Was the full problem significantly harder than the case where they're distinct? During the test, I thought I had proved the bulk of the problem and would get most of the points, but after seeing this post, I'm not so sure anymore. Basically, I want to know whether this would be scored 7- or 0+.
20.04.2017 04:01
I wouldn't call it completely trivial (I did it by outlining a recursive process -> every choice for $w_1$ contributes a different amount), but proving the actual requires a lot more insight, based on solutions I've seen. Definitely a 0+
20.04.2017 04:28
I actually got this trick from a cs problem, but I forgot the source :/
20.04.2017 08:42
If my collection is $1,1,2$, is the permutation $(1,2,1)$ counted once or twice?
20.04.2017 09:03
Hmm this problem seems v tough I feel like this should've been a C3
20.04.2017 17:05
Can someone please provide an English translation of this problem? I wonder what the problem writer was thinking when they wrote it.
20.04.2017 18:12
mathtastic wrote: Can someone please provide an English translation of this problem? I wonder what the problem writer was thinking when they wrote it.
20.04.2017 23:52
Doing it for distinct is easy enough, though I twisted it a bit (brought matrices into the mix >.>). Here's my solution for non-distinct:
Could someone tell me if there's any flaw? Cause this felt a bit too natural and easy compared to some of the solutions above, so I feel like I'm missing something. Also, is the solution for distinct really trivial to write? I tried to emulate the contest at home, and writing up that part of the solution took me a long time. Is there a simple way to prove that the number of inversions involving $a_1$ is distinct for each $m_i$, taking all values from $0$ to $n-1$?
21.04.2017 17:29
mota60ceng wrote: bobthesmartypants wrote: Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall Ok so I came up with the circle epiphany 5m before the end of the contest, but I think something like this works:
What about $a_1, 1, a_2, 2$ and $b_1, b_2, ?, ?$ Then 1 and 2 should both be placed in the first spot. I was thinking this same circle thing too.
22.04.2017 08:23
28.04.2017 00:02
Solved this a week too late Here's a pretty straightforward solution with generating functions: First, we may order $m_1,m_2,\ldots,m_n$ anyway we want as we only care about their permutations, so order them to \[m_1=m_2=\ldots=m_{c_1}<m_{c_1+1}=m_{c_1+2}=\ldots=m_{c_2}<\ldots<m_{c_1+c_2+\ldots+c_{i-1}+1}=m_{c_1+c_2+\ldots+c_{i-1}+2}=\ldots=m_{c_1+c_2+\ldots+c_i}\]where $c_1+c_2+\ldots+c_i=n$. For convenience, set $n_0=0$ and $n_j=m_{c_j}$ for $j>0$. Note that we may assume that $a_j\in\{n_0,n_1,\ldots,n_i\}$ as the only thing that affects the conditions is the interval out of $(-\infty,n_1),[n_1,n_2),[n_2,n_3),\ldots,[n_{i-1},n_i),[n_i,\infty)$ that $a_j$ lies in. Now, we induct on $n$ to show that \[c_1!\cdot c_2!\cdot\ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t\]is the generating function such that the coefficient of $t^k$ is the number of permutations of $m_1,m_2,\ldots,m_n$ with exactly $k$ $A$-inversions for any $A$, which will imply the problem statement as this expression is independent of $A$. Here, we define the $t$-factorial as $j!_t=\frac{(1-t)(1-t^2)\ldots(1-t^j)}{(1-t)^j}$ for any nonnegative integer $j$ and the $t$-multinomial as $\binom n{c_1,c_2,\ldots,c_i}_t=\frac{n!_t}{c_1!_t\cdot c_2!_t\cdot \ldots\cdot c_i!_t}$.
For the base case of $n=1$, our generating function is $1\binom11_t=1$, which is correct as we only have to consider the identity permutation which has no inversions. For the inductive step, suppose that $a_1=n_p$ and $w_1=n_q$. Note that if $w_1$ is in $r$ inversions, then the generating function for the number of permutations of $m_1,m_2,\ldots,m_n$ with $w_1=n_q$ and a fixed number of inversions is \[t^r\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]with the second term derived from the inductive hypothesis. If $p\ge q$, then $w_1,n_j$ is an inversion if $j>p$ or $j<q$, leading to $c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i$ inversions involving $w_1$. If $p<q$, then $w_1,n_j$ is an inversion if $p<j<q$, leading to $c_{p+1}+c_{p+2}+\ldots+c_{q-1}$ inversions involving $w_1$. Summing over all possible values of $w_1$ (noting that there are $c_q$ times when $w_1=n_q$), it suffices to show that \[\sum_{q=1}^p c_q\cdot t^{c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i}\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]\[+\sum_{q=p+1}^i c_q\cdot t^{c_{p+1}+c_{p+2}+\ldots+c_{q-1}}\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]\[=c_1!\cdot c_2!\cdot\ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t.\]This is much easier than it looks. Dividing both sides by $\frac{c_1!\cdot c_2!\cdot \ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t}{1-t^n}$, we are left with showing \[\sum_{q=1}^p t^{c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i}\cdot(1-t^{c_q})+\sum_{q=p+1}^i t^{c_{p+1}+c_{p+2}+\ldots+c_{q-1}}\cdot(1-t^{c_q})=1-t^n\]which is clearly true as the LHS telescopes to the RHS.
26.03.2020 00:58
Solved with franchester, ingenio, GameMaster402, anish9876, mira74, SD2014, AOPS12142015, huangyi_99, sriraamster, kothasuhas, budu, and mathfun5. We first solve a simpler case of the problem, where the $m_i$ are distinct. Lemma: For $n \in \mathbb{N}$, the number of permutations having $k$ $A$-inversions can be expressed by the coefficient of the $x^k$ term of the generating function $f(x) = \prod_{i=1}^{n} \frac{x^i-1}{x-1}$. Proof: We proceed by induction on $n$. The base case $n = 1$ is trivial as no such inversions exist. For $n = 2$, there is only one permutation with $0$ $A$-inversions and only one permutation with $1$ $A$-inversions, corresponding to the generating function $f(x) = x + 1$. Now, assume the lemma holds true for some $n \in \mathbb{N}$. We want to show this is true for $n+1$. Order the positive integers $(m_2,\cdots,m_{n+1})$ by size. Now, add a slot $a_1$ to a permutation $(a_2,\cdots,a_{n+1})$. Let $w_1 = m_y$. If $a_1<m_1$ or $a_1 \ge m_{n+1}$, then the number of new inversions generated to the old permutation is $y - 1$, as we can only generate new inversions from $a_1$ with values less than $w_1$. Otherwise, there exists $y \in \mathbb{N}$ such that $m_z \le a_1 < m_{z+1}$. We proceed with casework on $w_1$: If $w_1 = m_z$ (so $z=y$), then we can have an inversion with any other $w_j$, so this generates $n$ new inversions. If $w_1 = m_{z-c}$, then as long as $w_j$ is not between $a_1$ and $w_1$ (both inclusive), then we can have an inversion with $w_j$, so this generates $n-c$ new inversions. If $w_1=m_{z+c}$, then as long as $w_j$ is between $a_1$ and $w_1$ (both exclusive), then we can have an inversion with $w_j$, so this generates $c-1$ new inversions. Thus, after considering all cases of what $a_1$ and $m_1$ can be, there is always a case that generates $i$ new inversions to our old permutation for all $i$ between $0$ and $n$ inclusive, adding to the inductive hypothesis, our generating function is now $\prod_{i=1}^{n} \frac{x^i-1}{x-1} \cdot (1+x+\cdots+x^n) = \prod_{i=1}^{n+1} \frac{x^i-1}{x-1}$, as desired. $\blacksquare$ We now need to consider when multiple $m_i$s can be equivalent. Assume for some $m_i$ that there are $t$ copies of them. We can replace multiple $m_i$s by $m_i+k\epsilon$ where $\epsilon>0$ and $k$s are distinct. Then we have the same generating function, but we've overcounted by $\frac{f(t)}{t!}$, as there are no inversions between two equivalent integers. So for a general case of our set $(m_i)$, our generating function is $g(x) = \frac{f(x)(t_1!)(t_2!) \cdots (t_l!)}{f(t_1)f(t_2) \cdots f(t_l)}$, where $t_j$ is the number of repetitions of the $j$th smallest element in $(m_i)$. The number of permutations of $(m_i)$ having $k$ $A$-inversions can be expressed by the coefficient of the $x^k$ term. Since this generating function is independent of what the permutations $A$ and $B$ are, the number of permutations of $(m_i)$ having exactly $k$ $A$-inversions is equal to the number of permutations of $(m_i)$ having exactly $k$ $B$-inversions, and we are done. YUH.
25.09.2021 15:10
The following approach leaves out a few steps, but the details can be filled in by taking cases which are done after the main content. Let $m_1\le m_2\le \cdots \le m_n$ without loss of generality. We prove the result by induction on $n$. The result is clear at $n=1$. We first argue that we can assume $m_1<m_2$ and so on. This is because if $m_i = m_{i+1} = \cdots = m_{j-1} = m_j<m_{j+1}$, replacing each $m_k$ for $k\ge j$ with $m_k+1$ and moving each $a_t$ that was equal to $m_i$ to $m_i+1$ will multiply the polynomial by $(1+q+\cdots+q^{j-i})/(j-i+1)$ by analyzing what inversions this adds. So this means we can assume $m_1<m_2<\cdots<m_n$. We can maneuver the $a_2,a_3,\cdots,a_n$ by the induction hypothesis since it only affects the generating function for $n-1$. Then for $a_1$, we have a generating function of $1+q+\cdots+q^{n-1}$ based on the value of $w_1$ regardless of what $a_1$ actually is, so $a_1$ also does not matter and we are done. $\fbox{}$ To see the $(1+q+\cdots+q^{j-i})/(j-i+1)$ leap, note that inversions are only added among the $m_i,\cdots,m_j$ thus we can consider just those. There are no inversions in a constant sequence and in a sequence of $\underbrace{1,1,\cdots,1}_{j-i},2$ as we can WLOG assume we have (since we can always replace $a_s$ with $a_s = \max_{w_i \le a_s} w_i$ for no change), some $w_u$ is equal to $2$ so the only possible inversions are $a_u\ge w_u>w_v$ and $w_u>w_v>a_u$, the number of which is exactly equal to $j-i+1-u$. This replaces the inversions in which it does not matter where $w_u$ is. Note that if $a_1\ge w_1$ there are $n-1-(a_1-w_1)$ inversions and if $a_1<w_1$ there are $w_1-a_1-1$ inversions so varying $w_1$ does cover all terms equally.
17.09.2023 10:56
Does generating function really work? I have spent hours calculating the value of the k inversions,but I gained nothing. The formula seems so ugly.
27.12.2023 00:17
Here's the generating function solution from the OTIS walkthrough. It's quite motivated but still fairly painful to carry out. Notice that it suffices to show the result with $B = (0, 0, \dots, 0)$. For this $B$, I claim: Claim. The number of permutations of $[n]$ with exactly $k$ inversions is given by the coefficient of $q^k$ in $$n!_q = (1+q)(1+q+q^2)\dots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n \frac{1-q^i}{1-q}.$$ Proof. Induction. For $k$ the last term of the permutation $\sigma$, $k$ contributes exactly $k-1$ inversions to $\sigma$ and hence corresponds to a coefficient of $q^{k-1}$ in the product. Thus, adding a term is equivalent to multiplying by $1+q+\cdots+q^{n-1}$. $\blacksquare$ Now we deal with the multiplicity issue. Let $\{x_n\}$ be the increasing sequence of distinct integers that constitutes $\{m_n\}$, and let $e_i$ be the multiplicity of $x_i$ in $\sigma$. Let $F(e_1, \dots, e_m)$ be the generating function for the inversions on a sequence with multiplicities $e_1, \dots, e_m$. Claim. $F(e_1, \dots, e_m)$ is given explicitly by $n!_q \cdot \prod_{i=1}^m \frac{e_i!_q}{e_i!}$. Proof. This is essentially the functional analog of the classic overcounting problem. For any $e_i$ copies of $x_i$, perturb each of them a tiny amount such that any inversions containing exactly one element $x_i$ are preserved; after altering this for each $i$, the inversions are given by $n!_q$. Now, imagine returning all the $x_i$ for each $i$ to be equal; any inversions within the $x_i$ which contribute to the product, globally represented by $q^j$ terms, are replaced with $q^0$ terms. This replaces $e_i!_q$ in the original product with $e_i! \cdot q^0 = e_i!$. Performing this across all such $e_i$ yields the result. $\blacksquare$ Notice that we have $$\frac{e_i \cdot F(e_1, \dots, e_i - 1, \dots, e_m)}{F(e_1, \dots, e_m)} = \frac{1-q^{e_i}}{1-q^n}$$from direct computation on this formula. To finish, we prove by induction that the generating function of inversions with any arbitrary sequence $A$ is also given by $F$. In particular, we need only consider the contributions of the elements $m_i$ with respect to $a_1$. To begin with, for each of the, say $r$, $x_i$ such that $x_i \leq a_1$, $x_i$ contributes $$T_i = e_i \cdot q^{n-(e_i+e_{i+1}+\cdots+e_r)} \cdot F(e_1, \dots, e_i-1, \dots, e_m)$$as one of the $e_i$ $x_i$ forms an inversion with $a_1$ and one of the $e_j$ $x_j$ that is not within the subtracted sum per the given conditions. Similarly, for $x_i > a_1$, $x_i$ contributes $$T_i = e_i \cdot q^{e_{r+1} + \cdots + e_{i-1}} \cdot F(e_1, \dots, e_i-1, \dots, e_m).$$Hence it suffices to show that \begin{align*} F(e_1, e_2, \dots, e_m) &= \sum_{i=1}^m T_i \\ F(e_1, e_2, \dots, e_m)&=\sum_{i=1}^r e_i \cdot q^{n-(e_i+e_{i+1}+\cdots+e_r)} \cdot F(e_1, \dots, e_i-1, \dots, e_m) + \sum_{i=r+1}^m e_i \cdot q^{e_{r+1} + \cdots + e_{i-1}} \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\ 1-q^n &= \sum_{i=1}^r (1-q^{e_i})q^{n-(e_i+\cdots+e_r)}+ \sum_{i=r+1}^m q^{e_{r+1}+\cdots+e_{i-1}}(1-q^{e_i}) \\ 1-q^n &= q^{e_{r+1}+\cdots+e_m} - q^n + 1 - q^{e_{r+1}+\cdots+e_m} \end{align*}as the terms of the sum telescope. This finishes the proof.
18.04.2024 08:13
very hard problem than 5,can someone tell me why to think about generating function?Thanks