i think i might actually have a bijective solution here.... firstly rephrasing in terms of permutations, the number of 'good' distributions is simply the same as saying that if we consider the digraph of the corresponding permutation, then the undirected graph that results from this digraph is bipartite with partition sets of equal size. Since the corresponding graph has to be bipartite, it means that every cycle in the cyclic representation is even. Conversely, starting with a permutation that has only even cycles say $C_1,C_2,\ldots,C_r$ of sizes $2k_1,2k_2\ldots,2k_r$ resp., it is easy to see that if we consider a proper coloring of this graph, then both the color classes are equal-that has to be the case, anyway, since this is a permutation. so what we need to count is simply the number of permutations that have all cycles even.I claim that this number is $1^2\cdot 3^2\cdots(2n-1)^2$ and so in particular is even. this can be bijectively seen as follows: Consider all ordered tuples of partitions $(\Pi,\Psi)$ of $X=\{1,2,\ldots,2n\}$ of type $2^n$(i.e., all parts have size $2$). The number of such tuples is of course, the reqd number. Wha we now need is a bijection between these and the permutations with only even cycles. What we can do is, firstly retain(and remove) all the common sets in both partitions. Call the new set again as $X$(after deleting the elements of the common partitions). Now consider the two partitions and the parts of $\Pi$(resp. $\Psi$) that are not yet removed. Now starting from the least element of $x\in X$ and its corresponding partition, (say $\{x,y\}$),start with the word $xy$ and proceed to the other partition to that part that contains $y$.Call it $z$. enlarge the word to $xyz$ and again go to the part of the other partition that contains $z$ and keep proceeding till we hit an element that was already covered in the word.since both are partitions, one can argue that when we reach an already registered entry it has to be $x$ again. And since there are pairs counted at all times except the beginning and the end we reach a word of even length. This is one of the cycles of the reqd permutation. Again delete these elements from $X$ and iterate. This algorithm is easily inverted and accomplishes the desired result.

seshadri wrote: we consider the digraph of the corresponding permutation, then the undirected graph that results from this digraph is bipartite with partition sets of equal size. I couldn't get how did you obtain this undirected graph?

I couldn't understand, can a question be given more than one student?

seshadri wrote: This algorithm is easily inverted and accomplishes the desired result. you mean that, the number of the desired number is the square of the number of the all possible matchings in a 2n-complete graph. this, however, can not be inverted for exanple, Π={1,2}{3,4}{5,6}{7,8} Ψ={1,3}{2,4}{5,7}{6,8} and Π={1,2}{3,4}{5,7}{6,8} Ψ={1,3}{2,4}{5,6}{7,8}

