we start with a simple observation: if we line up all the integers $n,n+1,\ldots,n+32$ in that order circularly,(so that $n$ has neighbors $n+1,n+32$, $n+1$ has neighbors $n,n+2$ and so on) then this is a 'good' arrangement(i.e. any two consecutive are relatively prime), since $n$ is odd. to get the required arrangement, we could 'break and fuse' this arrangement to create two good circular arrangements. suppose we form the necklaces as $n+k,n+k+1,\ldots,n+k+13$ and $n+k+14,\ldots,n+32,n,\ldots,n+k-1$ then in order that this works we need that $(n+k,n+k+13)=1,(n+k-1,n+k+14)=1$. this is equivalent to saying that $r=n+k$ satisfies $r\not\equiv 1\pmod 3,r\not\equiv 1\pmod 5,r\not\equiv 0\pmod {13}$ and also $k\le 18$. it is now a simple exercise to see that this can be achieved quite easily(i am not going to prove this, but i think it should be pretty straightforward, since among $18$ numbers there can be atmost $2$ of them that are divisible by $13$ but lots more that satisfy the other two).

Obviously $ (m,m+1)=(m,1)=1$. Make a $ 33$ bead arrangement with the numbers in order. We can easily verify that $ (n,n+32)=(n,32)=1$ since $ n$ is odd. Hence this is a good necklace. Now lets remove $ 13$ beads from this larger necklace, and connect the two parts into the two satisfactory necklaces. Say the first number that we remove is $ n+k$, then the end of that $ 14$ chain is $ n+k+13$. We only have to find $ k$ so we have the two new adjacent beads have relatively prime labels: $ (n+k,n+k+13)=1$ and $ (n+k-1,n+k+14)=1$. Note that $ k\in[0,20]$. Let $ a=n+k$. The condition is $ (a,a+13)=(a,13)=1$ and $ (a-1,a+14)=(a-1,15)=1$. Note that $ a-1$ ranges between $ 21$ consecutive integers. Choose $ a-1$ even. Then $ (a-1,15)=1$ and $ a$ ranges from at least $ 10$ consecutive even integers. Now if $ (a,13)=1$, we are done. If $ (a,13)=13$, then $ (a-2,13)=(a+2,13)=1$ and since $ a$ is among at least $ 10$ consecutive even integers, $ a-2$ and/or $ a+2$ is also among these integers. Hence such $ a$ exists and we are done.

Sorry for bumping this, but I have some questions about altheman's proof. First, shouldn't k range from 1 to 18, not 0 to 20? (if the 14-chain is to be in between the two ends). Also, while trying to find a range of suitable a-1's such that the gcd (a-1, 15) = 1, choosing a-1 as even does not guarentee that the two are relatively prime. I think you need to prove (as seshadri said) that in any set of 18 consecutive numbers s = n+k (k ranging from 1 to 18) there exists at least one number such that it is not 1 mod 3, 1 mod 5, and 0 mod 13: In the set n+1, n+2, ... n+18, where n is odd, we can put each number in modulo 3, and despite the shift of n the distribution of the residues will be the same (because of symmetry). So there are 6 numbers 1 mod 3. Writing in mod 5, the most frequent residue appears 4 times so there are at most 4 numbers 1 mod 5. By the same logic, there are at most 2 numbers 0 mod 13. At the most we could rule out 12 numbers (maybe less because of overcounting mod 15), yet we have 18 to choose from therefore a suitable n + k exists. If I just got confused and didn't really understand I apologize and help would be appreciated =p.

Is the oddness of $n$ used in the solutions above? It seems no need for that. Or do I miss something?

Arslan wrote: Is the oddness of $n$ used in the solutions above? It seems no need for that. Or do I miss something? Because if n is even then by Pigeonhole Principle you always have 2 adjacent even beads so it does not work

Consider the 3 constructions A: n, n+1, n+2, ... , n+13, B: n+14, n+15, n+16, ... , n+32 A: n+19, n+20, n+21, ... , n+32, B: n, n+1, n+2, ... , n+18 A: n+2, n+3, n+4, ... , n+15, B: n, n+1, n+28, n+27, n+26, ... , n+16, n+29, n+30, n+31, n+32 First one fails if n = 1 (mod 3) or n = 0 (mod 13) Second one fails if n = 0 (mod 3) or n = 7 (mod 13) Third one fails if n = 2 (mod 3) or n = 10 (mod 13) Since no n can fail all 3 constructions, at least 1 of them work. If you are viewing this a few years in future the full proof would be linked at https://infinityintegral.github.io/contest-collections

seshadri wrote: we start with a simple observation: if we line up all the integers $n,n+1,\ldots,n+32$ in that order circularly,(so that $n$ has neighbors $n+1,n+32$, $n+1$ has neighbors $n,n+2$ and so on) then this is a 'good' arrangement(i.e. any two consecutive are relatively prime), since $n$ is odd. to get the required arrangement, we could 'break and fuse' this arrangement to create two good circular arrangements. suppose we form the necklaces as $n+k,n+k+1,\ldots,n+k+13$ and $n+k+14,\ldots,n+32,n,\ldots,n+k-1$ then in order that this works we need that $(n+k,n+k+13)=1,(n+k-1,n+k+14)=1$. this is equivalent to saying that $r=n+k$ satisfies $r\not\equiv 1\pmod 3,r\not\equiv 1\pmod 5,r\not\equiv 0\pmod {13}$ and also $k\le 18$. it is now a simple exercise to see that this can be achieved quite easily(i am not going to prove this, but i think it should be pretty straightforward, since among $18$ numbers there can be atmost $2$ of them that are divisible by $13$ but lots more that satisfy the other two). Finishing your proof, of the 18 numbers at most 2 are multiple of 13, 6 are multiple of 3, and at most 4 are multiples of 5. Even in worst case they dont coincide we still have 6 ok numbers.