The lemmas hide the statement and proofs of the sublemmas; let me know if this style is cumbersome to read. Edit: Broken solution [see post 4]

Say a permutation is good if the ratios $\frac{x_k}{k}$ are all distinct and bad otherwise. Let the inverse of $(x_1, \dotsc, x_n)$ be defined in the usual way (i.e. the inverse $(y_1, \dotsc, y_n)$ satisfies $x_{y_i}=y_{x_i}=i$.) Define an involution to be a permutation which is its own inverse, and a maximal involution to be an involution with at most one fixed point. It is well known that a permutation is an involution if and only if it swaps pairs of elements. Claim. If a permutation is bad, so is its inverse. Proof. Suppose that $\frac{x_i}{i}=\frac{x_j}{j}$. If $(y_1, \dotsc, y_n)$ is the inverse permutation, then \[\frac{y_{x_i}}{x_i}=\frac{i}{x_i}=\frac{j}{x_j}=\frac{y_{x_j}}{x_j}.\]Hence the inverse permutation is bad. $\blacksquare$ Using the claim we can pair good and bad permutations with their inverses, leaving involutions unpaired. It suffices to show that there are an odd number of good involutions. If an involution has at least two fixed points, then $\frac{x_k}{k}=1$ for at least two values of $k$, so it is a bad involution. Hence all good involutions are maximal. We will also need some results on the number of involutions: Lemma. There are an even number of involutions for all $n\geq 2$ and an odd number of maximal involutions for all $n$. Proof. Let $f(n)$ and $g(n)$ denote the number of involutions and maximal involutions respectively. Both proofs will use induction. For involutions, we may either make $1$ a fixed point or pair it with some element, yielding the recursion $f(n)=f(n-1)+(n-1)f(n-2)$. As $f(2)=2$ and $f(3)=4$ are both even, $f(n)$ is even for all $n\geq 2$. If $n$ is odd, then $g(n)=ng(n-1)$ because we must choose a unique fixed point and then pair up the remaining $n-1$ elements. If $n$ is even, then $g(n)=g(n-1)$ because we may ignore the element $n$ to biject to maximal involutions on $n-1$ elements. Hence if $g(n-1)$ is odd, then so is $g(n)$. Furthermore, $g(1)=1$ is odd, so $g(n)$ is odd for all $n$. $\blacksquare$ Recall that we want to show that there are an odd number of good (maximal) involutions. By the lemma, it is equivalent to show that there are an even number of bad maximal involutions. We will represent maximal involutions as a collection of $\left\lfloor\frac{n}{2}\right\rfloor$ pairs of numbers $(i, j)$ with $i < j$, each pair being a pair of numbers swapped by the involution. Note that the ratio $\frac{x_k}{k}=1$ is achieved at most once, and the pair $(i, j)$ creates ratios $\frac{i}{j}$ and $\frac{j}{i}$. Partition the pairs of the involution according to the value of $\frac{i}{j}$, and say that two pairs with the same ratio match. Note that a maximal involution is bad if and only if it has matching pairs. For example, the involution $(1, 2), (3, 6), (4, 8), (5, 7)$ is partitioned into $\{(1, 2), (3, 6), (4, 8)\}$ and $\{(5, 7)\}$, and $(1, 2), (3, 6), (4, 8)$ all match each other. Define a Swapnil of two matching pairs $(i_1, j_1)$ and $(i_2, j_2)$ with $i_1 < i_2$ as replacing them by $(i_1, i_2)$ and $(j_1, j_2)$. The two pairs match if and only if $i_1j_2=j_1i_2$, so Swapnils will take matching pairs to matching pairs. The next step is to define an adjacency on the set of bad maximal involutions. We say $\sigma_2$ is a neighbor of $\sigma_1$ if we can partition the pairs of $\sigma_1$ into some matching pairs and some singletons, perform Swapnils on all the pairs, and obtain $\sigma_2$. Since matching pairs will still match afterwards, we can Swapnil back from $\sigma_2$ to $\sigma_1$. This shows that we have a symmetric relation. Furthermore, this maps bad maximal involutions to bad maximal involutions. To count the number of neighbors of a bad maximal involution, observe that all neighbors are found by creating involutions on the sets of matching pairs independently and then subtracting $1$ for the identity. For the example $(1, 2), (3, 6), (4, 8), (5, 7)$ from earlier, which has matching sets of size $3$ and $1$, the number of neighbors is $f(3)f(1)-1=3$ (with the same $f$ as the lemma from earlier). In general, the number of neighbors is \[\prod_Sf(\lvert S\rvert)-1.\]Since any bad maximal involution has some matching pair, there is some set of matching pairs $S$ with $\lvert S\rvert\geq 2$. Then $f(\lvert S\rvert)$ is even, so the product is even and the number of neighbors is odd. Finally, being neighbors defines a graph on the set of bad maximal involutions where the degree of every vertex is odd. The sum of the degrees is twice the number of edges, which is even. Hence there are an even number of bad maximal involutions, which solves the problem.

