Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

$n$ is nice iff $n=2$ or $n \ge 4$: It is easy to see that $n=1,3$ are not nice and $n=2$ is. Let $t(a,b)$ denote that person $a$ and $b$ traded balls. Thus, if we do $t(1,2)\cdots t(1,n)$ (from left to right) then we have that person $k$ has ball $k-1 \pmod n$. If we do $t(n,n-1)\cdots t(n,2)$ then we have that $1$ and $n$ exchanged ball and everyone else has their own ball. Thus, since we have done all exchanges using $1$ or $n$ and have done no exchange that do not have $1$ or $n$, we can conclude that if $n-2$ is nice then $n$ is. We can easily find a series of exchangements that show that $n=5$ is nice $(t(1,2)t(1,3)t(1,4)t(1,5)t(2,3)t(2,4)t(2,5)t(3,5)t(3,4)t(4,5))$; therefore, all evens $\ge 2$ and all odds $\ge 5$ are nice. $n$ is tiresome iff $n\equiv 0,1\pmod 4$. To prove the 'only if' part, note that if $n\equiv 2,3\pmod 4$ then $\binom{n}{2}$ is odd. Since the exchanges are isomorphic to the transpositions of $S_n$, we have the composition of all of the transpositions is a symmetry of odd sign, but the identity has even sign, contradiciton. (See: http://en.wikipedia.org/wiki/Sign_of_a_permutation) To prove the 'if' part, consider the case that $n\equiv 0\pmod 4$, do $t(k,k+n/2)$ for $n/2\ge k\ge 1$. Notice how this rotates each of balls $1$ through $n$ $180$ degrees. Now for $k=1$ to $k=n/2$, do $t(k,k+1)t(k+1,k+2)\cdots t(k-1+n/2,k)$ and $t(k+1+n/2,k+2+n/2)\cdots t(k-1,k+1+n/2)$, this will rotate each time $1$ through $n$ $360/n$ degrees except $n/2$ and $n$ which are each rotated $180+360/n$ degrees. After $n/2$ times, each of $1$ through $n$ except $n/2$ and $n$ are rotated $180$. $n/2$ and $n$ are rotated $180(n/2)+180=180$ degrees. Thus, all of $1$ through $n$ is rotated $180+180=360=0$ degrees i.e. $n$ is nice. To prove that this uses all $\frac{n(n-1)}{2}$ transpositions, notice that the first part uses $n/2$ transpositions and the second part uses $(n-2)n/2$ transpositions which sums to $(n-1)n/2$, as desired. If $n\equiv 1\pmod 4$ do $t(1,2)t(2,3)t(1,3)\cdots t(1,n-1)t(n-1,n)t(1,n)$. Thus if we remove $1$, we are in a position equivalent to the second part of the case where $n\equiv 0\pmod 4$, so we are done, as desired.

Part 1: Niceness Denote the balls by $a_1,a_2,\dots, a_n$ and we wish to find $n$ such that we can transpose each pair of positions, one at a time, and get no fixed points. We claim that $n$ is nice if and only if $n\neq 3$. Indeed, if $n=3$ and if WLOG positions $(a,b)$ switch and then positions $(b,c)$ switch, then positions $(c,a)$ must switch, which leaves $a$ with the same ball as before. Note that we can do the following transpositions: $(i,i+1), (i,i+2), \dots (i,n)$ and we will do a cyclic shift, turning $(i,i+1,\dots, n)$ into $n,i,i+1,\dots, n-1.$ Call this sequence of moves $C_1(i).$ If we do these same transpositions in the opposite direction, we will get a different cyclic shift: $i+1,i+2,\dots, n, i.$ Call this sequence of moves $C_2(i).$ If we do $C_1(1)$ and then $C_2(n)$ then we will get rid of the need to make any operations on position $1$ or $n$, as well as get the same configuration as before except for $1$ and $n$ transposed. Therefore, if $n-2$ is nice then $n$ is nice. Note that $n=2$ is nice because $C_1(1)$ and $n=5$ is nice because $C_1(1), C_1(3), C_1(2), C_1(4)$ so our claim is proved. Part 2: Tiresomeness Let $S$ be the number of pairs of balls $(a_i,a_j)$ such that $i<j$ and $a_i$'s position is to the right of $j$'s position. Originally $S=0$. Note that each transposition changes $S$ by $1$, so if the ending $S$ is $0$ there must be an even number of moves made, so $n$ is tiresome only if $\tbinom{n}{2}$ is even, or when $n\equiv 0,1\pmod 4.$ If $n=4$, then note that the sequence of transpositions $(1,2),(3,4), (1,4) ,(2,3) ,(1,3), (2,4)$ is enough. If $n=5$ we can find a construction easily. We proceed by induction: if $4k$ is tiresome, then we add on girls $4k+1,4k+2,4k+3,4k+4$. We can make the first $4k$ finish all their internal transpositions and have them each retain her own ball and the last $4$ do the same. Note that $(4k+1,i),(4k+2,i+1),(4k+1,i+1),(4k+2,i)$ is equivalent to $(4k+1,4k+2),(i,i+1)$ and call this transformation $D(4k+1,i).$ Now, $D(4k+1,1),D(4k+3,1),D(4k+1,3),\dots, D(4k+3,4k-1)$ does the trick. If $4k+1$ is tiresome, then we do $D(4k+2,1),D(4k+4,1),\dots, D(4k+3,4k-1)$ and then the tiresome transposition sequence of $4k+1$, and then do the tiresome transpositions sequence if $5$ on $4k+1$ to $4k+5$. We are done.

This problem should be COMBINATORICS

The answer is that all $n$ except for 3 are nice and $n\equiv 0,1\pmod{4}$ are tiresome. For nice, the conclusion is clearly true for $n=2$ and for $n=3$ it is not nice. If we swap $1,2$ and then $1,3$ until $1,n$, then we will create a cyclic shift. Following this, we do $n,n-1$ $n,n-2$ until $n,2$, which will cyclic shift it in reverse. Once this is done, positions $1$ and $n$ are swapped, so neither of them get their own marble back, and the resulting configuration we need to solve in the middle is exactly equivalent to the problem for $n-2$. Thus, $n$ nice implies $n+2$ nice, and $n=2$ and $n=5$ are both nice which solves this part. For tiresome, ${n\choose 2}$ even is necessary since each swap changes the sign of the permutation. This leads us into the main part of the problem, which is the construction for $n\equiv 0,1\pmod{4}$ tiresome. We will construct inductively from $n$ to $n+4$. The main idea in this construction is the following. We say that girl $A$ performs a traversal across a group $A_1,A_2\dots ,A_n$ if $A$ swaps with $A_1$, followed by $A_2$, and so on until $A_n$. The outcome of this is that if $A$ joins the group as $A_{n+1}$, then the balls "cyclic shift" by 1, as in $A_1$ now has $A$'s original ball, $A_2$ has $A_1$'s original ball, and so on until $A_n$ has $A_{n-1}$'s original ball, and finally $A$ has $A_n$'s original ball. Now, we show that if $n$ is tiresome than $n+4$ also is. We will label the original $n$ girls $1,2,\dots n$. We first under the hypothesis execute all swaps among these $n$ without changing the permutation. Now, call the remaining $4$ girls Jessica, Kristie, Angela, and Hannah, who start with marbles $n+1$, $n+2$, $n+3$, and $n+4$ respectively. The construction is as follows. First, Jessica performs a traversal across the original $n$, which gives her marble $n$ and shifts the original group over by 1, and deposits marble $n+1$. Then, Kristie does the same, giving her marble $n-1$ and shifting the group again and deposits the marble $n+2$. Then, Angela swaps with Kristie (who previously had $n-1$ and now has $n+3$) to obtain marble $n-1$, and then does a traversal in the reverse order to take marble $n+2$ as well and deposit marble $n-1$ and also cyclic shift it back by 1. Finally, Hannah swaps with Jessica to obtain marble $n$, and does another reverse traversal, depositing marble $n$ and taking marble $n+1$ to recover the order of the original $n$ girls with another reverse cyclic shift. The current situation is: The original $n$ are solved, and all swaps involving any of them have already been performed. Jessica, Kristie, Angela, and Hannah have marbles $n+4$, $n+3$, $n+2$, and $n+1$. Thus, we can simply swap Jessica and Kristie, then swap Angela and Hannah, then swap Jessica and Angela, and finally swap Kristie and Hannah. The other two swaps between the last 4 have already happened during the previous section, so each swap happens exactly once, which shows the claim. $n=0$ and $n=1$ are clearly tiresome. Note that the above process works even if $n=0$, as the traversals just do nothing, so we are done by induction as all $0,1\pmod{4}$ are tiresome.

If $n=2$ or $n\ge 4$ then there exists a nice game. If $n\equiv 0\pmod 4$ or $n\equiv 1\pmod 4$ there exists a tiresome game. Take the obvious graph theoretic interpretation: we label the nodes $1$ to $n$ (these labels represent the girls) and each move swaps balls along an edge. Let's first prove a lemma. Claim: If $n$ is tiresome, then any value in $[n+1,2n]$ is nice. Proof: Split girls by $\{1,\dots,n\}$ and $\{n+1,\dots,n+k\}$. Perform the $\binom{n}{2}$ swaps within the first set of girls so that positions of balls are the same. Now for each $1\le i\le k$ (in that order) we perform swaps of girls \[(1,n+i),\dots,(n,n+i).\]At the end of each swap the positions of balls are $\{n+i,\dots,n+1,1,\dots,n-i\}$ and $\{n,\dots,n-(i-1),n+i+1,\dots,n+k\}$. Hence at the end of swap $k$ positions of balls are $\{n+k,\dots,n+1,1,\dots,n-k\}$ and $\{n,\dots,n-k+1\}$. Swapping girls in the set $\{n+1,\dots,n+k\}$ will not return a ball to its original girl. $\square$ Now we find all tiresome values. Take the interpretation with permutations. Any swap changes the parity of the number of inversions; thus $\binom{n}{2}$ (the number of swaps) is even. This implies $n\equiv 0\pmod 4$ or $n\equiv 1\pmod 4$. There is a small lemma that will help. Claim: Suppose we have a square graph with edges $1\to 2\to 3\to 4\to 1$. Then we can swap $1234\to 3412$ using all the edges. Proof: Write \[1234\to 1324\to 4321\to 3421\to 3412.\] From \[1234\to 3214\to 3412\]we get a square graph and can use the lemma to find that $4$ is tiresome. Also \[12345\to 52341\to 32541\to 32145\to 35142\to 34152\to 34125\]and now dropping the $5$ we get a square graph and can use the lemma again to find that $5$ is tiresome. Now we induct $n\to n+4$ to show that any $n\equiv 0\pmod 4$ or $n\equiv 1\pmod 4$ is tiresome. First suppose we have some $n\equiv 0\pmod 4$ which is tiresome and wish to show $n+4$ is tiresome as well. Split the girls by $\{1,\dots,n\}$ and $\{n+1,n+2,n+3,n+4\}$ and perform moves in these sets so that balls do not change positions. We are left with a $K_{n,4}$. If we can prove that there exist moves in a $K_{4,4}$ which preserve positions of balls, then we can just partition $\{1,\dots,n\}$ into groups of four and repeat said algorithm $n/4$ times. Hence reduce to this case with sets $\{1,2,3,4\}$ and $\{5,6,7,8\}$, and partition the $K_{4,4}$ into four $K_{2,2}$ square graphs. Applying the small lemma four times we find \[12345678\to 21346578\to 12346587\to 12435687\to 12345678\]thus $n+4$ is tiresome. Now to solve for $n\equiv 1\pmod 4$ we first prove another lemma. Claim: Take a $K_{4,4}$ and an extra node which has an edge to each of the other $8$ nodes. This graph is tiresome. Proof: Label the extra node $0$ and let the two sets of nodes in the $K_{4,4}$ be $\{1,2,3,4\}$ and $\{5,6,7,8\}$. Then for each $i\in \{1,2,3,4\}$ perform the swaps $0\to i\to i+4\to 0$. Then the balls are in positions $56781234$ and the remaining pairs of girls are \[16,17,18,25,27,28,35,36,38,45,46,47.\]Then the sequence \[56781234\to 21786534\to 21436587\]means we can split into two $K_{2,2}$'s: namely with girls $\{1,2,7,8\}$ and $\{3,4,5,6\}$. Applying the small lemma twice finishes. This immediately solves $n=9$. Now we prove that $n\to n+8$ induction works. The idea is simple; single out a special node and note the number of remaining nodes is divisible by $4$. There are three types of edges added with $8$ new nodes: Edges between the $8$ new nodes. Reduce the $K_8$ to a $K_{4,4}$. Edges between the $8$ new nodes and the special node. Do nothing to these. Edges between the $8$ new nodes and the $n-1$ other nodes. We have already found that a $K_{4,4}$ is tiresome, hence a $K_{8,n-1}$ is tiresome and can be ignored. Then we have reduced to only the first two types, which is precisely the previous lemma. Now we have solved the tiresome case. This also proves all $n\ge 5$ are nice. Notice: $2$ is nice. $3$ is not nice. $4$ is nice from \[1234\to 1324\to 2314\to 2413\to 3412\to 4312\to 4321.\] This completes the solution. $\blacksquare$