We claim the answer is $f(n) = (2n-1)!!^2$, assuming that no two students receive the same problem. First, the re-distribution of problems can be modeled by a permutation $\sigma$ of $[2n]$ (the first $2n$ positive integers). Write the permutation in cycle notation. Suppose we have a fair contest; without loss of generality, let contestants $1, 2, 3, \dots, n$ receive their problems from contestants $n+1, n+2, \dots, 2n$. This easily implies $n+1, n+2, \dots, 2n$ receive their problems from contestants $1, 2, 3, \dots, n$. Let $A = \{1, 2, \dots, n\}$ and $B = \{n+1, n+2, \dots, 2n\}$. Then $1 \in A$, so $\sigma(1) \in B, \sigma(\sigma(1)) \in A$, $\dots$. This implies the cycle containing 1 has even length. By a similar argument, all cycles of the permutation representing the fair contest have even length. Conversely, if all cycles have even length, then in each cycle color the numbers red and blue, such that no two consecutive numbers in the cycle are the same color. Then the red contestants receive their problems from the blue contestants, and vice versa. Therefore, it suffices to count the number of permutations of $[2n]$ with all cycles being even length. There are two ways to do this. Solution 1. (HMMT-style bash) Let $f(n)$ denote this quantity for a given $n$. Then by considering the length of the cycle $1$ is part of, we derive the recurrence $f(0) = 1$, and for $n \ge 1$, $$f(n) = \sum_{k=0}^{n-1} (2n-1)(2n-2)\dots(2k+1) f(k).$$Let $f(n) = (2n)! g(n)$; then we get $g(0) = 1$ and $2n g(n) = g(n-1) + g(n-2) + \dots + g(0)$. Thus $2n g(n) = g(n-1) + 2(n-1) g(n-1) = (2n-1) g(n-1)$, so $g(n) = \frac{2n-1}{2n} \cdot g(n-1)$. By induction we get $g(n) = \frac{(2n-1)!!}{(2n)!!}$, so $f(n) = (2n-1)!!^2$, as claimed. Solution 2. (Bijection) We claim that $f(n) = g(n)^2$, where $g(n)$ is the number of ways to partition $[2n]$ into $n$ pairs. (It is well-known that $g(n) = (2n-1)!!$.) Indeed, it suffices to establish a bijection between permutations $P$ of $[2n]$ with all cycles of even length, and ordered pairs of permutations $(A, B)$ of $[2n]$ with all cycles of length $2$. For a given $P$, write it in cycle notation. In each cycle, color the smallest number red and alternate coloring numbers red and blue such that no two consecutive numbers are the same color. Then we can let $A, B$ be the set of pairs $(x, P(x))$ for all red, blue $x$ respectively. Conversely, suppose we are given $A, B$. They determine $n$ red and $n$ blue edges on a graph with vertices at $1, 2, 3, \dots, 2n$. Forgetting about the colors for a moment, we see that each vertex has degree $2$, so the graph is a disjoint union of cycles. Now let's make everything colorful again. The edges of each cycle alternate red, blue, red, blue, .... We assign the cycle a direction by considering the vertex $v$ (of the cycle) with smallest number, and pointing the cycle in the direction of the red edge emanating from $v$. Thus, by piecing together all directed cycles, we obtain $P$ from $A, B$. Thus, our claimed bijection is invertible, proving that $f(n) = g(n)^2$.

Jettofaiyafukushireikan wrote: seshadri wrote: This algorithm is easily inverted and accomplishes the desired result. you mean that, the number of the desired number is the square of the number of the all possible matchings in a 2n-complete graph. this, however, can not be inverted for exanple, Π={1,2}{3,4}{5,6}{7,8} Ψ={1,3}{2,4}{5,7}{6,8} and Π={1,2}{3,4}{5,7}{6,8} Ψ={1,3}{2,4}{5,6}{7,8} Using my algorithm, it can be inverted. The first one is $(1243)(5687)$ and the second is $(1243)(5786)$. I hope this example better illustrates my algorithm and proves the correctness of the solution.

Fairly easy for Romania TST... But good problem! As above solutions, the number of fair contest distribution is same as the number of permutation $\sigma$ on $2n$ numbers such that each cycle length is even. Let's call this permutations good, and number of good permutations $f(n)$. We claim that $f(n)=(2n-1)^2f(n-1)$ for all $n\geq2$. Then $f(n)=[(2n-1)!!]^2$ by induction, and our problem will be solved. Let $S_{u, v}$ be the number of good permutation $\sigma$ on ${1, ..., 2n}$ satisfying $\sigma(1)=u$, $\sigma^2(1)=v$. Since $\sigma$ is $u\neq1$, If $v\neq1$ then all $1, u, v$ is pairwise different, so the number of $S_{u, v}$ is $(2n-1)(2n-2)$. And if $v=1$, then number of $S_{u, v}$ is $2n-1$. So the number of all $S_{u, v}$ is $(2n-1)^2$. We now show that $|S_{u, v}|=f(n-1)$. Let $\tau$ be the permutation on ${1, ..., 2n}$ except ${u, v}$ such that if $i\neq1$ then $\tau(i)=\sigma(i)$, and $\tau(1)=\sigma^3(1)$(this definition is only needed when $v\neq1$). Then $\tau$ is good permutation on $2n-2$ numbers, since all other cycles of $\sigma$ is unchange and cycle containing $1$ has decreased it's length by $2$($v\neq1$) or disappeared($v=1$). And it's easy to see relationship between $\sigma$ and $\tau$ is bijection. Just add $u, v$ and disappeared arrows, you'll see it satisfies bijection condition. So $|S_{u, v}|=f(n-1)$ is proved. Since $f(n)$ is sum of all $|S_{u, v}|$, it's obvious that $f(n)=(2n-1)^2f(n-1)$. Done! Comment. As you can see, this solution is just combinatorial explanation of induction solution in #6.