qbzvavba wrote: Sublemma 2.2: The number of illegal permutations with zero or one fixed point, that also satisfy $\pi(x) = \pi^{-1}(x)$, is even. Proof: Since $\pi$ is illegal, but there cannot be two fixed points, it must be that $\pi(a)=na$ and $\pi(b)=nb$ for some $n\ne 1$. But it is also true that $\pi(na)=a$ and $\pi(nb)=b$ because $pi(x)=\pi^{-1}(x)$. Suppose we define $\pi'$ so that $\pi'(a)=b$, $\pi'(na)=nb$, $\pi'(b)=a$, $\pi'(nb)=na$, and for all other $x$, $\pi(x)=\pi'(x)$. This function $\pi'$ also has the same number of fixed points as $\pi$, and is equal to its own inverse. Further, $\pi \ne \pi'$; if we tried to set $b=na$ so that this would be true, then $\pi(na)=n^2a$, but $\pi(na)=a$, so $n=1$, but this is a contradiction with setting $n\ne 1$. Since the elements of this set can be paired, there are an even number of elements. You fell into the trap! The pairing you defined isn't actually invertible (consider something like, in cycle notation, the permutations $(12)(36)(48)(57)$, $(12)(34)(68)(57)$, and $(13)(26)(48)(57)$). You might think you can easily patch this up, but... you really can't. I'm almost positive that there's no nice involution on the set of illegal permutations.

I can testify to the above, as while trying to do sublemma 2.2, my proof devolved into BS

cpma213 wrote: I can testify to the above, as while trying to do sublemma 2.2, my proof devolved into BS same so I proved that most permutations have inverses or whatever they're called then if the number of 2-cycles isn't maximal they're all bad, and there's an odd count for this then tried to prove that number of bad permutations with 2-cycles maxed out was even, but had no time left and couldn't do it anyway will this get 2+?

brian22 wrote: qbzvavba wrote: Sublemma 2.2: The number of illegal permutations with zero or one fixed point, that also satisfy $\pi(x) = \pi^{-1}(x)$, is even. Proof: Since $\pi$ is illegal, but there cannot be two fixed points, it must be that $\pi(a)=na$ and $\pi(b)=nb$ for some $n\ne 1$. But it is also true that $\pi(na)=a$ and $\pi(nb)=b$ because $pi(x)=\pi^{-1}(x)$. Suppose we define $\pi'$ so that $\pi'(a)=b$, $\pi'(na)=nb$, $\pi'(b)=a$, $\pi'(nb)=na$, and for all other $x$, $\pi(x)=\pi'(x)$. This function $\pi'$ also has the same number of fixed points as $\pi$, and is equal to its own inverse. Further, $\pi \ne \pi'$; if we tried to set $b=na$ so that this would be true, then $\pi(na)=n^2a$, but $\pi(na)=a$, so $n=1$, but this is a contradiction with setting $n\ne 1$. Since the elements of this set can be paired, there are an even number of elements. You fell into the trap! The pairing you defined isn't actually invertible (consider something like, in cycle notation, the permutations $(12)(36)(48)(57)$, $(12)(34)(68)(57)$, and $(13)(26)(48)(57)$). You might think you can easily patch this up, but... you really can't. I'm almost positive that there's no nice involution on the set of illegal permutations. yeah I tried that and failed. I'm betting inverses is worth something but probably not much.

mathisawesome2169 wrote: cpma213 wrote: I can testify to the above, as while trying to do sublemma 2.2, my proof devolved into BS same so I proved that most permutations have inverses or whatever they're called then if the number of 2-cycles isn't maximal they're all bad, and there's an odd count for this then tried to prove that number of bad permutations with 2-cycles maxed out was even, but had no time left and couldn't do it anyway will this get 2+? 2+ is definitely a stretch. That last step is basically the crux of the problem. That sounds like 1 point at most to me.

