11
$\begingroup$

There are 2016 wooden stakes, evenly spaced around a large circle. You have 2016 labels featuring all the numbers 1 to 2016, and you proceed to label each stake in any order you please.

Finally, you connect the stakes with taut strings in the order they are labeled, so 1 is tied to 2, 2 is tied to 3, and so on. You also tie 2016 to 1 to create a closed loop.

Is it possible to do this in such a way that no two of the 2016 strings are parallel?

$\endgroup$
1
  • $\begingroup$ My guess is that this is only possible for an odd number of stakes. (I know that it is possible for odd numbers, but not that it is impossible for even numbers.) $\endgroup$ Commented Jan 8, 2016 at 18:53

2 Answers 2

14
$\begingroup$

No, it is not possible. In particular, consider that, were we to number the stakes from $0$ through $2015$ going evenly around the circle, then a string going from $a$ to $b$ is parallel to one going from $c$ to $d$ if and only if $a+b\equiv c+d\pmod{2016}$. This may be seen as there is a reflection taking stake $a$ to stake $b$ which also takes stake $c$ to stake $d$. Two sets of parallel lines between such labeling are shown below:

enter image description here enter image description here

Thus, we may reduce the problem to the following:

Is there a sequence $s_0,\ldots,s_{2015}$ such that the value of $s_n+s_{n+1}$ is distinct for every $n$ between $0$ and $2015$ (inclusively, taking the last value to be $s_{2015}+s_0$)?

And the answer is "no" because there are only $2016$ equivalence classes mod $2016$, meaning each equivalence class must contain exactly one value $s_{n}+s_{n+1}$. However, that means that $$1008\equiv\sum_{i=0}^{2015}i\equiv \sum_{n=0}^{2015}s_n+s_{n+1}\equiv 2\sum_{n=0}^{2015}s_n\equiv 2\sum_{i=0}^{2015}i\equiv2\cdot 1008\pmod{2016}$$ which is false since $2\cdot 1008 \not\equiv 1008$. Note that we used, in our second to last step, that $s_n$ enumerates the equivalence classes mod $2016$.

(Note that the equivalence $1008\equiv\sum_{i=0}^{2015}i\pmod{2016}$ comes from a pairing argument - each summand $i$ may be paired with its opposite $-i$ making a total of $0$, with the exception of the two $i$ such that $i=-i$ - which are $0$ and $1008$. So the sum is $0+1008=1008$)

$\endgroup$
2
  • $\begingroup$ Clever solution. $\endgroup$ Commented Jan 8, 2016 at 19:26
  • 1
    $\begingroup$ That was quick! Helpful drawings and a clear argument in under 20min, well done! $\endgroup$ Commented Jan 8, 2016 at 19:26
2
$\begingroup$

Yes, you simply make each string go across the circle and then too the next one along. Like this but with 1008 strings acting as diameters and the other 1008 going to the one adjacent so it completes the circle:

"Example"

$\endgroup$
6
  • $\begingroup$ I think that each edge string will be parallel to one of the diameters. $\endgroup$ Commented Jan 8, 2016 at 18:52
  • $\begingroup$ Aaaah! Good point. If the strings were sort of bent so they form an arch that creates the edge of the circle, they wouldn't be but in this case you're right @2012rcampion $\endgroup$ Commented Jan 8, 2016 at 18:54
  • $\begingroup$ None of the lines would be parallel in this - it's just that this doesn't make a path around the circle. If you always, for instance, move to the next most counterclockwise diameter, then when you get back to the original diameter, you get back to the wrong side - so you haven't made a loop. $\endgroup$ Commented Jan 8, 2016 at 19:11
  • $\begingroup$ @MiloBrandt Works well enough if you sort the diameters by the position of their counterclockwisemost stake, then determine "next one along" according to that sort order. $\endgroup$
    – Brilliand
    Commented Jan 8, 2016 at 23:28
  • $\begingroup$ @Brilliand It doesn't work when I count - here, the number of diameters is even, so we can imagine that we switch sides and turn the diameter a little bit at each step. By the end of our process, we've switched sides an even number of times (so we're on "the same side" in a sense) - BUT the diameter's made a half-turn rotation, so in a more useful sense, we're on the wrong side. (If the number of diameters were odd, then the edges would each be parallel to a diameter) $\endgroup$ Commented Jan 8, 2016 at 23:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.