Let $n>2$ be an integer. A deck contains $\frac{n(n-1)}{2}$ cards,numbered \[1,2,3,\cdots , \frac{n(n-1)}{2}\]Two cards form a magic pair if their numbers are consecutive , or if their numbers are $1$ and $\frac{n(n+1)}{2}$. For which $n$ is it possible to distribute the cards into $n$ stacks in such a manner that, among the cards in any two stacks , there is exactly one magic pair?
Problem
Source: Baltic Way 2015
Tags: combinatorics, Baltic Way
08.11.2015 19:49
i think it will be $\frac{n(n-1)}{2}$ not $\frac{n(n+1)}{2}$
29.11.2015 09:45
This is Eulerian circuit, isn't it? Let $S_{i}$ be the stack of cards which could be considered as Vertex in the graph. So we can draw edge from $S_{i}$ to $S_{j}$, if some magic pair of cards are belonged to $(S_{i},S_{j})$. so $n$ be $2k+1$
18.03.2018 17:02
If n is even, a simple counting argument shows that those n won't make the distribution possible. Indeed, Each card can make a magic pair to exactly 2 other cards. Look at a stack. There are $n-1$ other stacks, so any pair of our chosen stack and the other stacks, so this stuck must contain at least $\frac{n-1}{2}$ cards which is not an interger, which means in each stuck we must have $\frac{n}{2}$ cards. But $n^2>n(n-1)$ and we're done. If n is odd, as above, the condition would be equivalent with an Eulerian cycle. Take the $K_n$. Every vertex has even degree(n-1) so we have an Eulerian Circuit, let's say $v_1-v_2-...-v_{\frac{n(n-1)}{2}}-v_1$. Mod n, placing the card i in the stack $v_i$ ends up the configuration for the odd case.
15.09.2023 18:21
Note firstly that there cannot be a magic pair of two cards in the same stack. Indeed, if cards $i$ and $i + 1$ are in the same stack, then among them and the stack with card number $i + 2$ (they might be identical), there are two magic pairs, contradiction. Hence no stack contains a magic pair. Suppose firstly that $n$ is even and consider the graph $G$ with vertices $1,2,\ldots,\frac{n(n-1)}{2}$ and an edge between two vertices precisely when they differ by $1$ (including $1$ and $\frac{n(n-1)}{2}$). We wish to partition the vertices into $n$ groups such that for any two groups $A$ and $B$ there is exactly one pair of a vertex in $A$ and a vertex in $B$ which are adjacent. (By the previous paragraph there can be no two adjacent vertices in the same group.) Consider any group $A$. As there are $n-1$ other groups and each vertex in $A$ has degree $2$, there must be at least $\left\lceil \frac{n-1}{2}\right\rceil = \frac{n}{2}$ vertices in $A$. As $A$ was arbitrary, it follows that $G$ has at least $n\cdot \frac{n}{2} > \frac{n(n-1)}{2}$ vertices, contradiction. Now we show that all odd $n$ work. In the complete graph $K_n$ on vertices $1$, $2$, $\ldots$, $n$ (the stacks) each vertex has degree $n-1$, in particular all degrees are even. Hence by Euler's theorem the graph $K_n$ has an Euler circuit $v_1v_2\ldots v_{\frac{n(n-1)}{2}}v_1$. Placing card $i$ into stack number $v_i$ gives the desired distribution, as in the Euler circuit for any vertices $i$ and $j$ the edge $ij$ appears once.