Round-robin party presents (or: Graeco-Latin square with additional cycle property) A group of $n$ people organizes recurring parties, $n-1$ events in total. At each event, each person offers a present to one other person, and each person receives a present ($n$ presents exchanged in total per event). Is it possible to organize the parties so that


*

*each person has given a present to each other person after $n-1$ parties,

*each person has received a present from each other person after $n-1$ parties,

*at each party, the "gives a present" relation forms a single cycle (i.e., the group cannot be subdivided in subgroups so that no presents are exchanged between persons in different subgroups)?


To me, it looks as if this is possible if and only if $n$ is prime, but a proof remains elusive to me. Is this a well-known problem? What would be a good formulation of the problem that allows for an elegant proof?
Pieter21 mentioned Graeco-Latin squares: for given $n$ we search for a Graeco-Latin square with w.l.o.g. the first column equal to $A\alpha, B\beta, C\gamma, \ldots$ and the other columns such that each forms a cycle, e.g., $A\beta \rightarrow B\gamma \rightarrow C\delta \rightarrow D\alpha \rightarrow A\beta$ is a cycle for $n=4$.
This is from a real-life setting where $n$ happens to be $6$ (a solution can be ruled out due to the nonexistence of such a Graeco-Latin square). Please feel free to re-tag as appropriate.
 A: Let's rephrase this question into a graph theory question. 
Basically you are asking if we have the directed complete graph, $K_n^*$, then there a decomposition into directed cycles all having length $n$. If you are not used to graph theory, the directed complete graph is a graph on $n$ vertices where each vertex has a directed arc to all other vertices. This question was solved in a paper "Cycle decompositions IV: complete directed graphs and fixed length directed cycles". A special case of the main theorem in the paper is
Given $K_n^*$, there exists a cycle decomposition where all cycles have length $n$ if and only if $n$ divides the number of edges, and $n \not = 4$ or $n \not =6$.
The number of edges in $K_n^*$ is $(n-1)(n)$, therefore $n$ always divides the number of edges. Thus we can conclude that for all $n$ not $4$ or $6$ such a decomposition exists. I haven't read the paper entirely as it is $44$ pages long so I'm not sure how they actually construct the decomposition (if they did so constructively). 