My solution was 14 pages long. I've discussed this problem with a bunch of other moppers, and I'm pretty sure I'm the only one who actually solved the problem, due to a common mistake that most of the MOPpers made. Props to a1267ab for also finding a correct solution, and thank you to qbzvavba for helping to demonstrate just how hard this problem really is. EDIT: I've been made aware that a1267ab is a MOPper. Evidently, I'm not the only MOPper who solved it.

Feel free to ask questions in this thread if you need me to explain any part of the proof better.

By request, I am posting my write-up of the official solution (which is the same as the one in post #3). To set the record straight I did not solve this problem.

Does anyone have a solution involving determinants of matrices and/or vectors? I observed that the condition is equivalent to none of the determinants of the matrix i j $x_i$ $x_j$ being zero, for all $1 \leq i < j \leq n$, but I was unable to make progress using this method and found the involution (almost-)pairing a while later.

I know this is wrong, but can someone kindly point out the mistake : Use PIE on pairs of expressions that are equal to get the total number of permutations that don't work. Let for some $k,l$ , we have $x_k/k=x_l/l$. Now, having fixed the numbers at positions $k,l$, the rest can be permuted arbitrarily. When taking unions as well, we can fix some and permute the rest. Similarly proceeding, we will get a sum of terms, where each term will be multiplied by $k!$ for some $k>1$ except the last term, which represents the intersection of all the sets, ie which is the identity permutation , which will contribute $1$. As the the number of permutations that don't work is even, we are done.

Bump.....

I believe that this solution is very similar to v_Enhance's and ab1267ab's. But I feel like writing this on my own. I admitted seeking the first claim back in 2018. First insight. Claim : If permutation $\pi$ works, then so is $\pi^{-1}$. Proof : If the ratios are $\tfrac{x_1}{1}, \tfrac{x_2}{2},...,\tfrac{x_n}{n}$ then taking inverse change the ratios to $\tfrac{1}{x_1}, \tfrac{2}{x_2},...,\tfrac{n}{x_n}$. Thus it suffices to consider only involution. Note that this involution must have at most one fixed points as otherwise two ratios are becoming $1$. This means it has no fixed points when $n$ is even and exactly one fixed point when $n$ is odd. We will now view the involution as a partition into $\lfloor n/2 \rfloor$ disjoints pair such that the ratios between pairs are distinct. Now the second insight is if we have pairs $(a,b)$ and $(c,d)$ with $a : b = c : d$, then we can replace this pair with $(a,c)$ and $(b,d)$. Define a foursome as two pairs $(a,b)$ and $(c,d)$ such that $a : b = c : d$, where the order does not matter. Consider a bipartite graph $G = \mathcal{A}\cup\mathcal{B}$ such that Vertices in $\mathcal{A}$ correspond to a partition of $\{1,2,...,n\}$ into $\lfloor n/2\rfloor$ pairs and at most one singletons such that ratio of some pairs are equal. Vertices in $\mathcal{B}$ correspond to a partition of $\{1,2,...,n\}$ into at least one foursome, some pairs and at most one singletons such that ratio of each pair are distinct. Two vertices are joined by an edge if and only if we decompose foursomes into two pairs, then we get exact the same partition. Clearly each vertices in $\mathcal{B}$ have degree one. Now we claim that Claim : Each vertices in $\mathcal{A}$ has odd degree. Proof : Group each pair by equal ratio. It suffices to show that there are odd number of ways to match them into foursomes. Indeed, if there are $k$ pairs, then clearly we have $(2\lfloor k/2 \rfloor + 1)!!$ ways to pair up. Hence we are done. Claim : $\lvert \mathcal{B}\rvert$ is even. Proof : Group all vertices of $\lvert \mathcal{B} \rvert$ by number of foursomes. We claim that the number of vertices in $\mathcal{B}$ having exactly $k$ foursomes is divisible by $2^k$. Indeed, for each foursome $\{(a,b), (c,d)\}$ where $a<b, c<d$, we can replace that into $\{(a,c), (b,d)\}$. As there are exactly $k$ foursomes, we can group each partition by set of entries in each foursome. Each group has $2^k$ elements thus the number is divisible by $2^k$. Now it's easy to finish. Note that the above two claims imply $\lvert \mathcal{A}\rvert$ is even, which means the number of partition which fails to meet the problem's condition is even. Finally, note that the number of such partition is $(2\lfloor n/2 \rfloor+1)!!$ which is odd. Hence the number of good involution is odd as desired.

Solved with eisirrational. Say a permutation is good if $\tfrac{x_k}k$ are all distinct, and bad otherwise. The inverse permutation $(y_1,\ldots,y_n)$ of $(x_1,\ldots,x_n)$ is such that $y_{x_k}=k$ for all $k$. Lemma: [Reduction to involutions] A permutation is good if and only if its inverse permutation is good. Proof. The proof is direct: if $(x_1,\ldots,x_n)$ is good and has inverse $(y_1,\ldots,y_n)$, then for each $i$, $j$, \[\frac{y_i}i=\frac{y_i}{x_{y_i}}\ne\frac{y_j}{x_{y_j}}=\frac{y_j}j,\]so $(y_1,\ldots,y_n)$ is good. $\blacksquare$ It suffices to show there is an odd number of good permutations equal to its own inverse --- i.e.\ involutions. If an involution is good, then it has at most one fixed point. We consider these involutions as maximal matchings on a graph of $n$ vertices labeled $1$, $\ldots$, $n$. Label each edge $i\sim j$, where $i<j$, with the ratio $i/j$. Lemma: [Total maximal matchings] The number of maximal matchings of a graph with $n$ distinguishable vertices is always odd. Proof. Let the number of maximal matchings be $f(n)$. I claim $f(n)=(2\lceil n/2\rceil-1)!!$. Indeed, $f(2k)=(2k-1)f(2k-2)$ by selecting an arbitrary vertex and its neighbor, and $f(2k+1)=(2k+1)f(2k)$ by selecting its fixed point. $\blacksquare$ Lemma: [Main step] There is an even number of bad maximal matchings. Proof. Consider an undirected, nonsimple graph $\mathcal G$ on all bad maximal matchings. The key is to consider the following adjacency: $~$ For a matching $\mathbf x$ in $\mathcal G$, select some (possibly zero) number of disjoint pairs of edges $a\sim b$, $c\sim d$ in $\mathbf x$ with the same label, and swap $b$, $c$. The result is another bad maximal matching --- draw an edge between it and $\mathbf x$. $~$ It is easy to verify the operation above is symmetric. I contend each vertex has even degree. Let $\mathbf x$ be a vertex in $\mathcal G$. For each $\lambda$, let $m_\lambda$ denote the number of edges $a\sim b$ in $\mathbf x$ with $a/b=\lambda$, and let $s_\lambda$ be the number of ways to swap these $m_\lambda$ edges. By similar computation to Lemma 2, \[s_\lambda=\sum_{k\ge0}\binom{m_\lambda}{2k}(2k-1)!!\equiv\sum_{k\ge0}\binom{m_\lambda}{2k}=2^{m_\lambda-1}\pmod2,\]which is even whenever $n_\lambda\ge2$. Finally $\deg\mathbf x$ is the product of $s_\lambda$ over all $\lambda<1$. Since $\mathbf x$ is bad, $n_\lambda\ge2$ for some $\lambda$, so $\deg\mathbf x$ is even. Removing all self-loops, $\mathcal G$ is simple and each vertex of $\mathcal G$ now has odd degree, so $\mathcal G$ has an even number of vertices. $\blacksquare$ In conclusion, the total number of maximal matchings is even, but the number of bad maximal matchings is even, so the number of good maximal matchings is odd, the end.

Interpret a permutation as a bijection $f: \{1, 2, \ldots , n\} \to \{1, 2, \ldots , n\}$ and call a desirable permutation good and undesirable permutations bad. I claim that if $\{f(1), f(2), \ldots , f(n)\}$ is bad then so is $\{f^{-1}(1), f^{-1}(2), \ldots , f^{-1}(n)\}$. This should almost certainly be clear; there must exist distinct $i, j$ for which $\tfrac{f(i)}{i} = \tfrac{f(j)}{j}$, so\[\frac{f^{-1}(f(i))}{f(i)} = \frac{i}{f(i)} = \frac{j}{f(j)} = \frac{f^{-1}(f(j))}{f(j)}\]hence if the permutation $a_i = f(i)$ is bad, then the inverse permutation $a_i = f^{-1}(i)$ is also bad. It remains to show that there are an odd number of involutions $f$. To be completed

45 mohs?

The case $n=1$ is obvious. Suppose $n>1$. We call a permutation bad if $\frac{x_k}{k}$ are not all distinct and good otherwise. Now notice that if $\sigma$ is good then so is $\sigma^{-1}$. Therefore, if $\sigma$ is good and $\sigma^2\neq I$ then we can pair it up with another permutation $\sigma^{-1}$. Therefore, define $$S=\{\sigma(\sigma(x))=x\forall x:\sigma\in S_n\}$$It suffices to show that the number of good permutations in this set is odd. Indeed every permutation in $S$ can always be decomposed into $2$-cycles and fixed points, and every good permutation contains at most $1$ fixed points. Therefore, good permutation in $S$ consists of $1$ fixed points and $\frac{n-1}{2}$ $2$-cycles if $n$ is odd and $\frac{n}{2}$ $2$-cycles if $n$ is even. Define $T$ to be the set of permutations with $1$ fixed points and $\frac{n-1}{2}$ $2$-cycles if $n$ is odd and the set of permutations with $\frac{n}{2}$ $2$-cycles if $n$ is even. Notice that by simple counting we obtain $$|T|=\begin{cases}1\cdot 3\cdot...\cdot(n-2)\cdot n&\text{if $n$ is odd}\\ 1\cdot3\cdot...\cdot(n-1)&\text{if $n$ is even}\end{cases}$$which is odd in odd cases. Therefore, it suffices to show that the number of bad permutations is even. To do this, we will use the Inclusion-Exclusion principle. Define $$Q=\{(a,b,c,d):ad=bc:1\leq a<b<c<d\leq n\}$$For each pair $(a,b,c,d)\in Q$, let $$S_{a,b,c,d}=\{\sigma\in T:\text{ $\sigma$ swaps $(a,b)$ and $(c,d)$, OR swaps $(a,c)$ and $(b,d)$}\}$$Obviously the size of $S_{a,b,c,d}$ and arbitrary union of them are even since the permutations swapping $(a,b)$ and $(c,d)$ can be bijectively mapped to those which swaps $(a,c)$ and $(b,d)$. Now notice that a mapping belongs to $T$ is bad if and only if it belongs to some $S_{a,b,c,d}$. Therefore, by inclusion-exclusion principle, the number of bad permutations in $T$ is equal to the sum of the size of $S_{a,b,c,d}$ and their unions modulo $2$, where the sum runs through all of $Q$, which is even and we are done.

I think in the following idea, but I cound't solve it :

We say that a permutation is good if it satisfies the hypotheses in the problem, and bad otherwise. Non-involutions do not matter: Consider a non-involution $f$ that permutes over $[n]$. Then we have \[ \frac{f(i)}{i}=\frac{f(j)}{j} \Leftrightarrow \frac{f^{-1}(f(i))}{f(i)}=\frac{f^{-1}(f(j))}{f(j)}, \]so using an obvious bijection it suffices to focus only on involutions. Involutions and Matchings: We can represent a good involution of $[n]$ as a maximal matching over $[n]$, because there is at most one fixed point. We say that a matching is good if its corresponding permutation is good, and bad otherwise. Realize that constructive counting gives us that the number of maximal matchings over $[n]$ is $(2\lceil n/2\rceil-1)!!$, which is odd. Label an edge between vertices $a$ and $b$ (where $a<b$) with $a/b$. Given a matching we say its friends are those matchings obtained as follows: for each label $\lambda$, we take some pairs of edges (which can be none) with label $\lambda$ and apply the following operation: Given edges $ab$ and $cd$ with the same label where $a<b$ and $c<d$, interchange $b$ and $c$. Key Lemma: The matching corresponding to the permutation $\sigma$ has an even number of friends (including itself) iff it is bad. Proof: Fix a label $\lambda$, and suppose $n$ edges have label $\lambda$. Select $k$ disjoint pairs of edges and apply the operation on each pair; the number of ways to do such a swapping is $\binom{n}{2k} (2k-1)!!$, so summing over $k$, the total number of ways to perform operations on the edges labeled $\lambda$ is \[\sum_{k \ge 0} \binom{n}{2k} (2k-1)!! \equiv \sum_{k \ge 0} \binom{n}{2k} =2^{n-1} \pmod{2}. \]The LHS of the above equivalence is even if and only if $n > 1$, and consequently odd if and only if $n=1$. Moreover, the number of friends of the matching corresponding to $\sigma$ is the product of $\sum_{k \ge 0} \binom{n}{2k} (2k-1)!!$ over all $\lambda$ on the labels. Thus, the number of friends of the matching for $\sigma$ is odd if and only if all of the labels are distinct, or equivalently when $\sigma$ is good. $\square$ Finish: Let $G$ be the simple graph with vertices corresponding to all maximal matchings over $[n]$, where edges are determined by friendships, and self-loops are deleted. Note that the good matchings are isolated vertices and that the remaining vertices correspond to bad matchings and have odd degree per the Lemma. Delete the isolated vertices to obtain a new graph $G'$. Thus, a well-known consequence of the Handshake Lemma implies that there are an even number of vertices corresponding to bad matchings. Since the number of vertices of $G$ is odd, the number of vertices corresponding to good matchings is odd, and we are done.

Okay here's a patch for solutions above that claim that doing the "fraction swap" operation proves that there are an even number of bad involutions. Lemma: the number of ways to partition $2n$ or $2n+1$ things into $n$ pairs is odd. The proof of this is pretty easy. Let the multiset of ratios in an involution ${m_1,m_2,\ldots}$. Call the "score" S of an involution be the sum of the floor of $\frac{m_i}{2}$. Note that the fraction swap operation described in previous posts preserve the score. The following claim clearly implies the problem. Claim: the number of involutions with a fixed score $n\ge 1$ is even. Make these involutions vertices in a graph. Place an edge between two vertices if the two permutations can be transitioned between with exactly $n$ fractions swaps which do not overlap. From the lemma we can calculate that the number of possible sets of $n$ disjoint fraction swaps is odd (since $n$, our score, is the maximum possible number of disjoint fraction swaps), and we can also easily check that two distinct sets of $n$ fraction swaps yield a different permutation. Thus every vertex has an odd degree, so there must be an even number of vertices.

Slightly different, hopefully it works. Call a permutation cool if all $\frac{x_k}{k}$ are distinct. Note that a permutation is cool iff its inverse is, since $\frac{x_i}{i}=\frac{x_j}{j} \iff \frac{i}{x_i}=\frac{j}{x_j}$. Hence we can pair up cool non-involutions, and it suffices to show that there are an odd number of cool involutions. Obviously any good permutation has at most $1$ fixed point, so any cool involution may be thought of as a maximal matching, where we pair up as many (disjoint) pairs of points into cycles as possible; note that we will pair everything for $n$ even and have exactly one fixed point when $n$ is odd. Consider a complete graph on labeled vertices $v_1,\ldots,v_n$ with colored edges such that We never have any $a<c<d<b$ such that $\overline{v_av_b}$ and $\overline{v_cv_d}$ are edges of the same color. If $\overline{v_av_b}$ and $\overline{v_av_c}$ are both edges of the same color, then we have $\min(b,c)<a<\max(b,c)$ If $a<b<c<d$ exist such that $\overline{v_av_b}$ and $\overline{v_cv_d}$ are edges of the same color, then $\overline{v_av_c}$ and $\overline{v_bv_d}$ exist and are of the same color (not necessarily the same as $\overline{v_av_b}$ and $\overline{v_cv_d}$; in fact, the second condition implies that the two colors must be different). Call such graphs interesting. The task of counting the number of cool maximal involutions on $[n]$ is equivalent to counting the number of maximal matchings on a certain interesting graph $G$ with $n$ vertices that use at most one edge of each color, where $G$ is defined by coloring the edge $\overline{v_iv_j}$ with a color corresponding uniquely to $\frac{i}{j}$ for all $i<j$. In fact, it is more generally true that the number of color-unique maximal matchings (call these matchings good) on any interesting graph for any $n$ is odd. We will prove this by strong induction on $n$, with small $n$ (including the vacuous $n=0$) following by inspection. Observe that if we delete some number of vertices from an interesting graph and relabel the vertices in the same relative order (for instance, deleting $v_1$ and $v_4$ from an interesting graph on $5$ vertices remaps $v_2 \to v_1$, $v_3 \to v_2$, $v_5 \to v_3$), we clearly obtain another interesting graph. We can "almost" count the number of good matchings on an interesting graph by matching $v_1$ with another vertex $v_k$—or possibly itself if $n$ is odd—and then counting the number of good matchings on the interesting graph formed by deleting $v_1$ and $v_k$. Observe that there are an odd number of choices for pairing (including $v_1$ itself when $n$ is odd), and by inductive hypothesis each of these corresponds to an odd number of good matchings on the remaining graph, for a total of an odd number of good matchings. However, this overcounts precisely the situations where we match $v_1$ and $v_k$, and we select a good matching on the remaining graph that contains exactly one edge $\overline{v_iv_j}$ which is the same color as $\overline{v_1v_k}$; we must show that this quantity is even. If we fix a choice of $\overline{v_1v_k}$, and select some same-color edge $\overline{v_iv_j}$ in the remaining graph, there are an odd number of ways to form a good matching on the graph formed by deleting $v_i$ and $v_j$ from the remaining graph. Some of these matchings, however, will contain exactly one other edge $\overline{v_pv_q}$ that's the same color as $\overline{v_iv_j}$. But if we consider all same-color edges as $\overline{v_iv_j}$, each considered matching on the remaining graph that contains both $\overline{v_iv_j}$ and $\overline{v_pv_q}$ is counted twice, so in fact the number of matchings on the remaining graph with exactly one same-color edge will miraculously have the same parity as the number of same-color edges $\overline{v_iv_j}$ present in it. Therefore, it suffices to show that there are an even number of edges $\overline{v_iv_j}$ with $i<j$ that are the same color as some $\overline{v_1v_k}$ but also disjoint. Finally, we may do what so many have tried and failed at: we may pair the same-colored edges $(\overline{v_1v_k},\overline{v_iv_j})$ with $(\overline{v_1v_i},\overline{v_kv_j})$, since we can't have $k>j$ by our condition, and this pairing is in fact reversible. Hence we are done. $\blacksquare$

We begin with the following claim: Claim: If a permutation works, then its inverse works as well. Proof: Note that all the inverse does is turn $x_k/k$ into $k/x_k$. So if $x_i/i=x_j/j$, then in the inverse, we have $i/x_i=j/x_j$. Thus we can pair permutations that work with their inverses, as long as the permutation is not an involution, i.e. it consists of only fixed points and $2$-cycles. We need to show there are an odd number of working involutions. First, we show the following: Claim:There are an even number of involutions for all $n>1$. Proof: Let $i_n$ be the number of involutions. If $1$ is a fixed point, then there are $i_{n-1}$ involutions, otherwise $1$ has $n-1$ options to pair and there are $(n-1)i_{n-2}$ involutions. So we have the recursion \[ i_n=i_{n-1}+(n-1)i_{n-2},\]and since $i_2$ and $i_3$ are even we're done. Call an involution simple if it has at least two fixed points (obviously all simple involutions work), and complex if it works but has at most one fixed point. Claim: There are an odd number of simple involutions. Proof: The number of non-simple involutions is $n!!$ if $n$ is odd, and $(n-1)!!$ if $n$ is even, which is odd. Claim: There are an even number of complex involutions. Proof: A complex involution has two $2$-cycles $a\leftrightarrow b$ and $c\leftrightarrow d$ with $a/b=c/d$. Note that if we switch these cycles to $a\leftrightarrow c$ and $b\leftrightarrow d$, the involution still works. Call a maneuver a nonempty choice of disjoint pairs of $2$-cycles with the same ratio, and then applying this switching operation. To perform a maneuver, we first partition the $2$-cycles into sets with equal ratio. Then we assign each of these sets an involution, which represents which pairs of $2$-cycles we should switch! Since we are dealing with a complex involution, at least one of the sets has at least two $2$-cycles, so in particular the number of ways to assign each set an involution is even. But we must make sure that we don't assign all sets the identity, so there are an odd number of maneuvers. As such, create a graph $G$ with vertex set of complex involutions. Draw an edge if you can maneuver from one involution to another (clearly this relation is symmetric). We've shown that every vertex has odd degree, so there are an even number of complex involutions, as desired.

Whats wrong in this i accidentally showed $a_n$ is even for large even integers $n$. We firsly consider the number of invoutions as if $\pi$ works $\pi^{-1}$ works. Call any such permutation as "successfull" pick $n$ as a large even integer firstly. large enough so that there exists atleast 3 primes in the interval $[n,\frac{n}{2})$ which we know exists by stronger bertands. Claim: in any successfull permutation there dosent not exist any fixed points. Proof: as $n$ is even the number of fixed points is even and as there exists at max one we are done. Obviously the numbers ${1,2,....n}$ must contain a subset $S$ of size $\frac{n}{2}$ such that for every element $e$ in $S$ , $\pi(e)$ is not in $S$ . Now we prove given any specific $S$ the number of $\pi$ we get for that is even . we can WLOG assume there exists atleast $2$ primes in $S$ which are greater than $\frac{n}{2}$ as we can always swap $S$ with its .compliment. and there are atleast $3$ such primes. which shows this is justified. Now call the primes in that interval as "cool" primes. we basically want the number of ways to assign each element $e$ in $S$ a $\pi(e)$ in its compliment. such for any two distinct elements $e_1,e_2$ . in $S$ $\frac{\pi(e_1)}{e_1}$ and $\frac{\pi(e_2)}{e_2}$ are neither inverse nor equal. Say there are $X$ ways to assign the permutations of the uncool elements of $S$ . such that atleast two uncool elements $e_1,e_2$ in $S$ do not cause this issue. Claim: we can set the permutations of the cool elements anwyay we like given the permutation of the uncool elements. Proof: Here we entire number theory land. say it does cause an issue that is one of two things $\frac{\pi(P)}{P}=\frac{\pi(e)}{e}$ for some $e \neq P$ or $\frac{\pi(P)}{P}=\frac{e}{\pi(e)}$ where $P$ is a cool prime. lets first bunk first case observe denominator of LHS has to be $p$ as if $\pi(P)$ has to be multiple of $P$ and $\leq n$ its equal $P$ which isnt possible. but then $P|e$ as well then again $e=P$ which isnt possible. in second case also we must have $\pi(e)=P$ which isnt possible as $\pi(e)$ is in compliment of $S$. With that done say there are $d \geq 2$ cooll primes in $S$. so for each arrangmenet of non cool elements of $S$ we have $d!$ arrangements of cool elements giving a total of $d!X$ which is even. But by this the number of $\pi$ by summing up across different $S$ is also even.

Probably the most similar to #25. Claim: The permutation $p$ works iff its inverse $p^{-1}$ works. Proof. We have that $\frac{x_a}{a} = \frac{x_b}{b}$ iff $\frac{a}{x_a} = \frac{b}{x_b}$. $\blacksquare$ We thus to reduce to considering when our permutations are involutions. Furthermore, our permutations must have exactly $0$ or $1$ fixed point. We now set up for proving a claim which finishes. Define a pair-set as a set of pairs $(a, b)$ with positive integers $a < b$ where all integers in the pair-set are distinct. Call two pairs $(a, b), (c, d)$ equal if their values $\frac{a}{b} = \frac{c}{d}$ are equal. We say a pair-set is cancelling if has two equal pairs in the pair-set. We define the swapping operation $(a, b), (c, d) \mapsto (a, c), (b, d)$ which acts on two equal pairs and preserves their equality. We apply this swapping operation to two pairs in a pair-set. Claim: The number of possible swapping operations to apply on a pair-set are the same $\pmod{2}$ after applying a swapping operation. Proof. The number of swapping operations is the same as the number of pairs of equal pairs. The swapping operations takes two pairs $p_1, p_2$, and changes their value, preserving their equality. Then the values equal to the old pair value lose an even amount, the values equal to the new pair value gain an even amount, and the connection $p_1$ to $p_2$ is maintained. $\blacksquare$ Claim: A graph in which every vertex has odd degree has an even number of vertices. Proof. Decompose into paths. $\blacksquare$ Claim: Take equivalence classes under the swapping operation. A cancelling pair-set has an equivalence class with even size. Proof. We induct downwards. Take the graph $G$ on pair-sets connecting pair-sets if they are one swapping operation away. If each vertex in this graph has odd degree we are done. Else, each vertex has even degree, and thus degree at $2$. This means that for a pair $(a, b)$ in a pair-set, one of the operations possible can't contain the pair $(a, b)$, as there are at least two operations, and if they both use $(a, b)$ then take the two others as a pair. This means that we can replace $G$ as the disjoint union of $G_{b_1} \sqcup G_{b_2} \sqcup \dots \sqcup G_{b_k}$ where $G_{b_k}$ is the subset of $G$ consisting of pairs with $(a, b_k)$. By the above we have that $G_{b_k}$ has size at least $1$ and is closed under the swapping operation ignoring $(a, b_k)$, so it has even size inductively. $\blacksquare$ For even $n = 2k$, the number of involutions with no fixed points on $n$ vertices is $(2k-1)!! = 1 \cdot 3 \cdot \cdots \cdot (2k-1)$ which is odd, so removing the equivalence classes of cancelling pair-sets gives an odd number of noncancelling pair-sets which finishes. For odd $n = 2k+1$, the number of involutions with one fixed point is $(2k-1)!! \cdot (2k+1)$ which remains odd so we finish as above.