Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
    
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.) – 2012rcampion Jan 8 at 18:53
up vote 14 down vote accepted

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$)

share|improve this answer
    
Clever solution. – Fimpellizieri Jan 8 at 19:26
1  
That was quick! Helpful drawings and a clear argument in under 20min, well done! – Mike Earnest Jan 8 at 19:26

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"

share|improve this answer
    
I think that each edge string will be parallel to one of the diameters. – 2012rcampion Jan 8 at 18:52
    
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 – Beastly Gerbil Jan 8 at 18:54
    
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. – Milo Brandt Jan 8 at 19:11
    
@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. – Brilliand Jan 8 at 23:28
    
@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) – Milo Brandt Jan 8 at 23:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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